Hash Tables

A Hash Table is a table that uses a hash method to get the elements. A hash function will take an element and given a nearly unique value for it. Therefore it can be found in the array at or near a secific location rather than having linear searches for it.

A basic hash function is to take a numeric value and divide it modulary (return the remainder not the quotient). Now if you had a table that can hold ten items, then modular division by ten will set elements into their positions quickly. However if by chance two elements share a hash result then a colision results. The main study in hash tables is how to deal with these colisions.

Hash Table

A table that uses a hash function to position its elements

Colision

When two elements added to a hash table have the same position

Rehashing

recalculating the keys for resizing a hash table

Load Factor

number of elements in a table divided by the size of the table's array

Clustering

the tendancy for new elements to be hashed in the same location

Relatively Prime

the property that two number share no common factors except the number one

Twin Primes

two numbers that are both relatively prime and differ by two

Linear Hashing

A hashing algorithm that uses linear searches for colisions

Open Addressing

hashing that uses direct location in the table's array

Double Hashing

A hashing algorithm that uses two modular division to deal with colisions

Chain Hashing

A hash table that utilizes a linked list to deal with colisions

Linear Hashing

This is a simple algorithm for hashing and is best used with an array based table. The hash code is modular division of the size of the table. When adding an element just get the hash code. If the spot if empty put it in, otherwise just place is in the next available spot. If the end is reached then loop to the begining like with the circular queue. Removing an element is a linear search, but since it starts from where the element should be it is much quicker.

The problem with linear hashing is adding when removals a have been done. This can create situations in which the element may already be in the table. In that case the table must be seached from the hash position to the first empty space. If it already is in there then that it. If a space is reached then it is not in the table and it can then be added. Here is the general adding algorithm, followed by some example code.

Linear Hashing Adding Algorithm

1. Get the hash code.
2. Check the index of the hash value.
   1. If it is empty, search the table until a empty space is reached.
      1. If the element is found return.
      2. Else add the element at the hash value
   2. Else search the table for an empty space and place the value there.
      1. If the element was found before empty space return.
      2. Else add the element at the empty.

Rehashing

With various elements returing the same hash codes they can be mixed up in the table, this lessens the usefulness of the table and creates a new issue, resizing. When the table resizing all the keys have to recalculated and added to the table. This is relativly expensive given the tables quick performance, O(n). Since colisions occur more often as the table gets full a rehash is done when it is filled at a certain point. The value of how much is used by a table is called the load factor. Rehashing usually occurs with the load factor is 75%.

Double Hashing

Linear hashing is useful but it can often creates clustering. Clustering is when the hash fuction tends to send the elements in the same area of the table. To prevent this double hashing gets two hash codes. The first is the index of where the value show be. The second is a skip value. Instead of just searching till the next available spot or the element itself, search every hash2-th spot after it.

This skipping however can create problesm. What if there are not available spaces in the table on the skips? This is avoided by making sure that the two numbers for modular divsion are relatively prime. Two relativly prime numbers only have one for a common factor. This does not limit the choices to prime numbers alone. Take fourteen and fifteen. Fourteen's factors are one, two, seven, and fourteen. Fifteen's are one, three, five, and fifteen. The only common factor is one, so they are relativly prime.

An optoinal performance booster caculated by computer sciencetis Donald Knuth is to have the relavtively prime numbers be twin primes. Twin primes are relatively prime numbers whose difference are two. For example fivteen and seventeen. The factor's of fifteen are one, three, five, and fifteen. Seventeen's factors are one and seventeen. The greatest common factor is one, so they are relativly prime. Seventeen minus fifteen is two, so they are also twin primes.

Here's the tracing of the same hash calls with double hashing. Notice that the size of the table, seven, allows for the use of the twin prime five and seven.

int hash1(const string& s)         //notice constance pass by reference
{                                  //& returns the memory location
   return int(&s) % theTableSize;  //mod by table size gets position
}

int hash2(const string& s)         //only used in double hashing
{                                  //one is added so there is no skip of zero
   return 1 + (int(&2) % (theTableSize-2)) 
}

Chain Hashing

Performance

Each implementation of the hash table creates different performances. Donald Knuth is the computer scientist who figured all this stuff out. The average performance of a hash table is based on its implementation and is load factor, α These value are how fast a serach is for an element in a tabel that is not full and has had no removals.

Prev -- Back to Portal -- Next