Prerequisito - Introduzione all'hashing Tabella hash utilizzando l'elenco collegato singolarmente & Implementazione della nostra tabella hash con concatenamento separato in Java L'implementazione della tabella hash utilizzando il concatenamento tramite l'elenco doppiamente collegato è simile all'implementazione Tabella hash utilizzando l'elenco collegato singolarmente . L'unica differenza è che ogni nodo della Linked List ha l'indirizzo sia del nodo successivo che di quello precedente. Ciò accelererà il processo di aggiunta e rimozione di elementi dall'elenco, quindi la complessità temporale sarà ridotta drasticamente.
Esempio:
Se abbiamo un elenco collegato singolarmente:
1->2->3->4Se siamo a 3 ed è necessario rimuoverlo, allora 2 deve essere collegato con 4 e da 3 non è possibile accedere a 2 poiché è un elenco collegato singolarmente. Quindi la lista deve essere attraversata di nuovo, cioè O(n), ma se abbiamo una lista doppiamente collegata, cioè
1<->2<->3<->4È possibile accedere a 2 e 4 da 3, quindi in O(1) 3 può essere rimosso.
Di seguito è riportata l’implementazione dell’approccio di cui sopra:
C++// C++ implementation of Hashtable // using doubly linked list #include
// Java implementation of Hashtable // using doubly linked list class GFG { static final int tablesize = 25; // declaration of node static class hash_node { int val key; hash_node next; hash_node prev; } // hashmap's declaration static class HashMap { hash_node hashtable[] top[]; // constructor HashMap() { // create a empty hashtable hashtable = new hash_node[tablesize]; top = new hash_node[tablesize]; for (int i = 0; i < tablesize; i++) { hashtable[i] = null; top[i] = null; } } // hash function definition int HashFunc(int key) { return key % tablesize; } // searching method void find(int key) { // Applying hashFunc to find // index for given key int hash_val = HashFunc(key); boolean flag = false; hash_node entry = hashtable[hash_val]; // if hashtable at that index has some // values stored if (entry != null) { while (entry != null) { if (entry.key == key) { flag = true; } if (flag) { System.out.println( 'Element found at key ' + key + ': ' + entry.val); } entry = entry.next; } } if (!flag) System.out.println( 'No Element found at key ' + key); } // removing an element void remove(int key) { // Applying hashFunc to find // index for given key int hash_val = HashFunc(key); hash_node entry = hashtable[hash_val]; if (entry.key != key || entry == null) { System.out.println( 'Couldn't find any element at this key ' + key); return; } // if some values are present at that key & // traversing the list and removing all values while (entry != null) { if (entry.next == null) { if (entry.prev == null) { hashtable[hash_val] = null; top[hash_val] = null; break; } else { top[hash_val] = entry.prev; top[hash_val].next = null; entry = top[hash_val]; } } entry = entry.next; } System.out.println( 'Element was successfully removed at the key ' + key); } // inserting method void add(int key int value) { // Applying hashFunc to find // index for given key int hash_val = HashFunc(key); hash_node entry = hashtable[hash_val]; // if key has no value stored if (entry == null) { // creating new node entry = new hash_node(); entry.val = value; entry.key = key; entry.next = null; entry.prev = null; hashtable[hash_val] = entry; top[hash_val] = entry; } // if some values are present else { // traversing till the end of // the list while (entry != null) entry = entry.next; // creating the new node entry = new hash_node(); entry.val = value; entry.key = key; entry.next = null; entry.prev = top[hash_val]; top[hash_val].next = entry; top[hash_val] = entry; } System.out.println( 'Value ' + value + ' was successfully added at key ' + key); } } // Driver Code public static void main(String[] args) { HashMap hash = new HashMap(); hash.add(4 5); hash.find(4); hash.remove(4); } } // This code is contributed by Lovely Jain
# Python implementation of Hashtable # using doubly linked list # declaration of node class hash_node: def __init__(self val key): self.val = val self.key = key self.next = None self.prev = None # hashmap's declaration class HashMap: def __init__(self): # create an empty hashtable self.tablesize = 25 self.hashtable = [None] * self.tablesize self.top = [None] * self.tablesize # hash function definition def HashFunc(self key): return key % self.tablesize # searching method def find(self key): # Applying hashFunc to find # index for given key hash_val = self.HashFunc(key) flag = False entry = self.hashtable[hash_val] # if hashtable at that index has some # values stored if entry is not None: while entry is not None: if entry.key == key: flag = True if flag: print('Element found at key' key ':' entry.val) entry = entry.next if not flag: print('No Element found at key' key) # removing an element def remove(self key): # Applying hashFunc to find # index for given key hash_val = self.HashFunc(key) entry = self.hashtable[hash_val] if entry is None or entry.key != key: print('Couldn't find any element at this key' key) return # if some values are present at that key & # traversing the list and removing all values while entry is not None: if entry.next is None: if entry.prev is None: self.hashtable[hash_val] = None self.top[hash_val] = None del entry break else: self.top[hash_val] = entry.prev self.top[hash_val].next = None del entry entry = self.top[hash_val] entry = entry.next print('Element was successfully removed at the key' key) # inserting method def add(self key value): # Applying hashFunc to find # index for given key hash_val = self.HashFunc(key) entry = self.hashtable[hash_val] # if key has no value stored if entry is None: # creating new node entry = hash_node(value key) self.hashtable[hash_val] = entry self.top[hash_val] = entry # if some values are present else: # traversing till the end of # the list while entry.next is not None: entry = entry.next # creating the new node new_entry = hash_node(value key) new_entry.prev = entry entry.next = new_entry self.top[hash_val] = new_entry print('Value' value 'was successfully added at key' key) # Driver Code if __name__ == '__main__': hash_map = HashMap() hash_map.add(4 5) hash_map.find(4) hash_map.remove(4)
// Java implementation of Hashtable using doubly linked list class GFG { static final int tablesize = 25; // declaration of node static class hash_node { int val key; hash_node next; hash_node prev; } // hashmap's declaration static class HashMap { hash_node hashtable[] top[]; // constructor HashMap(){ // create a empty hashtable hashtable = new hash_node[tablesize]; top = new hash_node[tablesize]; for (int i = 0; i < tablesize; i++) { hashtable[i] = null; top[i] = null; } } // hash function definition int HashFunc(int key) { return key % tablesize; } // searching method void find(int key) { // Applying hashFunc to find index for given key int hash_val = HashFunc(key); boolean flag = false; hash_node entry = hashtable[hash_val]; // if hashtable at that index has some values stored if (entry != null) { while (entry != null) { if (entry.key == key) flag = true; if (flag) { System.out.println('Element found at key ' + key+ ': ' + entry.val); } entry = entry.next; } } if (!flag) System.out.println('No Element found at key ' + key); } // removing an element void remove(int key) { // Applying hashFunc to find index for given key int hash_val = HashFunc(key); hash_node entry = hashtable[hash_val]; if (entry.key != key || entry == null) { System.out.println('Couldn't find any element at this key '+ key); return; } // if some values are present at that key & traversing the list and removing all values while (entry != null) { if (entry.next == null) { if (entry.prev == null) { hashtable[hash_val] = null; top[hash_val] = null; break; } else { top[hash_val] = entry.prev; top[hash_val].next = null; entry = top[hash_val]; } } entry = entry.next; } System.out.println( 'Element was successfully removed at the key ' + key); } // inserting method void add(int key int value) { // Applying hashFunc to find index for given key int hash_val = HashFunc(key); hash_node entry = hashtable[hash_val]; // if key has no value stored if (entry == null) { // creating new node entry = new hash_node(); entry.val = value; entry.key = key; entry.next = null; entry.prev = null; hashtable[hash_val] = entry; top[hash_val] = entry; } // if some values are present else { // traversing till the end of // the list while (entry != null) entry = entry.next; // creating the new node entry = new hash_node(); entry.val = value; entry.key = key; entry.next = null; entry.prev = top[hash_val]; top[hash_val].next = entry; top[hash_val] = entry; } System.out.println( 'Value ' + value + ' was successfully added at key ' + key); } } // Driver Code public static void main(String[] args) { HashMap hash = new HashMap(); hash.add(4 5); hash.find(4); hash.remove(4); } } // This code is contributed by Lovely Jain
// JavaScript implementation of Hashtable using doubly linked list const tablesize = 25; // declaration of node class hash_node { constructor(key val) { this.key = key; this.val = val; this.next = null; this.prev = null; } } // hashmap's declaration class HashMap { constructor() { // create a empty hashtable this.hashtable = new Array(tablesize).fill(null); this.top = new Array(tablesize).fill(null); } // hash function definition HashFunc(key) { return key % tablesize; } // searching method find(key) { // Applying hashFunc to find index for given key const hash_val = this.HashFunc(key); let flag = false; let entry = this.hashtable[hash_val]; // if hashtable at that index has some values stored if (entry !== null) { while (entry !== null) { if (entry.key === key) flag = true; if (flag) { console.log(`Element found at key ${key}: ${entry.val}`); } entry = entry.next; } } if (!flag) console.log(`No Element found at key ${key}`); } // removing an element remove(key) { // Applying hashFunc to find index for given key const hash_val = this.HashFunc(key); let entry = this.hashtable[hash_val]; if (entry.key !== key || entry === null) { console.log(`Couldn't find any element at this key ${key}`); return; } // if some values are present at that key & traversing the list and removing all values while (entry !== null) { if (entry.next === null) { if (entry.prev === null) { this.hashtable[hash_val] = null; this.top[hash_val] = null; break; } else { this.top[hash_val] = entry.prev; this.top[hash_val].next = null; entry = this.top[hash_val]; } } entry = entry.next; } console.log(`Element was successfully removed at the key ${key}`); } // inserting method add(key value) { // Applying hashFunc to find index for given key const hash_val = this.HashFunc(key); let entry = this.hashtable[hash_val]; // if key has no value stored if (entry === null) { // creating new node entry = new hash_node(key value); this.hashtable[hash_val] = entry; this.top[hash_val] = entry; } // if some values are present else { // traversing till the end of the list while (entry !== null) entry = entry.next; // creating the new node entry = new hash_node(key value); entry.prev = this.top[hash_val]; this.top[hash_val].next = entry; this.top[hash_val] = entry; } console.log(`Value ${value} was successfully added at key ${key}`); } } // Driver Code const hash = new HashMap(); hash.add(4 5); hash.find(4); hash.remove(4);
Produzione
Value 5 was successfully added at key 4 Element found at key 4: 5 Element was successfully removed at the key 4Crea quiz