Hash Map (Hash Table)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Reference: Wiki PrincetonAlgorithm

What is Hash Table

Hash table (hash map) is a data structure used to implement an associative array, a structure that can map keys to values.
A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

hash function: transform the search key into an array index

What is Hash Collisions

Different keys that are assigned by the hash function to the same bucket.

Perfect Hashing

A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions.

Perfect hashing allows for constant time lookups in the worst case. This is in contrast to most chaining and open addressing methods, where the time for lookup is low on average, but may be very large, O(n), for some sets of keys.

Load Factor

A critical statistic for a hash table.

Load factor = n / k

where:
n = number of entries
k = number of buckets

high load factor: hash table becomes slower, and it may even fail to work (depending on the method used).
low load factor: considering the proportion of unused areas in the hash table. This results in wasted memory.

Also, one should examine the variance of number of entries per bucket. For example, two tables both have 1000 entries and 1000 buckets; one has exactly one entry in each bucket, the other has all entries in the same bucket. Clearly the hashing is not working in the second one.

Hash Functions

3 primary requirements in implementing a good hash function for a given data type:

It should be deterministic - equal keys must produce the same hash value.
It should be efficient to compute.
It should uniformly distribute the keys.

Suppose we have an array that can hold M key-value pairs, then we need a function that can transform any given key into an index into that array.

Positive Integers

modular hashing

Choose the array size M to be prime, and, for any positive integer key k, compute the remainder when dividing k by M. (k % M)

Floating-Point Numbers

Simple but defective way:
If the keys are real numbers between 0 and 1, we might just multiply by M and round off to the nearest integer to get an index between 0 and M-1.
This approach is defective because it gives more weight to the most significant bits of the keys; the least significant bits play no role.
Better way (adopted by Java):
Use modular hashing on the binary representation of the key.

String

Simply treat them as huge integers.

R is prime number, Java uses 31. Calculate each bit of the array.

int hash = 0;
for (int i = 0; i < s.length(); i++)
hash = (R * hash + s.charAt(i)) % M;

Also, we can use MD5 to randomize input keys

int hashFunc(String key) {
return md5(key) % HASH_TABLE_SIZE;
}

APR hash function uses magic number 33. Similar with the first method.

int hashFunc(String key) {
int sum = 0;
for (int i = 0; i < key.length(); i++) {
sum = sum * 33 + (int) key.charAt(i);
sum = sum % HASH_TABLE_SIZE;
}
return sum;
}

Compound Keys

We can follow the ways of processing string.

For example, we use a tuple as key (element1, element2, element3)

int hash = (((element1 * R + element2) % M) * R + element3) % M;

By Using hashCode() in Java

private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}