Topic: hashing

[ygfperson]

Just wondering... do the majority of database/search programs which hash search strings have some kind of method that checks to make sure that a previous entry didn't have the same hash value? or do they just think that the chances are astronomical enough for the risk of a collision to outweigh the extra cost of checking every entry?

[Major_Small]

well with some forms of hashing (or should I say a good algorithm) that's not really possible... for example, seperate chaining. (near the bottom)

[Perspective]

They just hash every entry to its position, if there is a collision they iterate by an offset AFAIK.

[Major_Small]

how could they possibly know where to look that up then? for example, if ABC hashes to position 3 and ABCD to position 4, how do they know where to find DEF (that was supposed to hash to 3, but is now in 5)?

that very quickly turns into a linear search...

[Perspective]

>>that very quickly turns into a linear search...

indeed. and thats what happens if your hash structure is more than %75 full. A good hash function along with a %75 capacity is what makes an optimal hash structure. But this is just the basics of hashing, im sure apps like Berkely DB have more sophisticated approaches to optimize things.