[Data Structure] Hash Table - 1 | Basic Operations & Chaining Collision Handling Technique

Hash Table

A hash table is data structure that stores unordered items by mapping (or hashing) each item to a location in an array (or vector).

Ex. Given an array with indices 0 ... 9 to store integers from 0 ... 5000, the modulo (remainder) operator can b usd to map 25 to index 5 (25 % 10 = 5), and 149 to index 9 (149 % 10 = 9). 

A hash table's main advantage is that searching, inserting, and removing an item may require only O(1).

 

In a hash table, an item's key is the unique value used to map to an index.

Each hash table array elements is called a bucket. 

A hash function computes a bucket index from the item's key. 

We can choose different variables for the key, but normally we choose a unique integer ID. 

 

 

---

Hash Table Operations

 

A common hash function uses the modulo opeartor %, which computes the integer remainder. 

A hash table's opeartions of insert, remove, and serach each use the hash function to determine an item's bucket. 

 

Ex 1. Inserting 113 into a hash table with 10 buckets first determines the bucket to be: 113 % 10 = 3

Ex 2. Given a hash table with 100 buckets and modulo hash function, HashInsert(table, item 334) will insert item 334 into bucket 34. (334 % 100 = 34)

Ex 3. Given a hash table with 50 buckets and modulo hash function, HashInsert(table, item 201) will insert item 201 into bucket 1. (201 % 50 = 1)

 

---

Collision Resolution Techniques

 

A collision occurs when an item being inserted into a hash table maps to the same bucket as an existing item in the hash table. 

Ex. For a hash function of key % 10, 55 would be inserted in bucket 5; later inserting 75 would yield a collision because 75 % 10 is also 5. 

Various techniques are used to handle collisions during insertions, such as chaining or open addressing. 

 

Chaining is a collision resolution technique where each bucekt has a list of items (so bucket 5's list would become 55, 75). 

Open addressing is a collision resolution technique where collisions are resolved by looking for an empty bucket elsewhere in the table (so 75 might be stored in bucket 6). 

There are more techniques for handling collisions. 

 

 

Chaining 

Chaining handles hash table collisions by using a list for each bucket, where each list may store multiple items that map to the same bucket. 

The insert operation first uses the item's key to determine the bucket, and then inserts the item in that bucket's list. 

Searching also first determines the bucket, and then seraches the bucket's list. Likewise for removes. 

 

We'll take a look into Python integration at the last. 

Let's consider there are three methods, HashInsert(), HashSearch(), and HashRemove() for Hash Class that implements Hash table.

And look at some examples after the operations. 

hash table with chaining

From valsTable above, 

1) After HashInsert(valsTable, item 20) 

Buckets 0's list: [60, 300, 40, 20]

2) After HashInsert(valsTable, item 23); HashInsert(valsTable, item 99)

Bucket 3's list: [13, 713, 23]

3) After HashRemove(valsTable, item 147)

Bucket 7's list: [67]

4) How many elements are compared for HashSearch(valsTable 62)?:    1

5) How many elements are compared for HashSearch(valsTable 40)?:    3

6) What does HashSearch(valsTable 168) return?:    null