Hashtables ketjuttaminen kaksoislinkitetyillä listoilla
Edellytys - Hashing Johdanto Hashtable yksittäisten linkitettyjen luetteloiden avulla & Oman hash-taulukon toteuttaminen erillisellä ketjutuksella Javassa Hajautustaulukon toteuttaminen ketjuttamalla kaksoislinkitettyjen luetteloiden kautta on samanlaista kuin toteuttaminen Hashtable yksittäisten linkitettyjen luetteloiden avulla . Ainoa ero on, että jokaisella Linked List -solmulla on sekä seuraavan että edellisen solmun osoite. Tämä nopeuttaa elementtien lisäämistä ja poistamista luettelosta, joten aika monimutkaisuus vähenee huomattavasti.
Esimerkki:
Jos meillä on yksittäin linkitetty luettelo:
1->2->3->4Jos olemme 3:ssa ja se on poistettava, 2 on linkitettävä numeroon 4 ja 3:sta lähtien 2:ta ei voida käyttää, koska se on yksittäin linkitetty luettelo. Lista on siis ajettava uudelleen eli O(n), mutta jos meillä on kaksoislinkitetty lista ts.
1 <->2 <->3 <->42 & 4 pääsee käsiksi kohdasta 3, joten kohdassa O(1) 3 voidaan poistaa.
Alla on yllä olevan lähestymistavan toteutus:
C++ // C++ implementation of Hashtable // using doubly linked list #include using namespace std ; const int tablesize = 25 ; // declaration of node struct hash_node { int val key ; hash_node * next ; hash_node * prev ; }; // hashmap's declaration class HashMap { public : 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 ; } } // destructor ~ HashMap () { delete [] hashtable ; } // 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 ); bool 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 ) { cout < < 'Element found at key ' < < key < < ': ' ; cout < < entry -> val < < endl ; } entry = entry -> next ; } } if ( ! flag ) cout < < 'No Element found at key ' < < key < < endl ; } // 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 ) { cout < < 'Couldn't find any element at this key ' < < key < < endl ; 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 ; delete entry ; break ; } else { top [ hash_val ] = entry -> prev ; top [ hash_val ] -> next = NULL ; delete entry ; entry = top [ hash_val ]; } } entry = entry -> next ; } cout < < 'Element was successfully removed at the key ' < < key < < endl ; } // 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 ; } cout < < 'Value ' < < value < < ' was successfully' ' added at key ' < < key < < endl ; } }; // Driver Code int main () { HashMap hash ; hash . add ( 4 5 ); hash . find ( 4 ); hash . remove ( 4 ); return 0 ; }
Java // 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
Python3 # 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 )
C++ // 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 // 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 );
Lähtö
Value 5 was successfully added at key 4 Element found at key 4: 5 Element was successfully removed at the key 4Luo tietokilpailu
