Difference between revisions of "Hashtable"

From Suhrid.net Wiki
Jump to navigationJump to search
Line 6: Line 6:
 
* However, this approach suffers from wasted space in the array - for those array indexes for which corresponding hash values are never generated.
 
* However, this approach suffers from wasted space in the array - for those array indexes for which corresponding hash values are never generated.
 
* Another problem is collisions - a single hash value can represent many keys.
 
* Another problem is collisions - a single hash value can represent many keys.
 +
* How to reduce the no. of collisions - increase the address space. Therefore, most hashing algorithms are a trade-off between space and time efficiency.
 
* To solve wasted space use : hashcode modulo arraysize.
 
* To solve wasted space use : hashcode modulo arraysize.
 
* To solve collisions use linkedlists to store key->value pairs for each hash value.
 
* To solve collisions use linkedlists to store key->value pairs for each hash value.
 +
* Also choosing prime numbers as the hash table size gives better results.
  
 
= Hash function properties =  
 
= Hash function properties =  

Revision as of 20:24, 17 December 2014

Hashing

  • Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection. It is a technique to narrow down the search space.
  • Hashing means using some function or algorithm to map object data to some representative integer value.
  • One basic approach. Calculate a hash for each key and store the hash value in an array index of the same value. Store the key, value pair in the same index positions in other arrays.
  • However, this approach suffers from wasted space in the array - for those array indexes for which corresponding hash values are never generated.
  • Another problem is collisions - a single hash value can represent many keys.
  • How to reduce the no. of collisions - increase the address space. Therefore, most hashing algorithms are a trade-off between space and time efficiency.
  • To solve wasted space use : hashcode modulo arraysize.
  • To solve collisions use linkedlists to store key->value pairs for each hash value.
  • Also choosing prime numbers as the hash table size gives better results.

Hash function properties

  • Be able to distribute the keys evenly over the range of positions in the array.
  • Distribute the keys over a larger range of values.
  • Combining the above two, Ideally a hash function should distribute hash codes evenly over the range of integers.