1
\$\begingroup\$

After understanding HashMaps, I decided to implement my own using 3 classes HashMap, LinkedList, and Node. I knew how to implement LinkedList from before.

Can you please give me feedback on this. Will this be an acceptable implementation for a technical interview?

Also do we actually need to implement the data structure needed to solve the problem or use the language library?

public class HashMap<K, V> {

    LinkedList<K, V>[] buckets;

    HashMap(int size) {
        buckets = new LinkedList[size];
    }

    public void insert(K key, V value) {
        Node<K, V> newNode = new Node<>(key, value);

        int bucket = getIndex(key);

        //Create bucket if it does not exist.
        if(buckets[bucket] == null) {
            buckets[bucket] = new LinkedList<>();
        }

        buckets[bucket].insert(newNode);
    }

    public void delete(K key) {
        int bucket = getIndex(key);

        if(buckets[bucket] == null) {
            System.out.println("Hashmap is empty.");
            return;
        }

        buckets[bucket].delete(key);
    }

    public Node find(K key) {
        int bucket = getIndex(key);

        return buckets[bucket].find(key);
    }

    public int getIndex(K key) {
        return key.hashCode() % buckets.length;
    }

    @Override
    public String toString() {
        String data = "";

        for(int i = 0; i < buckets.length; i++) {
            if(buckets[i] != null) {
                data += "[" + i + "]" + " = " + buckets[i].toString() + " null";
                data += "\n";
            }
        }

        return data;
    }
}



public class LinkedList<K, V> {
    Node<K, V> head;

    public void insert(Node<K, V> newNode) {
        if(head == null) {
            head = newNode;
            return;
        }

        Node<K, V> current = head;

        while(current.getNext() != null)
            current = current.getNext();

        current.setNext(newNode);
    }

    public void delete(K key) {
        if(head == null)
            return;

        //If head to be deleted.
        if(head.getKey() == key) {
            head = head.getNext();
            return;
        }

        Node current = head;

        while(current.getNext().getKey() != key)
            current = current.getNext();

        current.setNext(current.getNext().getNext());
    }

    public Node find(K key) {
        Node current = head;

        //While not reached end or not found keep going.
        while(current != null && current.getKey() != key) {
            current = current.getNext();
        }

        //Returns null if not found.
        return current;
    }

    @Override
    public String toString() {
        String data = "";

        Node current = head;

        while(current != null) {
            data += "(" + current.getKey() + ", " + current.getValue() + ")" + " -> ";
            current = current.getNext();
        }

        return data;
    }
}



public class Node<K, V> {
    private K key;
    private V value;

    private Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}



public class HashMapTesting {
    public static void main(String[] args) {

        HashMap<String, Integer> ages = new HashMap<>(5);

        //Testing insertion
        ages.insert("Reda", 22);
        ages.insert("Mike", 34);
        ages.insert("Tom", 55);
        ages.insert("Daniel", 32);
        ages.insert("Leonardo", 42);

        System.out.println(ages.toString());

        //Testing search
        System.out.println(ages.find("Daniel").getValue() + "\n");

        //Testing deletion
        ages.delete("Mike");
        System.out.println(ages.toString());
    }
}

Output:

[0] = (Reda, 22) -> (Mike, 34) ->  null
[2] = (Leonardo, 42) ->  null
[4] = (Tom, 55) -> (Daniel, 32) ->  null

32

[0] = (Reda, 22) ->  null
[2] = (Leonardo, 42) ->  null
[4] = (Tom, 55) -> (Daniel, 32) ->  null
\$\endgroup\$
  • 1
    \$\begingroup\$ The moment an interviewee would proudly tell me how they implemented their own HashMap, I'd extend my hand, wish them all the best and say goodbye. \$\endgroup\$ – I'll add comments tomorrow Nov 15 '18 at 23:24
  • 2
    \$\begingroup\$ I think I know what you mean, but just want to double check. I don't understand? \$\endgroup\$ – Rino Leonardino Nov 15 '18 at 23:31
  • \$\begingroup\$ Are the generic definition missing on nearly all return values? Like Node instead of Node<K,V> \$\endgroup\$ – Serverfrog Nov 16 '18 at 12:33
  • \$\begingroup\$ What is the difference of having return type as Node and Node<K, V>? \$\endgroup\$ – Rino Leonardino Nov 16 '18 at 16:17
2
\$\begingroup\$

Visibility: I find the visibility of your variables strange. Why is "buckets" a package protected variable in your HashMap class? Do you need to use it outside of the class in the package? Your code doesn't indicate that, so it should be private. Same with LinkedList.head.

Additionally, why are the constructors package private? I assume your IDE gave you that tip because your main method lies in the same package, but you should ignore that. Make them public.

Node.next: Your HashMap returns Nodes and those Nodes have a public getter and setter for the next variable. Using them, one can get a node, set another next and mutate the HashMap from outside. That's certainly not what you (should) want. "getNext" and "setNext" should be package private and your main method should be outside the package to demonstrate that you really understand that these methods shouldn't be accessed by the client. I guess that's what vnp meant.

Node<K, V>: As Serverfrog mentioned, your returns miss the generic type information for Node. Imagine you create a HashMap with a String key and integer values. Now you want to find a certain integer and multiply it by two. The problem with this is that your HashMap returns a Node which doesn't know which types are stored in it. So it gives you the value as an Object. Now you have to cast it just because you forgot to add <K, V> to your return type.

|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$
  • LikedList::insert is suboptimal. It requires an entire list to be traversed. Since you don't case about the order it is much simpler to always prepend a new node:

        newNode.setNext(head);
        head = newNode;
    

    If you for some reason do care about the order, consider maintaining an explicit tail.

  • LinkedList::delete fails with an exception if the key doesn't exist (current.getNext() will eventually be null).

  • Unrestricted accessors getNext() and setNext() hint that Node::next really is a public member.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Very good points. I totally agree with the first point. I will just add a tail to the LinkedList just because it will give me better flexibility later, and I like the idea of having the order. Second point, you are totally correct, I missed this. Hopefully I don't miss this in the interview.. Third point, I don't quite understand what you mean by this? Do you mean remove the getNext() and setNext() methods and having the next variable public? Thanks! \$\endgroup\$ – Rino Leonardino Nov 15 '18 at 23:36

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.