Priekšnosacījums - Jaukšanas ievads Hashtable, izmantojot atsevišķi saistīto sarakstu & Mūsu pašu hash tabulas ieviešana ar atsevišķu ķēdi Java Hash tabulas ieviešana, izmantojot ķēdi, izmantojot divkārši saistīto sarakstu, ir līdzīga ieviešanai Hashtable, izmantojot atsevišķi saistīto sarakstu . Vienīgā atšķirība ir tā, ka katram Saistītā saraksta mezglam ir gan nākamā, gan iepriekšējā mezgla adrese. Tas paātrinās elementu pievienošanas un noņemšanas procesu no saraksta, tāpēc laika sarežģītība tiks krasi samazināta.
Piemērs:
Ja mums ir atsevišķi saistīts saraksts:
1->2->3->4Ja esam 3 un ir nepieciešams to noņemt, tad 2 ir jāsaista ar 4 un no 3 2 nevar piekļūt, jo tas ir atsevišķi saistīts saraksts. Tātad saraksts ir jāšķērso vēlreiz, t.i., O(n), bet, ja mums ir divreiz saistīts saraksts, t.i.
1<->2<->3<->42 un 4 var piekļūt no 3, tāpēc O(1) 3 var noņemt.
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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);
Izvade
Value 5 was successfully added at key 4 Element found at key 4: 5 Element was successfully removed at the key 4Izveidojiet viktorīnu