Difference between revisions of "Hashtable"
From Suhrid.net Wiki
Jump to navigationJump to search| Line 1: | Line 1: | ||
| + | = 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 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. | * Hashing means using some function or algorithm to map object data to some representative integer value. | ||
| Line 6: | Line 8: | ||
* 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. | ||
| + | |||
| + | = 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. | ||
Revision as of 01:55, 22 October 2012
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.
- To solve wasted space use : hashcode modulo arraysize.
- To solve collisions use linkedlists to store key->value pairs for each hash value.
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.
