1

I am looking for a hash function for an integer array containing about 17 integers each. There are about 1000 items in the HashMap and I want the computation to be as fast as possible.

I am now kind of confused by so many hash functions to choose and I notice that most of them are designed for strings with different characters. So is there a hash function designed for strings with only numbers and quick to run?

Thanks for your patience!

RickyGao
  • 11
  • 2
  • you mean hashmap inside a hashmap? or a hashmap that accepts string as a key and integer as a value? – Joseph118 Nov 26 '14 at 03:18
  • Sorry for the ambiguous description. Actually I just want to query an object by key in a hashmap. And the hashmap accepts an array of integer as the key. – RickyGao Nov 26 '14 at 03:38
  • Related: http://stackoverflow.com/questions/1058149/using-a-byte-array-as-hashmap-key-java http://stackoverflow.com/questions/2627889/java-hashmap-with-int-array?rq=1 – Thilo Nov 26 '14 at 04:04
  • it seems really odd that you'd want an int array as a key in a Map. – MeBigFatGuy Nov 26 '14 at 06:00

2 Answers2

1

You did not specify any requirements (except speed of calculation), but take a look at java.util.Arrays#hashCode. It should be fast, too, just iterating once over the array and combining the elements in an int calculation.

Returns a hash code based on the contents of the specified array. For any two non-null int arrays a and b such that Arrays.equals(a, b), it is also the case that Arrays.hashCode(a) == Arrays.hashCode(b).

The value returned by this method is the same value that would be obtained by invoking the hashCode method on a List containing a sequence of Integer instances representing the elements of a in the same order. If a is null, this method returns 0.

And the hashmap accepts an array of integer as the key.

Actually, no!

You could technically use int[] as a key in a HashMap in Java (you can use any kind of Object), but that won't work well, as arrays don't define a useful hashCode method (or a useful equals method). So the key will use object identity. Two arrays with identical content will be considered to be different from each-other.

You could use List<Integer>, which does implement hashCode and equals. But keep in mind that you must not mutate the list after setting it as a key. That would break the hashtable.

Community
  • 1
  • 1
Thilo
  • 257,207
  • 101
  • 511
  • 656
  • Thanks~ I have looked at them and I just want to know more about the computation of the hashcode. Basically, I want as few hashcode collisions as possible. As there are less than 1000 items, I think it should generate almost no collison. And I also want the computation to be fast as it will be implemented for a lot of time. Thanks again for your effort~ – RickyGao Nov 26 '14 at 03:43
  • 1
    The computation of the hash code is defined at http://docs.oracle.com/javase/6/docs/api/java/util/List.html#hashCode%28%29. Quite simple, just additions and multiplication with 31. – Thilo Nov 26 '14 at 03:57
  • I was wondering is it enough to use in this case? Are there any better solutions? I have seen some hash functions such as FNV hash and ELF hash. It seems that they are also good to implement. – RickyGao Nov 26 '14 at 04:09
  • You can run a test with a sample of your data. See if it "behaves". – Thilo Nov 26 '14 at 04:13
  • Ok~ As I am not so familiar with hash function, so can you recommend some hash designed for array of integer except the one defined by multiplying 31 kind of thing? – RickyGao Nov 26 '14 at 04:15
0

hashmap functions can be found in https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html

Creating a hashmap is easy.. it goes as 

HashMap<Object, Integer> map = new HashMap<Object, Integer>();
Joseph118
  • 505
  • 6
  • 21