Hash Table

Motivation

Storing data in no order with an array means searching will be slow in linear time. Storing data in a binary search tree means searching can be done in logaritmic time via binary search.

How an we get constant time for all core operations? A hash table is a data structure aiming for average (expected) constant-time operations.

Hash Table

Fundamental Idea: map each key (entry) to a position (an array index) based on the key itself.

key > hash function... calculating index... > index

Example: when I give "cat", it gives 1, and "dam" gives 9. I now can use the index to insert each element or find the element. The cost of insertion and sort will be the cost of running this function.

• When we access an entry based on its key (associative retrieval), not its location (e.g., no need to search for the key in a tree).

Set/Map ADT can be efficiently implemented using a hash table

• has/get(key): compute getIndex(key) and check the corresponding array element for an enrty with a matching key.
• insert/put(key, value): compute getIndex(key), add or update the corresponding array element with the entry for the matching key.
• remove(key): compute getIndex(key), find the entry with a matching key in the corresponding array colelction.

Hash Function

Imagine the array where we store the key has the capacity M. The job of the mystery function is to map "key" to "indices" in the range [0, M-1].

• This process of mapping keys to array indices is called hashing
  • Hashing is common in data structures, databases (retrieval or assigning IDs), cryptography (encryption).

The steps has function performs:

1. Converts a key to an integer (hash code) in a range like [0, N).
   • There are many ways to represent anything with an integer.
   • There are good and bad conversions.
2. Map the hash code into a smaller range [0, M-1] where M << N.

A good hash function has these properties:

• uniform: maps keys to array indices as evenly as possible (equal likelyhood of generating each index value). If you had a table with N positions, you want each position to be as likely to be picked.
  • If a hash function only results in even numbers, then the odd numbers are never filled.
• deterministic: a given key is always mapped to the same index so that we can still look it up.
• cheap: a constant-time operation that is simple and fast to compute.

Java's hashCode()

There are many ways to approach the hash function. However, we are only interested in implementing hash tables.

A hash table is a data structure that organizes data using hash functions to support quick insertion/removal and search.

Responsibility of the hash function is divided between the element annd the data structure.

• Key-->Integer is done by the element (key) itself
  • Every "type" inherits the hashCode() method from the Object class. This method returns the hash code value. Remember to override the hashCode method when making custom types.
• Reducing (compressing) the hash code to the rannge of the array indices is part of the geeral hash table implementation (you have to do it)
  • Once we have the hash code for a given key, map that value to array indices.

// compress
index = key.hashCode() % M;

Java has a utility called Objects that you can use to craft a hash code out of the other hash codes.

• When you override equals you should always override hashCode.

Collisions

A collision occurs when two different keys x and y map to the same positon (array index) in the hash table. getIndex(x) == getIndex().

• This will be inevitable because the set of possible keys is vastly larger than the capacity of the hash table.

Two main collision reduction techniques:

• Open addressing: locate the next available (open) position
• Chaining: store multiple entries in each position.

Chaining

Store all colliding elements in an auxiliary data structure like a linked list.

• Every position is more like a bucket. A data structure in each position.
• Each element will hold a reference to the next element- think of a linked list.
• Better than a binary search tree because the subset is tiny.

Performance In chaining, operations run proportional to the number of keys in the given chain.

• The best case is that the number of elements inserted is smaller than the capacity fo the tabble. We have no collision so the performance for insert, remove, and search are O(1).

• The worst case is that the keys all get mapped to the same bucket: O(n).

• The average case is under the assumption of uniform hashing. Every bucket is expected to be the size N/M, where N is the number of items sorted in the hash table and M is its size (number of array indies/table slots). Notice this ratio is the load factor. Performance is then $O(\alpha)$.

  • If $\alpha$ is a small constant (<1), we get constant runtime operations.
  • Performance also depends on the choice of auxiliary data structures.

  In Java, the HashMap is implemented using chaining with a linked list auxiliary data structuer. It maintains $\alpha <= 0.75$. When the number of elements reaches a certain limit, it switches to a BST (if elements are comparable).

  Open Addressing

  Open addressing allows elements to overflow out of their target into other "open" (unoccupied) positions.

  The process of locating an open location in the hash table is called probing. There are many techniques.

  • Linear probing: if the calculated index is occupied, increment the index by a constant step size. Keep incremeneting from the index until we find an empty position to insert the key.

int index = getIndex(key); // if table[index] is occupied, then 
for(int i = 0; i < M; i++) { 
	index = (getIndex(key) + i) % M; 
	// stop the loop when table[index] is available! 
} 
// if we get here and haven't inserted the key, the table is full!

Linear Probing

If a positionis occupied by another item, increment the index by a constant step size until we find an empty position.

However, removing an item may lead to not being able to find previously inserted items that collided with it.

• Because if we delete an item, then we might prematurely stop a search for another one and incorrectly conclue that the target is in the table.

The solution is lazy deletion flag the item as deleted (instead of deleting it). Also known as placing a tombstone over the deleted item.

• Storing tombstones forces the search algorithm to keep looking until either the taret is found or a free cell is located.

• Future inserts can overwrite tombstones, but lookups treat them as collisons.

  • However, you should not replace tombstone with a new item because if the item was already inserted, you must first follow the probe sequence to ensure that the new item is no already present in the table. So, you must never write over tombstones or perform a search before insertion.

• Tombstones waste space and reduce search efficiency.

  • If the table is full of tombstones, then searching will be O(n). This phenomenon is called contamination. You must rehash to recover.

Rehashing

The likelihood of a collision is proportional to how full the table is.

When the hash table is sufficiently full, a larger table should be allocated, and the entries should be reinserted.

• Copying the values from the original collection will not work because the table size affects the hashing procedure. A key inserted at index x in the smaller table will not be mapped to the same index at the larger table. The search operation may not wrk.

Rehashing* involves

1. Allocating a new hash table (with a larger prime number).
2. Reinsert each old table entry (that has not been deleted) into the new hash table.

Load Factor

$\alpha$ the measure that indicates how "full" a table is. alpha = number of filled cells / table capacity.

• Filled cells includes tombstones.

The lower the load factor, the better the performance because there is less chance of a collision.

When the load factor reaches a given threshold, rehashing kicks in. Increasing the capacity reduces the load factor.

• The threshold is configurable as it offers a tradeoff between time and space costs. Lower load factors means fewer collisions but more memory overhead.

Table Size

When choosing a table size, a prime number larger than the desired table size is recommended. This is because we compute the index as:

index = key.hashCode() % M

• Assume the value returned from key.hashCode() is K. Then for every possible K that shares a common factor withM, the ke wil lbe hashed to multiple positions of thsi factor. Therefore, choosing M to have a few factors by being a prime number minimizes collsions.

Furthermore, doubling the table capacity gets you an even number. If M is an even number, then key.hashCode() will be even, and index will also be even.This bias means half the table will be used..

To implement, it is common to tabuilate primes and use it as a look-up table topick the table size. E.g.,

int primes[] = {2, 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437,102877, 205759, 411527, 823117, 1646237,3292489, 6584983, 13169977};

When it reaches the max P_k, then the algorirthm switches to doubling the capacity for the following rehashes.

Analysis

No collision: insert/remove and search performace is O(1). This is the best-case scenario.

The worst-case scenario is when probing sequence goes over every occupied position. This leads to O(n).

Given an open-address hash table with a load factor $\alpha$, the expected number of probes in an unsuccessful search is at most: 1/(1-alpha).

Ultimately, since alpha < 1 in open-address hash tables, the average (expected) performanceis constant time under the assumption of uniform hashing.

Clustering

Clustering effect of linear probing happens because an existing clusert acts as a "net" and catches many of the new keys, which will be appended to the chain and exacerbate the problem. As a new collision expands cluster by one element, it increases the length of the searhc chain for each element. As the chain gets longerg and longer, more positions must be scanned during insert/search. This is called primary clustering.

Quadratic Probing

Instead of constant size strides, the strides are increments in a quadratic series. The next value is calculated as

int index = getIndex(key);
// if table[index] is occupied then,
for (int i = 0; i < M; i++) {
	index  (getIndex(key) + i*i) % M;
	// stop loop when table[index] is available. 
}

A potential issue is that a item can't be inserted even when the table is not full.

This can still cause the secondary clustering effect. If a key is mapped tot he same index as another key, the second key's prob sequence will follow the first one's footsteps. If this happens repeatdly, chains will still form that cause performance to degrade.

Other Probing Strategy

Double hashing is where the interval between probes is computed by a second hash function.

int index = getIndex(key);
// if table[index] is occupied, then 
for(int i = 0; i < M; i++) { 
	index = (getIndex(key) + hash(key) * i) % M; 
	// stop the loop when table[index] is available! 
}

• Second hash codes typically use the first one to produce another hash value.
• The advantage of double hashing is that th pprobe sequence depends on the key rather than a fixed pattern so it avoids both primary and secondary clustering.

Questions

Can I use another hash table as the auxilliary data structure?

• There is a circular dependance. You would need a different hash function so that there is no infiniet loop. (looking into cuckoo hashing)