Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
add comment

1 Answer

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
add comment

Your Answer

 
discard

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.