How to calculate an array index from a hash

Question

I've seen examples on how to create a hash for a string. Here is one example in Java:

private int getHashCode(String text) {
    int hash = 7;
    for (int i = 0; i < text.length(); i++) {
        hash = hash * 31 + text.charAt(i);
    }

    return hash;
}

This of course can produce large numbers. If I am storing my strings in an array and I have only say 10 array items, how do I calculate the array index from the hash code? I can of course use a HashMap to do this, but I want to do this as part of learning how indexes are created from hash codes.

The hash function output is a number between 0...n, the hash itself is the index. However the hash should be transparent for you, you should not access the object by index.If you want a shorter array you should shrink the function codomain — yonutix
– yonutix, Commented Oct 8, 2015 at 13:50
The hash is not the index. The code above will generate very large values when the text is long. The hash is just one part of getting to the index. I'm still missing the part of going from the hash to the index. — Johann
– Johann, Commented Oct 8, 2015 at 13:54
You can go from the hash to the index if you are using a function with the codomain in the rage of your array. A hash function is a function f:String->[a, b] , in your case a= 0 , b = length-1. — yonutix
– yonutix, Commented Oct 8, 2015 at 13:57

Eran · Accepted Answer · 2015-10-08 14:17:00Z

10

You could use the remainder operator (%) to map your hash code to an index of an array :

int index = obj.getHashCode ("SomeString") % yourArray.length;

Of course, you should be able to handle clashes (i.e. situations in which two or more Strings are mapped to the same array index).

HashMap handles such potential clashes by storing in each index of the array an entry instance that can point to the next entry that was mapped to that same index (thus forming a linked list).

EDIT:

As was correctly commented below, the % operator wouldn't work for negative hash codes. As an alternative, you can use Math.floorMod (introduced in Java 8) instead :

int index = Math.floorMod (obj.getHashCode ("SomeString"), yourArray.length);

This is guaranteed to return a non-negative index, regardless of the sign of the hash code.

Or you can take the alternative used in HashMap implementation. If the length of your array is always a power of 2, you can use obj.getHashCode ("SomeString") & (yourArray.length - 1).

edited Oct 8, 2015 at 14:17

answered Oct 8, 2015 at 13:49

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

khelwood Over a year ago

Because Java's % operator is not sane, this won't work if you have a negative hashcode.

Eran Over a year ago

@khelwood Well, you can easily account for that (for example, by applying the % operator on the absolute value of the hash code).

davmac Over a year ago

It's worth noting that when changing the size of the array, the position at which each item should be stored may change.

Johann Over a year ago

@davmac That's a valid point. So Eran's simple solution implies that you cannot use it if you need to resize your array.

Eran Over a year ago

@AndroidDev HashMap uses a similar solution. When the array is resized, all the entries must be rehashed (i.e. the array index should be re-calculated for them before they can be added to the new array).

|

Rakesh Chaudhari · Accepted Answer · 2018-06-28 13:45:50Z

1

from java hashmap implementation

n - > Size of array

index = hashCode(key) & (n-1).

answered Jun 28, 2018 at 13:45

Rakesh Chaudhari

3,5461 gold badge32 silver badges26 bronze badges

1 Comment

maggu Over a year ago

Will work only if n is a power of 2

Collectives™ on Stack Overflow

How to calculate an array index from a hash

2 Answers 2

7 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related