Using one Hash Table to Improve another

Question

I'm studying for my final with questions given to us by our professor. I don't know how to answer this question:

Consider a hash-table T1 with n values where we have used f(k) = k%n for a hash-function and Chaining as our collision resolution method. Now, we want to insert these same values into a second hash-table T2 using the same hash-function, but apply Linear Probing (Single-Probing) to resolve collisions. How could you take advantage of T1 to build T2?

In which sense advantage? Do in you mean in terms of complexity? — Luca Marzi

Andrea Dusza Andrea Dusza · Accepted Answer · 2015-12-12T22:18:53

Note: My answer does not contain an exact solution, only ideas.

If I understand correctly, we already have a hash-table instance T1 with n values in it, and we want to use it to build T2, instead of normally building T2 from scratch.

Since we have n values for n buckets, we know that the hash table is going to be full.

My idea #1:

I would loop through all the buckets of T1. When I find a chain of values in the m-th bucket, I can know that all these values' hash is m, without having to call the hash function. So I can insert all of these values into the m-th, (m+1)-th, (m+2)-th ... buckets in T2, or if one is occupied then I skip that bucket.

The advantage is that we never have to call the hash function.

My idea #2:

I could see which buckets contain many and which buckets contain very few elements (like 1-2) in T1. I could use this information to determine an ideal order of insertion to minimize average access time. Unfortunately, I cannot think of a concrete method to determine an ideal order.

Example:

N = 10
values = 10,20,30,40,11,32,13,35,45,19

T1 always looks like this (order within chains does not matter):

0 -> {10,20,30,40}
1 -> {11}
2 -> {32}
3 -> {13}
4 -> {}
5 -> {35,45}
6 -> {}
7 -> {}
8 -> {}
9 -> {19}

Unlike T1, T2 can vary depending on the insertion order of values. One possible T2 where accessing each element takes a few steps:

0 -> {10} 0 off
1 -> {20} 1 off
2 -> {30} 2 off
3 -> {40} 3 off
4 -> {11} 3 off
5 -> {32} 3 off
6 -> {13} 3 off
7 -> {35} 2 off
8 -> {45} 3 off
9 -> {19} 0 off

Another possible T2 when some elements can be accessed immediately, but some elements are really off:

0 -> {10} 0 off
1 -> {11} 0 off
2 -> {32} 0 off
3 -> {13} 0 off
4 -> {20} 4 off
5 -> {35} 0 off
6 -> {45} 1 off
7 -> {30} 7 off
8 -> {40} 8 off
9 -> {19} 0 off

Using one Hash Table to Improve another

2 Answers

My idea #1:

My idea #2:

Example: