0
$\begingroup$

I have to proof this theorem: "An extendible hashing table always contains at least one bucket where only one pointer points to after an element is added". I made this proof, but I'm not completely sure if it's correct.

Note: The expand-operation on an extendible hashing table works by first doubling the pointer array. Then, the $2*i$-th and $2*i + 1$-th pointers should now point to the $i$-th bucket after expansion.

We deliver a proof by induction on the number of operations on a (initially) empty extendible hashing table.

Basis: The extendible hashing table contains 2 buckets with each one pointer that points to them when no operations are performed. The theorem holds.

Induction hypothesis: Suppose the theorem holds for n operations on an (initially) empty extendible hashing table.

Induction step: We are now going to proof that the theorem also holds for n + 1 operations on an initially empty extendible hashing table. Suppose the (n+1)th operation is an addition of a new element to the table. Now there are 2 possible cases:

First case: The element should be added to a bucket that's not full. The element can then simply be added to this bucket, and no changes occur to the hash-table that was created due to n operations. The theorem holds (induction).

Second case: The element should be added to a bucket that's full. When more than one pointer points to this bucket, it can be split up. If there's room in the bucket, than it can be placed and the theorem holds (induction) because none of the buckets where one pointer points to has been changed. When there's still no room in the bucket and it cannot be split up anymore, the pointerarray has to be doubled. Now this filled bucket has 2 pointers pointing to it and needs to be split to be able to add the element to this full bucket. But by splitting it, only one pointer points to the 2 new buckets, prooving the theorem.

QED

I'm not completely sure if this proof is valid. I'm not sure what I should do with the fact that when a bucket has been split (second case in the induction step) and there's still no room. Can I just say that it has to be split again an indeterminate amount of times, or is this not the way to go?

$\endgroup$
  • 1
    $\begingroup$ As it stands, your question boils down to "is my proof correct?", to which the only possible answers are "yes" or "no". Since most CS.SE users and visitors tend not to be decisional Turing machines, this is not particularly useful or interesting, not even to you. Could you point to a specific conceptual issue you're having trouble with? On a side note, I believe you should be more explicit in your definition of an "extendible hashing table", in particular it is not clear how the expansion operation works. $\endgroup$ – quicksort Jan 6 '17 at 12:51
  • $\begingroup$ Ah I see. Thank you. I will edit my question. $\endgroup$ – Pieter Verschaffelt Jan 6 '17 at 12:54

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.