Topic 8 - Hash Table without Linked Lists
In the previous topic, we saw how to create a hash table using the separate chaining, meaning using linked lists to store elements that have the same hash.
The only issue is the running time of adding and searching in the linked list.
Idea
The linked lists are used in case of collision.
To remove the linked list, we need to deal with the collision differently.
Consider the following:
You have an element \(x\).
You hash the element \(h = hash(x)\)
You check if the cell \(h\) is occupied or not.
If it is, you have a collision, then you check \(h + 1\).
You continue until one cell is empty.
It is called Probing Hash Tables.
More formally, we check a cell \(h_i(x)\) defined as:
where \(f\) is the collision resolution function and \(f(0) = 0\).
Of course, we can use different collision resolution function.
Important
The size of the table must be larger than with separate chaining tables.
Linear Probing
In linear probing, \(f\) is a linear function:
It’s very simple to understand, so we will take an example to illustrate it.
Example
Consider the hash function \(hash(x) = x\).
Consider a table of size 10.
Now we want to insert the following element \(\{89, 18, 49, 58, 69\}\).
For each element we calculate \(h_i(x) = (x + f(i))\mod 10)\).
We obtain the following result:
As long as the table is large enough we can always find an empty cell.
However, the running time can be quite large.
Activity
Why can the running time grow very quickly with linear probing?
This problem is accentuated with the primary clustering effect.
It occurs when block of occupied cells start forming.
It is possible to calculate the average number of probes required using a linear probing strategy and a random probing strategy.
Linear probing (insertion): \(\frac{1}{2}(1+ \frac{1}{(1-\gamma)^2})\).
Random probing (insertion): \(\frac{1}{\gamma}\ln \frac{1}{1-\gamma}\)
We can see that the number of prob before finding a cell to insert a new element grows quickly with the load factors:
Quadratic Probing
Linear probing is not optimal due to the primary clustering.
Quadratic probing eliminates this issue.
Obviously, the collision function is quadratic, usually \(f(i) = i^2\) is used.
Activity
Take the previous example and the new collision function and show what is the state of the table after each insertion.
Are we avoiding the primary clustering issue?
With quadratic probing there is no guarantee of finding an empty cell once the table gets more than half full!
This is because the at most half of the table can be used as alternative locations.
It leads us to the following.
Theorem
If quadratic probing is used, and the table size is prime, then a new element can always be inserted if the table is at least half empty.
Proof
Let \(TableSize\) be an odd prime greater than 3.
We show that:
\(\lceil TableSize/2\rceil\) alternative locations are all distinct.
Two of these locations are \(h(x)+i^2 \mod TableSize\) and \(h(x)+j^2 \mod TableSize\), where \(0\leq i, j\leq \lfloor TableSize/2 \rfloor\).
(Proof by contradiction):
Suppose that the locations are the same but \(i\neq j\), then:
Since \(TableSize\) is prime, either \((i-j)\) or \((i+j)\) is equal 0.
Since \(i\) and \(j\) are distinct, the first option is impossible.
Since \(0\leq i, j\leq \lfloor TableSize/2 \rfloor\), the second option is impossible.
If at most \(\lfloor TableSize / 2 \rfloor\) positions are taken, then an empty spot can always be found.
Implementation
The implementation is in the most part straightforward with the exception of the deletion.
If we remove an element that caused a collision, finding the elements that collided will fail.
We will consider each cell to have three states:
Active
Empty
Deleted
We will use a standard enumerated type:
enum EntryType {ACTIVE, EMPTY, DELETED};
So we define the interface of the class as:
Interface
1template <typename HashedObj>
2class HashTable
3{
4 public:
5 explicit HashTable( int size = 101 );
6
7 bool contains( const HashedObj & x ) const;
8 void makeEmpty( );
9 bool insert( const HashedObj & x );
10 bool insert( HashedObj && x );
11 bool remove( const HashedObj & x );
12
13 enum EntryType { ACTIVE, EMPTY, DELETED };
14
15 private:
16 struct HashEntry
17 {
18 HashedObj element;
19 EntryType info;
20
21 HashEntry( const HashedObj & e = HashedObj{ }, EntryType i = EMPTY )
22 : element{ e }, info{ i } { }
23
24 HashEntry( HashedObj && e, EntryType i = EMPTY )
25 : element{ std::move( e ) }, info{ i } { }
26 };
27
28 vector<HashEntry> array;
29 int currentSize;
30
31 bool isActive( int currentPos ) const;
32 int findPos( const HashedObj & x ) const;
33 void rehash( );
34 size_t myhash( const HashedObj & x ) const;
35};
Contains
The function contains require two other functions:
isActive: check if the element is “active”.
findPos: find the cell of the element (deal with the collision, etc.)
The functions contains and isActive are very easy to implement:
1template <typename HashedObj>
2bool HashTable<HashObj>::contains( const HashTableHashedObj & x ) const
3{
4 return isActive( findPos( x ) );
5}
6template <typename HashedObj>
7bool HashTable<HashObj>::isActive( int currentPos ) const
8 { return array[ currentPos ].info == ACTIVE; }
For findPos we need to proceed by steps:
Initialize the offset aka \(f(1)\).
Calculate the current position by calculating the hash of the element
While the position is not empty and it is not the element we’re looking for:
we had the offset to the hash.
we increment the offset, using the quadratic collision function \(f(i) = f(i-1) + 2*i -1\).
If the current position is greater than the size subtract the size.
Activity
Implement the function
findPos
.
Insert
To insert we do the following:
Find the position of the new element.
Check if it is already active.
Otherwise, put the element at the position and set it active
If the currentSize is greater than the size of the table rehash.
Activity
Implement the function
insert
.
Remove
Very similiar to insert:
Find the position of the element to delete.
If the element is not active, return false.
Otherwise, put the element state to
DELETE
.return true.
1template <typename HashedObj>
2bool HashTable<HashObj>::remove( const HashTableHashedObj & x )
3{
4 int currentPos = findPos( x );
5 if( !isActive( currentPos ) )
6 return false;
7
8 array[ currentPos ].info = DELETED;
9 return true;
10}
Double Hashing
The last collision resolution function is double hashing.
The idea is simple, we apply a second hashing function inside the hashing function.
A popular function is :
Note, that we apply the second hash function inside the probe function.
The second hash function needs to be selected carefully.
We need to ensure that all cells can be probed.
It requires that \(TableSize\) is prime.
After that a simple function as:
works well, if \(R\) is a prime number smaller than \(TableSize\).
Important
If double hashing is implemented correctly, then the expected number of probes is almost the same as for a random collision function.
Rehashing
If the table gets too full, the running time for the operations will increase.
A solution is
to build another table that is around twice the size (prime number)
scan the original hash table
compute the new hash value for each (nondeleted) element and insert it in the new table.
Example
Consider the following table.
The hash function is \(h(x) = x \mod 7\).
It is more than half full.
So we need to rehash the table.
We created a new table around twice the size (closest prime number).
Every value of the previous table have been inserted using the new hash function \(h(x) = x \mod 17\).