Widely used hashing algorithm in Java for implementing Hash tables?

Question

I am implementing a basic HashTable data structure in Java without using collection framework and Arrays.

I intend to use individual nodes whose reference I would store in an array.

I am doing it this way:

Define a Node:

class Node {
 private int data;
 private String key;
 private Node next;
 // Other helper methods
}

Create an array which would hold reference to pre-created Node objects:

public class MyHashTable {
 private Node[] nodeArray = new Node[100];
 public MyHashTable() {
 for(int i=0 ; i<100; i++) {
 nodeArray[i] = new Node();
 }
 }
 private int getIndex(String key) {
 long hashCode = key.hashCode();
 return (int )hashCode%100;
 }
 // Other helper methods...
}

For getting the hash-code, I am using the Java's inbuilt method -> hashCode().

It seems to be working fine, however for the case in which the key is "second", it returns a negative hash code and because of which the programs terminates with an exception.

My question is:

Is there any standard hashing algorithm which I can use for hashing and which is widely used? I am writing for learning purpose.

• Rohan: hashCode() is widely used. You can use Math.abs() to get a positive value from the hashCode() if it is returning negative.
• CuriousMind: @Rohan: Thanks for your response. Is there any other hashing algorithm other than hashCode() which we can use?
• Rohan: The Java HashMap and HashSet classes use hashCode() internally. I don't know of any other standard methods used to create a hash code value. You can always look for some external library that contains one.
• Andy Turner: @Rohan hashCode isn't an algorithm, it is merely a way to access some implementation of hashing.
• Henry: @CuriousMind what I am saying is there is no one best solution. You want to distribute the values pretty good over the hash range and at the same time you want it to be fast to compute. It is a compromise that also depends on the distribution of the things you feed into it.

Answer 1

You could use for example:

@Override
public int hashCode() {
 return 31 * data + ((key == null) ? 0 : key.hashCode());
}

But you also need to implement equals.

• Henry: data should most likely not be included if you want to make something like a hash map.
• Thomas Mueller: @Henry yes, if it's mutable. The same goes for key, if it's mutable. It's better to make key / data final if possible.