Bare bones implementation of Java HashMap

Question

I've done a minimal implementation of a HashMap. Invite comments.

public class HashMap<K, V> {
 private final int size = 16;
 private Node<K, V>[] arr;
 public HashMap(){
 arr = new Node[size];
 }
 class Node<K, V> {
 private int index;
 private K key;
 private V value;
 private Node<K, V> next;
 protected Node(K key, V value){
 this.key = key;
 this.value = value;
 }
 }
 private int getHashCodeForKey(K key){
 int result = 7;
 return 31 * result + (key != null ? key.hashCode() : 0);
 }
 public V get(K key){
 int hashcode = getHashCodeForKey(key);
 int index = hashcode & size;
 Node head = arr[index];
 while(head != null){
 if(head.key == key) return (V) head.value;
 head = head.next;
 }
 return null;
 }
 public void put(K key, V value){
 Node curr = new Node(key, value);
 int hashcode = getHashCodeForKey(key);
 int index = hashcode & size;
 if(arr[index] == null){
 arr[index] = curr;
 }else{
 Node head = arr[index];
 curr.next = head;
 }
 }
}

• Marc-Andre: Welcome to Code Review. Do you have any side of your code that you think need more love ? Are there any specific aspect you want reviewed ? Keep in mind that people can review any aspect.
• CodeMonkey: @Marc-Andre thanks for highlighting that. This is not a full-featured implementation, so I'm basically looking someone to review the correctness and efficiency of the current implementation.

Answer 1

Strange constant usage

This code seems strange to me:

private int getHashCodeForKey(K key){
 int result = 7;
 return 31 * result + (key != null ? key.hashCode() : 0);
}

Why set result to 7, just to multiply it by 31? That is, why not this:

private int getHashCodeForKey(K key){
 int result = 7 * 31;
 return result + (key != null ? key.hashCode() : 0);
}

It makes me think that you wanted to multiply the whole thing by 31 but I'm not sure of your intent.

Weakening the hash

The code that uses the hash code:

 int hashcode = getHashCodeForKey(key);
 int index = hashcode & size;
 Node head = arr[index];

weakens the hash because you are using power of 2 sized arrays (in your case a fixed size 16 array). So in your case you are using only 4 bits of the hash. If your array size were 17 and you used % 17, it would use all the bits of the hash.

Poor performance

With a fixed size of 16 buckets, your hash will quickly devolve into a linear search once you add a lot of entries. A proper hash map would resize itself at appropriate intervals to maintain performance.

Correctness

This comparison is not correct:

if(head.key == key)

For example, two strings that have the same contents will not compare correctly using the above code. You should change the comparison to:

if (head.key.equals(key)) 

• CodeMonkey: I agree head.key == key won't work but equals(head.key, key) is giving compilation errors. I think you meant head.key.equals(key)
• JS1: @CodeMonkey Yes, thanks for that. I fixed my answer. I think I was thinking of a helper function that could also work if both objects were null.