Results 1 to 4 of 4

Thread: Hashing a large range of integers to a smaller range

  1. #1
    Member
    Join Date
    Apr 2011
    Location
    Pakistan
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Hashing a large range of integers to a smaller range

    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.

  2. #2
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    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.

  3. #3
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,474
    Thanks
    26
    Thanked 121 Times in 95 Posts
    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.
    Last edited by Piotr Tarsa; 11th April 2011 at 19:46.

  4. #4
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    You're right, but the OP didn't mention having to remove elements.

Similar Threads

  1. Replies: 7
    Last Post: 19th March 2011, 11:50
  2. How fast should be a range coder ?
    By Cyan in forum Data Compression
    Replies: 33
    Last Post: 16th November 2009, 17:02
  3. Delete smallest file if not smaller then Xpercentage
    By SvenBent in forum Data Compression
    Replies: 2
    Last Post: 6th January 2009, 00:41
  4. LZSS with a large dictionary
    By encode in forum Data Compression
    Replies: 31
    Last Post: 31st July 2008, 22:15
  5. Large text benchmark
    By Matt Mahoney in forum Forum Archive
    Replies: 39
    Last Post: 13th January 2008, 01:57

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •