Separate chaining hash table tutorial

separate chaining hash table implementation java and advantage of chained hash table over open addressing
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
ECE 250 Algorithms and Data Structures Chained hash Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering tables University of Waterloo Waterloo, Ontario, Canada © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Chained hash tables 2 Outline We have: – Discussed techniques for hashing – Discussed mapping down to a given range 0, ..., M – 1 Now we must deal with collisions – Numerous techniques exist – Containers in general • Specifically linked listsChained hash tables 3 Background First, a review: – We want to store objects in an array of size M – We want to quickly calculate the bin where we want to store the object • We came up with hash functions—hopefully Q(1) • Perfect hash functions (no collisions) are difficult to design – We will look at some schemes for dealing with collisionsChained hash tables 4 Implementation Consider associating each bin with a linked list: template class Type class Chained_hash_table private: int table_capacity; int table_size; Single_listType table; unsigned int hash( Type const & ); public: Chained_hash_table( int = 16 ); int count( Type const & ) const; void insert( Type const & ); int erase( Type const & ); // ... ;Chained hash tables 5 Implementation The constructor creates an array of n linked lists template class Type Chained_hash_table::Chained_hash_table( int n ): table_capacity( std::max( n, 1 ) ), table_size( 0 ), table( new Single_listTypetable_capacity ) // empty constructor Chained hash tables 6 Implementation The function hash will determine the bin of an object: template class Type int Chained_hash_table::hash( Type const &obj ) return hash_M( obj.hash(), capacity() ); Recall: – obj.hash() returns a 32-bit non-negative integer – unsigned int hash_M( obj, M ) returns a value in 0, …, M – 1Chained hash tables 7 Implementation Other functions mapped to corresponding linked list functions: template class Type void Chained_hash_table::insert( Type const &obj ) unsigned int bin = hash( obj ); if ( tablebin.count( obj ) == 0 ) tablebin.push_front( obj ); ++table_size; Chained hash tables 8 Implementation template class Type int Chained_hash_table::count( Type const &obj ) const return tablehash( obj ).count( obj ); Chained hash tables 9 Implementation template class Type int Chained_hash_table::erase( Type const &obj ) unsigned int bin = hash( obj ); if ( tablebin.erase( obj ) ) table_size; return 1; else return 0; Chained hash tables 10 Example As an example, let’s store hostnames and allow a fast look-up of the corresponding IP address – We will choose the bin based on the host name – Associated with the name will be the IP address – E.g., ("optimal", hash tables 11 Example We will store strings and the hash value of a string will be the last 3 bits of the first character in the host name – The hash of "optimal" is based on "o"Chained hash tables 12 Example The following is a list of the binary representation of each letter: – "a" is 1 and it cycles from there… a 01100001 n 01101110 b 01100010 o 01101111 c 01100011 p 01110000 d 01100100 q 01110001 e 01100101 r 01110010 f 01100110 s 01110011 g 01100111 t 01110100 h 01101000 u 01110101 i 01101001 v 01110110 j 01101010 w 01110111 k 01101011 x 01111000 l 01101100 y 01111001 m 01101101 z 01111010Chained hash tables 13 Example Our hash function is unsigned int hash( string const &str ) // the empty string "" is hashed to 0 if str.length() == 0 ) return 0; return str0 & 7; Chained hash tables 14 Example Starting win an array of 8 empty linked listsChained hash tables 15 Example The pair ("optimal", is entered into bin 01101111 = 7Chained hash tables 16 Example Similarly, as "c" hashes to 3 – The pair ("cheetah", is entered into bin 3Chained hash tables 17 Example The "w" in Wellington also hashes to 7 – ("wellington", is entered into bin 7Chained hash tables 18 Example Why did I use push_front from the linked list? – Do I have a choice? – A good heuristic is ―unless you know otherwise, data which has been accessed recently will be accessed again in the near future‖ – It is easiest to access data at the front of a linked list Heuristics include rules of thumb, educated guesses, and intuitionChained hash tables 19 Example Similarly we can insert the host names "augustin" and "lowpower"Chained hash tables 20 Example If we now wanted the IP address for "optimal", we would simply hash "optimal" to 7, walk through the linked list, and access when we access the node containing the relevant string