The question: let it be two data structures that are represented by hash tables $T_1,T_2$ with chaining ($T_1,T_2$ are arrays of linked lists), and hash functions h1,h2 accordingly. Suppose that the distribution of keys is sufficiently uniform by $h_1$ and $h_2$.

Is it true that you can merge/unify this two data structures into one data structure from that same type (hashing with chaining) with $n$ elements in $O(logn)$ at worst case?

The answer here is no, and I don't understand why. For example, I can define the new data structure with tables $T_1,T_2$ and functions $h_1,h_2$. it takes $O(1)$, and I can implement the known methods like that:

insertion(x)- insert to one of the tables with one of the functions- $O(1)$.

search(x)- search in both the tables. It's $O(1)$ expected.

delete(x)- search in both tables. If you found $x$, delete him- $O(1)$ expected.

where am I wrong here?

  • $\begingroup$ merge two hash tables : if you have a list for the non-zero entries of the array of lists, it would take $\approx T_1$ operations where $T_1$ is the number of elements of the smallest hash table. (merging two unsorted linked lists demands about $N_1$ operations). if you use cyclic linked lists instead of linked lists, you can do it in less operations (merging two unsorted cyclic linked lists asks for two modifications of pointers ) $\endgroup$ – reuns Jul 22 '15 at 12:28
  • $\begingroup$ ok, but I don't see why I need to merge these two lists. In my idea that I showed here, I just define the new data-structures with the two tablets in O(1). I also showed how can I implement the hash table known methods. isn't that an acceptable solution? $\endgroup$ – John Jul 23 '15 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.