I'm having difficulty understanding how linear hashing works. I'd like an expert to try and clear up some of the difficulties I'm having understanding this.

I'm very familiar with the overall concept of hash tables, and have implemented them in both C and C++ multiple times, using various forms of collision resolution, so any expert who responds can assume I'll understand what you're talking about when it comes to how hash tables work.

What I'm having difficulty understanding is how Linear Hashing specifically works. I read the paper on it, and also a summary at

http://swig.stanford.edu/pub/summaries/database/linhash.html, but I don't understand exactly what they're saying.

What I've gotten so far about Linear Hashing:

When a collision happens, instead of doing a normal collision resolution method, (e.g. chaining or probing), a linear hash table actually changes the hash function dynamically, through something called a "split", which seems to modify the hash function so that instead of doing hashf(key) % N, you do hashf(key) % ((2^i) * N). Then, from what I can tell, you add another bucket at the end of the table, and move half of the ith bucket to the end of the table.

I really don't understand what this accomplishes, or how this works. So, can any expert explain to me how this works?

I seem to learn best by example, so let's take the following example. Suppose you have a hash table with 100 buckets, and you insert key K and it hashes to bucket 10. But bucket 10 is already full, so we have a collision. What precisely happens next?

http://citeseer.ist.psu.edu/cache/papers/cs/27834/http:zSzzSzwww.cs.ubc.cazSzlocalzSzreadingzSzproceedingszSzspe91-95zSzspezSz.zSzvol23zSzissue4zSzspe816.pdf/griswold93design.pdf