2
\$\begingroup\$

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


}
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ – Marc-Andre Jul 26 '16 at 19:04
  • \$\begingroup\$ @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. \$\endgroup\$ – CodeMonkey Jul 26 '16 at 19:39
1
\$\begingroup\$

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)) 
\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$ – CodeMonkey Jul 26 '16 at 23:53
  • \$\begingroup\$ @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. \$\endgroup\$ – JS1 Jul 26 '16 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.