Hashing a large range of integers to a smaller range

[mtwaha]

Hi all,

I'm new here and need a little help with hashing.

I have an array : buckets[5000];

Each bucket should be able to store multiple entries to handle collisions; there should be no limit on the number of entries each bucket can store.

I need to hash integers from range 0 - (2^32-1) in this bucket.

Can anyone help? I'm very confused as to how I can hash them.

Thanks,

Twaha.

[Matt Mahoney]

One simple method is to use an array of buckets that is a power of 2 like 2^12 = 4096. Then multiply by a 32 bit odd number picked at random and use the high bits as your hash index, like (x*3141592653u >> 20). If the element is occupied, then keep going to the next one until you find an empty spot.

[Piotr Tarsa]

Matt:
You've described hash array with open addressing. What author needs is: http://en.wikipedia.org/wiki/Hash_ta...arate_chaining Open addressing has a serious drawback: you can't remove anything from table with open addressing, you can only mark element as removed. Of course you can do removing by moving data to another fresh hash table, but doing that for every remove request would be too costly.

[Matt Mahoney]

You're right, but the OP didn't mention having to remove elements.