Hashes

‘Hash’, also known as ‘Hash Table’ or ‘Hash Map’, is a data structure that maps a ‘key’ to ‘value’ stored in an array. Hash map uses ‘Hash Function’ for this purpose. Hash function processes the ‘key’ and finds the ‘index’ of ‘value’ stored in an array of ‘buckets or slots’. Portion of an array where the data i.e. value is stored is called as ‘bucket’. Many such
Ideally a hash uses a key to point to a unique bucket. But it is possible that two or more keys are calculating indices to point the same bucket. This phenomenon is as ‘collision’.
 
 

‘Values’ are also called as ‘entries’. In the above given example, each bucket has only one entry. It is also possible that there are multiple entries per bucket, as follows:
 
 
 
Perfect hash function
A hash function is said to be ‘perfect hash function’ if it is used to create ‘perfect hash table’ which has no collision. If perfect hash function is used to create a perfect hash table, lookups for the value always takes a constant time. This will be irrespective of volume of data.
 
Load factor
Load factor of a hash function is calculated as follows:
Load factor = n/k;
Where,
 n = no. of entries
 k = no. of buckets
Time required for searching data in an array is directly proportional to load factor.
If load factor is higher, hash table becomes slower. If load factor is lower (less than 1 and approaching to 0), it means memory is being utilized properly. This is also not favorable condition.

Note: If the set of key-value pairs is fixed and known ahead of time (so insertions and deletions are not allowed), one may reduce the average lookup cost by a careful choice of the hash function, bucket table size, and internal data structures. In particular, one may be able to devise a hash function that is collision-free, or even perfect.
 
Uses of Hash table
1. Database indexing
2. Implementation of cache
3. Implementation of Sets Data Structure
4. Implementation in programming languages like Java, C/C++.
5. Unique data representation
6. String interning
7. Object representation
 
Hash table operations
1.  Adding key-value mapping
2. Deleting key-value mapping
3. Fetching value when key is given
 
Good functioning of a hash table
Good functioning of a hash table can be achieved by taking care of following things while implementing a hash table:
1. Collision resolution
2. Dynamic resizing

No comments :

Post a Comment