16

I am creating my own implementation to hash a table for education purposes.

What would be the best way to increase a hash table size?

I currently double the hash array size.

The hashing function I'm using is: key mod arraysize.

The problem with this is that if the keys are: 2, 4, 6, 8, then the array size will just keep increasing.

What is the best way of overcoming this issue? Is there a better way of increasing a hash table size? Would changing my hashing function help?

NOTE: My keys are all integers!

7
  • Are you writing your own implementation? Why? The best way is never resizing. Commented Mar 16, 2014 at 13:28
  • 3
    Yes. And sometimes resizing is needed, because you don't know how many elements will be added. I'm making my own implementation because it's for my CS course in university. Commented Mar 16, 2014 at 13:32
  • There is no "best" way. It's always going to be a compromise.
    – Hot Licks
    Commented Mar 16, 2014 at 13:35
  • (But as others have said, you need to properly hash your key.)
    – Hot Licks
    Commented Mar 16, 2014 at 13:35
  • @HotLicks Finding a way/implementation which will never need to resize (copy) the underlying array(s)/structure(s) is the best way. If one devises a way to grow the underlying structure with no need to copy data then new Map will be near perfect data storage solution Commented Mar 17, 2014 at 9:15

4 Answers 4

21

Hash tables often avoid this problem by making sure that the hash table size is a prime number. When you resize the table, double the size and then round up to the first prime number larger than that. Doing this avoids the clustering problems similar to what you describe.

Now, it does take a little bit of time to find the next prime number, but not a whole lot. When compared to the time involved in rehashing the hash table's contents, finding the next prime number takes almost no time at all. See Optimizing the wrong thing for a description.

1
4

OpenJDK uses powers of 2 for the capacity of a HashMap, which will lead to a lot of collisions if the keys are all multiples of a power of two. It prevents this by applying another hash function on top of the key's hashCode:

/**
 * Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions.
 * This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions
 * for hashCodes that do not differ in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
 static int hash(int h) {
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }
2
  • My keys are all integers so this may not be the best way to do it Commented Mar 16, 2014 at 13:33
  • @YahyaUddin It shouldn't make any difference if the keys are integers. They can still be rehashed in the same way.
    – fgb
    Commented Mar 16, 2014 at 13:37
4

If you try to implement your own hash table, here is some tips:

  1. Chose a prime number for table size if you use the mod for the hash function.
  2. Use Quadratic Probing to find the final position for collisions, h(x,i) = (Hash(x) + i*i) mod TableSize for the ith collision.
  3. Double the size to the nearest prime number when hash table get half full which you will merely never do if your collision function is ok for your input.

Here is an elegant implement for Quadratic Probing:

//find a position to set the key
int findPos( int key, YourHashTable h )
{
    int curPos;
    int collisionNum = 0;    
    curPos = key %  h.TableSize;
    //while find a collision
    while( h[curPos] != null && h[curPos] != key )
    {
        //f(i) = i*i = f(i-1) + 2*i -1
        curPos += 2 * ++collisionNum - 1;
        //do the mod only use - for efficiency
        if( curPos >= h.TableSize )
            curPos -= h.TableSize;
    }
    return curPos;
}
3

Hashing and hash functions are a complex topic, fortunately with lots of online resources.

It is not clear how you determine the array size in the first place.

In the Java HashMap implementation, the size of the underlying array is always a power of 2. This has the slight advantage that you don't need to compute the modulo, but can compute the array index as index = hashValue & (array.length-1) (which is equivalent to a modulo operation when array.length is a power of 2).

Additionally, the HashMap uses some "magic function" to reduce the number of hash collisions for the case that several hash values only differ by a constant factor, as in your example.

The actual size of the array is then determined by a "load factor". (You can even specify this as a constructor parameter of HashMap). When the number of array entries that are occupied exceeds loadFactor * array.length, then the length of the array will be doubled.

This load factor allows a certain trade-off: When the load factor is high (0.9 or so), then it will be more likely that hash collisions will occur. When it is low (0.3 or so), then hash collisions will be more unlikely, but there will be a lot of "wasted" space, because only few entries of the array will actually be occupied at any point in time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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