CS211-Algorithms & Data

Structures
Taibah University

Dr. Sameer M. Alrehaili

1
Hash tables

2
What are hash tables?

● A hash table (hash map) is a data ● h(k) maps each key k to the index where
structure associated with a function (hash the associated value will be stored.
function) ● Then we could find the item with the key k
● A hash table allow us very fast retrieval of by arr[h(k)] .
data regardless the size of data and the ● It Would be easiest if we could just make
position of the targeted item. the data array big enough to hold all the
● The idea is to put each item in an easily keys.
determined location, so we never need to
search for it. For example, put an item in a
location that can be accessed using its
value.
● Hash tables are widely used in database Add O(1)
indexing, cashing, compilers, error
Delete O(1)
checking, password authentication,
search engines, and more. Lookup(Get) O(1)
● Hash tables are achieved by a hash
function h(k).

3
Hash tables

Consider the following 1d array.

● The cost of finding an item in this array using sequential search is O(n).
● For very large size array, this could take long time.
● The time of finding an item by its value is dependant on the position of the
item and the size of the array.
● The time of finding an item by its index is very quick and independent of the
size of the array and of its position in the array

h(k) = k mod size of array

arr 21 30 20 16 29 26 14 12 11 28 24

0 1 2 3 4 5 6 7 8 9 10

4
Apply hashing for an array

arr 21 30 20 16 29 26 14 12 11 28 24

0 1 2 3 4 5 6 7 8 9 10
h(21) = value Mod size of array
Index of 21 = 21 Mod 11 = 10
arr 21

0 1 2 3 4 5 6 7 8 9 10

h(30) = 30 Mod 11 = 8
arr 30 21

0 1 2 3 4 5 6 7 8 9 10
h(24) = 24 Mod 11 = 2
h(28) = 28 Mod 11 = 6

arr 11 12 24 14 26 16 28 29 30 20 21

0 1 2 3 4 5 6 7 8 9 10 5
Example: finding an element in a large 1d array

● Consider the following 1d array.

h(k) = sum ASCII codes of k Mod size of array

h(Mia) = 77+105+97 = 279 Mod 11 = 4

h(Leo) = 76+101+111 = 288 Mod 11 = 2

arr Jan Tim Mia Sam Leo Ted Bea Lou Ada Max Zoe

0 1 2 3 4 5 6 7 8 9 10 6
Collisions Resolution

● Collisions occurs when a hash function generates the same index for two or
more items. h(k1)=h(k2) and k1 != k2
● A location in a hash table is full while another item need to be inserted in the
same location.
○ Open addressing
■ Linear Probing : is a strategy for resolving collisions
● Apply linear search for the next empty location in the hash table
● Put the new item in it
● If you reach the end of the hashtable go back to the front
■ Linear probing result sparse array and this known as primary clustering
● Plus 3 rehash
15 1 3 4 5
● Quadratic probing
● Double hashing: apply a secondary hash function to tell us how many slots to jump
to look for an empty slot.
○ Closed addressing
■ Chaining: make each item of the hash table point to a linked list of items that have the
same index.

7
Collisions resolution by probing

1. i = h(k)
2. If i > n then i=0
3. If the slot of i is occupied
3.1. i = i+1
3.2. Go to 2
4. End if
5. T[i]=k

8
Collision resolution by chaining

1. i=h(k)
2. Put all elements that hash to the same slot in a linked list
3. Slot i has a pointer to the head of the list of all stored elements that hash to i
4. If there no such elements
○ Slot i contains none
5. Each slot T[i] in the hash table has a linked list ot all keys whose hash value
is i

Example, h(k1) =h(k4) and h(k5) =h(k2)=h(k7)

k1 k4

k5 k2 k7

9
Examples of using linear probing

● Question: Use linear probing to insert the following items into a hash table of
size 6 using the hash function H(key) = key mod 5. Show the result of hash
table after each insertion.

Items = 15,14, 12, 20, 11

#step Hashing Hash table

#1 H(15) = 15 mod 5 = 0 [15, , , , , ]

#2 H(14) = 14 mod 5 = 4 [15, , , ,14, ]

#3 H(12) = 12 mod 5 = 2 [15, ,12 , ,14, ]

#4 H(20) = 20 mod 5 = 0 [15, 20, 12, ,14, ]

#5 H(11) = 11 mod 5 = 1 [15, 20, 12,11 ,14, ]

10
Examples of using chaining

● Question: Use closed addressing technique(chaining) to insert the following

Items = 15,14, 12, 20, 11,10,19

0 15 20 10

1 11

2 12
3

4 14 19
5

11
Hash tables are good in some situations

● When speedy insertion, deletion, and lookup is the priority in your algorithm,
then hash table performs them in constant time.
● In situations where you have enormous amounts of data from which you
would like to quickly search and retrieve information.

12
Summary

● In hash table, the index is calculated using the value

13