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;
        }
    }


}

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))