Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

So I have a quick question about the linear probing method of collision resolution in hash tables. So by definition a linear probing method would look like:

while (hashTable[hash] != null)
    hash = (hash(key) + step) % tableSize;

But in my case I know exactly what the table size will be, I know all the keys, so I'm wondering if this is a valid alternative implementation:

while (hashTable[hash] != null) {
    if (++hash == hashTable.length)
        hash = 0;

I'm sorry if I made it too confusing, but I'm a little confused myself... If you can't get what I'm asking, a simple explanation of how linear probing would be implemented would be very helpful, and ps: I'm working in java. Thanks alot

share|improve this question
The second one doesn't support step!=1. – Patrick Apr 13 '13 at 9:00

If you know all the keys, then you should use a perfect hash function; gperf can help with that. With a perfect hash, collisions needn't be handled, since they cannot happen.

This does not quite make sense: "hash = (hash(key) + step) % tableSize" Either you meant "hash = (hashFunction(key) + step) % tableSize", which looks like double hashing, or you mean "hash = (hash + step) % tableSize", which is indeed linear probing.

Your second code fragment makes sense, and is valid.

The trouble with linear probing, especially with step size of one, is it encourages clustering, so O(1) operations degenerate to O(n) operations even at moderate load factors.

share|improve this answer
Wow gperf is awesome, but is there a way to tell it how long you want to table to be? I need it to be at least 70% full – crazymao Apr 13 '13 at 23:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.