Designing Hash Tables Notes | EduRev

: Designing Hash Tables Notes | EduRev

 Page 1


1
Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Designing a hash table
? Hash function: establishing a key with an
indexed location in a hash table.
? Index = hash(key) % table_size;
? Resolve conflicts:
? Need to handle multiple keys that may be mapped to
the same index.
? Two representative solutions
? Linear probe open addressing (will discuss more later)
? Chaining with separate lists.
Separate Chaining
? Each table entry
stores a list of items
? So we don’t need to
worry about multiple
keys mapped to the
same entry.
Separate Chaining (contd.)
Type Declaration for
Separate Chaining
Hash Table
Separate Chaining (contd.) Separate Chaining (contd.)
Page 2


1
Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Designing a hash table
? Hash function: establishing a key with an
indexed location in a hash table.
? Index = hash(key) % table_size;
? Resolve conflicts:
? Need to handle multiple keys that may be mapped to
the same index.
? Two representative solutions
? Linear probe open addressing (will discuss more later)
? Chaining with separate lists.
Separate Chaining
? Each table entry
stores a list of items
? So we don’t need to
worry about multiple
keys mapped to the
same entry.
Separate Chaining (contd.)
Type Declaration for
Separate Chaining
Hash Table
Separate Chaining (contd.) Separate Chaining (contd.)
2
Separate Chaining (contd.) Separate Chaining (contd.)
Hash Tables Without Chaining
?Try to avoid buckets with separate lists
?How ? use Probing Hash Tables
?If collision occurs, try another cell in the hash
table.
?More formally, try cells h
0
(x), h
1
(x), h
2
(x),
h
3
(x)… in succession until a free cell is found.
?h
i
(x) = (hash(x) + f(i))
?And f(0) = 0
Insert(k,x)  // assume unique keys
1. index =  hash(key) % table_size;
2. if (table[index]== NULL)
table[index]=
new key_value_pair(key, x);
3. Else  {
• index++;
• index = index % table_size;
• goto 2;
}
Linear Probing: f(i) = i
? Search (key)
1. Index = hash(key) % table_size;
2. If (table[index]==NULL)
return –1; // Item not found
3. Else if (table[index].key == key) 
return index;
4. Else {
• Index ++;
• index = index % table_size;
• goto 2;
5. }
Linear Probing: Search
Linear Probing Example
Insert 89, 18, 49, 58, 69
Page 3


1
Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Designing a hash table
? Hash function: establishing a key with an
indexed location in a hash table.
? Index = hash(key) % table_size;
? Resolve conflicts:
? Need to handle multiple keys that may be mapped to
the same index.
? Two representative solutions
? Linear probe open addressing (will discuss more later)
? Chaining with separate lists.
Separate Chaining
? Each table entry
stores a list of items
? So we don’t need to
worry about multiple
keys mapped to the
same entry.
Separate Chaining (contd.)
Type Declaration for
Separate Chaining
Hash Table
Separate Chaining (contd.) Separate Chaining (contd.)
2
Separate Chaining (contd.) Separate Chaining (contd.)
Hash Tables Without Chaining
?Try to avoid buckets with separate lists
?How ? use Probing Hash Tables
?If collision occurs, try another cell in the hash
table.
?More formally, try cells h
0
(x), h
1
(x), h
2
(x),
h
3
(x)… in succession until a free cell is found.
?h
i
(x) = (hash(x) + f(i))
?And f(0) = 0
Insert(k,x)  // assume unique keys
1. index =  hash(key) % table_size;
2. if (table[index]== NULL)
table[index]=
new key_value_pair(key, x);
3. Else  {
• index++;
• index = index % table_size;
• goto 2;
}
Linear Probing: f(i) = i
? Search (key)
1. Index = hash(key) % table_size;
2. If (table[index]==NULL)
return –1; // Item not found
3. Else if (table[index].key == key) 
return index;
4. Else {
• Index ++;
• index = index % table_size;
• goto 2;
5. }
Linear Probing: Search
Linear Probing Example
Insert 89, 18, 49, 58, 69
3
Linear Probing: Delete
?Can be tricky ...
?How to maintain the consistency of the
hash table
?What is the simplest deletion strategy you
can think of?
Quadratic Probing
f(i) = i
2
Double Hashing
?f(i) = i*hash
2
(x)
?E.g.:  hash
2
(x) = 7 – (x % 7)
What if hash
2
(x) == 0 for some x?
Rehashing
? Hash Table may get full
? No more insertions possible
? Hash table may get too full
? Insertions, deletions, search take longer time
? Solution: Rehash
? Build another table that is twice as big and has a new hash
function
? Move all elements from smaller table to bigger table
? Cost of Rehashing = O(N)
? But happens only when table is close to full
? Close to full = table is X percent full, where X is a tunable
parameter
Rehashing Example
After Rehashing
Original Hash Table
After Inserting 23
Rehashing Implementation
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!