In the realm of bytes and data’s might,
Where algorithms dance and code takes flight,
Behold the Hash Table, a structure so grand,
A symphony of keys conducted by skilled hands.
In the kingdom of structures, two minds intertwine,
Benji Tusk and Eyal Schachter, their brilliance does shine.
Together they crafted, with knowledge profound,
A Homework on Hash Tables, in wisdom abound.
Benji, a maestro, with algorithms in his quill,
Notes of efficiency, his code does distill.
Eyal, a virtuoso, with logic so clear,
In the art of hashing, he steers without fear.
Hash functions hum like a melody sweet,
Mapping keys to slots, a dance discreet.
Collisions harmonize, as resolutions unfold,
In the vast memory, a tale to be told.
Chaining or probing, methods untold,
In the landscape of data, adventures unfold.
Linked lists entwine, or clusters disband,
As the Hash Table weaves its intricate strand.
So let the code compile, let logic prevail,
As Benji and Eyal set their knowledge to sail.
In this world of data, where structures align,
May Hash Tables guide you, like stars that entwine.
Eyal Schachter (209792266) and Benji Tusk (650282680)
Question 1
Part A
The table looks like the following after the insertions:
Part B
The load factor is α=1112
Part C
Let p(k) be the number of probes required to search for k in the table. p(617)=1 p(78)=2 p(47)=1 p(90)=1 p(115)=1 p(18)=1 p(8)=1 p(41)=2 p(64)=1 p(76)=1 p(65)=2 p(54)=3
k∑keys in tablep(k)=17
The average number of probes required is 1217=1.42
Part D
The expected runtime = Θ(1+2α)
In our case, this is 1+11⋅212=1117=1.54
The ratio is 1217÷1117=1112=1.09
Question 2
Disproof by Pigeonhole Principle:
Since the domain of h is larger than its range, a one to one function cannot exist.
Question 3
Function
Best
Average
Worst
Insertion
O(1)
O(1+logα)
O(logn)
Successful Search
O(1)
O(1+logα)
O(logn)
Failed Search
O(1)
O(1+logα)
O(logn)
Deletion
O(1)
O(1+logα)
O(logn)
Insertion Average Case
We will calculate the average runtime for inserting into a hash table with n elements. E[insert(x)]=O(1+log∣treeh(kn)∣)
We include O(1) for applying the hash function.
Based on SUHA, ∣treeh(kn)∣=mn=α
Therefore, E[insert(x)]=O(1+log∣treeh(kn)∣)=O(1+logα)
Failed Search Average Case
A failed search has the same runtime complexity as insert.
This is because in order to fail a search, we must completely follow the ‘insertion path’ that the given key may have taken. Thus, Failed Search = O(insert)=O(1+log(α))
Successful Search Average Case
By definition of average case: E[search(x)]=n1⋅∑i=1nsearch(xi)
Now we calculate the time to search for element xi:
The process is to find the tree in the hash table at key h(ki), then perform AVL-Search(). AVL-Search=O(log(∣treeh(ki)∣))
Based on SUHA, ∣treeh(ki)∣=mn=α
So, AVL-Search=O(log(α))
[For simplicity’s sake, we will ignore Big O™ and treat search(xi) as log(α)]
We add +1 to the final runtime for accessing the hash table, giving us a runtime of O(1+log(α)). Kew Ee Dee.
Deletion Average Case
A Deletion has the same runtime complexity as a successful search.
This is because in order to delete, we must find the element that the given key points to.
Internally, the algorithm is parallel to AVL-Search.
Thus, Deletion = O(SuccessfulSearch)=O(1+log(α))
Insertion Best Case
The best case is where ∣treeh(kn)∣=0,
The Runtime Complexity is O(1+Create-Tree)=O(1).
Failed Search Best Case
The best case is where ∣treeh(kn)∣=0.
The Runtime Complexity is O(1+Create-Tree)=O(1).
Successful Search Best Case
The best case is where ∣treeh(kn)∣=1.
The Runtime Complexity is O(1) because we only need to access the hash table and perform one comparison, which is O(1).
Deletion Best Case
The best case is where ∣treeh(k)∣=1.
The Runtime Complexity is O(1) because we only need to access the hash table and perform one comparison, which is O(1).
Insertion Worst Case
The worst case is where ∣treeh(k)∣=n.
We need to insert into the AVL tree of size n (height Θ(logn)).
Since AVL-Insert is O(logn), the worst case is O(logn).
Failed Search Worst Case
The worst case is where ∣treeh(k)∣=n.
We need to search the AVL tree of size n (height Θ(logn)).
Since AVL-Search is O(logn), the worst case is O(logn).
Successful Search Worst Case
The worst case is where ∣treeh(k)∣=n.
We need to search the AVL tree of size n (height Θ(logn)).
Since AVL-Search is O(logn), the worst case is O(logn).
Deletion Worst Case
The worst case is where ∣treeh(k)∣=n.
We need to delete from the AVL tree of size n (height Θ(logn)).
Since AVL-Delete is O(logn), the worst case is O(logn).
The solution is to calculate the square of the key, instead of taking the square root of the concatenated bits. While the concatenated bits do not equal the square of the key, we have not yet found the value.
Part B
The size of the index is p bits, because the hash table has 2p entries. b is the size of the key, therefore, k2is 2b bits long.
The following calculations are referring to the size (in bits), not the literal value. 2b=l+p+r l+r=2b−p 2r=2b−p (because l=r)
We save space when 2r<b 2b−p<b b<p ∴ We save memory space when b<p.
Question 5
Linear Probing
Index
Content
Probes
0
15
2
1
1
1
2
18
1
3
34
2
4
68
1
5
51
3
6
7
39
1
8
72
1
9
10
122
1
11
43
1
12
26
3
13
13
1
14
14
1
15
31
1
Average number of probes is 1420=1.428
The expected runtime = Θ(α1ln(1−α1))
In our case, this is 1416ln(216)=1.584
The ratio is 1.428÷1.584=0.901
Quadratic Probing
Index
Content
Probes
0
15
2
1
1
1
2
18
1
3
34
2
4
68
1
5
6
51
3
7
39
1
8
72
1
9
26
6
10
122
1
11
43
1
12
13
13
1
14
14
1
15
31
1
Average number of probes is 1423=1.643
The expected runtime = Θ(α1ln(1−α1))
In our case, this is 1416ln(216)=1.584
The ratio is 1.643÷1.584=1416=1.037
Double Hashing
Index
Content
Probes
0
15
2
1
1
1
2
18
1
3
51
1
4
68
1
5
6
26
1
7
34
2
8
72
1
9
43
2
10
122
1
11
39
3
12
13
13
1
14
14
1
15
31
1
Average number of probes is 1419=1.357
The expected runtime = Θ(α1ln(1−α1))
In our case, this is 1416ln(216)=1.584
The ratio is 1.357÷1.584=0.856
Question 6
Assume that the keys k1,k2,…,kn were inserted in order, with no deletions.
The time to search for a key, therefore, will be the same as the time it took to insert it.
We will calculate time based on number of probes required.
For any given key k, let Xk be the number of probes to insert kk into T.
The insert algorithm will repeatedly apply the hash function until it finds an empty cell to insert into, comparing against the keys already in the table.
Because we assume SUHA, the result of each iteration of the hash is independent, and could be any index in the table.
Because Xk distributes geometrically, E[Xk]=p1=(mm−1)k−11=(mm−1)1−k
For a random l, where i≤l≤j, and 1≤i<j≤n,
E[search(kl)]=j−i1k=i∑jE[search(kk)]=j−i1k=i∑j(mm−1)1−k=j−i1k=1−j∑1−i(mm−1)t=j−i1(mm−1)−1(mm−1)1−j((mm−1)j−i−1)(sum of a geometric sequence)=j−i1(mm−1−mm1)((mm−1)1−j+j−i−(mm−1)1−j)=j−i1⋅−1m((mm−1)1−i−(mm−1)1−j)=i−jm((m−1m)i−1−(m−1m)j−1)
Therefore, the expected runtime of search for a key between i and j is: