Interview: Implement a HashMap-like datastruct without using any types from Collection API. Make sure it is flexibly extensible.

LinkedMap.java

class LinkedMap<Key, Value> {
    private class Node<Key, Value> {
        private Key key;
        private Value value;
        private Node<Key, Value> next;

        public Node(Key key, Value value, Node<Key, Value> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node: [key=" + key + ", value=" + value +"]";
        }
    }
    private class Bucket<Key, Value> {
        private int hashCode;
        private Node<Key, Value> head;
        private Bucket<Key, Value> next;

        public Bucket(int hashCode, Bucket<Key, Value> next) {
            this.hashCode = hashCode;
            this.next = next;
        }

        @Override
        public int hashCode() {
            return hashCode;
        }

        public Value put(Key key, Value value) {
            if (key == null) {
                throw new NullPointerException("Key cannot be null!");
            }
            Node<Key, Value> currentNode = head;
            while (currentNode != null ) {
                if (currentNode.key.equals(key)) {
                    currentNode.value = value;
                    break;
                }
                currentNode = currentNode.next;
            }
            if (currentNode == null) {
                currentNode = new Node<Key, Value>(key, value, head);
                head = currentNode;
            }
            return currentNode.value; 
        }

        public Value get(Key key) {
            if (key == null) {
                throw new NullPointerException("Key cannot be null!");
            }

            Node<Key, Value> currentNode = head;
            while (currentNode != null) {
                if (currentNode.key.equals(key)) {
                    return currentNode.value;
                }
                currentNode = currentNode.next;
            }
            return null;
        }

        public Value remove(Key key) {
            Node<Key, Value> currentNode = head;
            Node<Key, Value> previousNode = null;
            Value value = null;

            if (currentNode != null && currentNode.key.equals(key)) {
                value = currentNode.value;
                head = currentNode.next;
            } else {
                while (currentNode != null) {
                    if (currentNode.key.equals(key)) {
                        value = currentNode.value;
                        previousNode.next = currentNode.next;
                        break;
                    } else {
                        previousNode = currentNode;
                        currentNode = currentNode.next;
                    }
                }
            }
            return value; 
        }

        public boolean isEmpty() {
            return head == null;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder("Bucket:" + hashCode + "[");
            Node<Key, Value> currentNode = head;
            while (currentNode != null) {
                sb.append(currentNode.toString());
                currentNode = currentNode.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }

    private Bucket<Key, Value> head;

    public Value get(Key key) {
        if (key == null) {
            throw new NullPointerException("Key cannot be null!");
        }
        Bucket<Key, Value> bucket = findBucketByHashCode(key.hashCode());
        if (bucket == null) {
            return null;
        }
        return bucket.get(key);    
    }

    public boolean isEmpty() {
        return null == head;
    }

    public Value put(Key key, Value value) {
        if (key == null) {
            throw new NullPointerException("Key cannot be null!");
        }
        Bucket<Key, Value> bucket = findBucketByHashCode(key.hashCode());
        if (null == bucket) {
            bucket = insertBucketByHashCode(key.hashCode());
        }
        return bucket.put(key, value);
    }

    public Value remove(Key key) {
        if (key == null) {
            throw new NullPointerException("Key cannot be null!");
        }
        Bucket<Key, Value> bucket = findBucketByHashCode(key.hashCode());
        if (bucket == null) {
            return null;
        }
        Value value = bucket.remove(key);
        if (bucket.isEmpty()) {
            removeBucket(bucket);
        }
        return value; 
    }

    public int size() {
        int count = 0;
        Bucket<Key, Value> currentBucket = head;
        while (currentBucket != null) {
            Node<Key, Value> currentNode = currentBucket.head;
            while (currentNode != null) {
                count += 1;
                currentNode = currentNode.next;
            }
            currentBucket = currentBucket.next;
        }
        return count;
    }

    @Override
    public String toString() {
        Bucket<Key, Value> currentBucket = head;
        StringBuilder sb = new StringBuilder("Map: ");
        while (currentBucket != null) {
            sb.append(currentBucket.toString());
            currentBucket = currentBucket.next;
        }
        return sb.toString();
    }

    private Bucket<Key, Value> findBucketByHashCode(int hashCode) {
        Bucket<Key, Value> bucket = head;
        while (bucket != null) {
            if (bucket.hashCode() == hashCode) {
                return bucket;
            } else {
                bucket = bucket.next;
            }
        }
        return bucket;
    }

    private Bucket<Key, Value> insertBucketByHashCode(int hashCode) {
        Bucket<Key, Value> newBucket = new Bucket<>(hashCode, head);
        head = newBucket;
        return newBucket;
    }

    private void removeBucket(Bucket<Key, Value> bucket) {
        
        if (head.equals(bucket)) {
            head = head.next;
        } else {
            Bucket<Key, Value> currentBucket = head;
            Bucket<Key, Value> previousBucket = null;
            while (currentBucket != null) {
                if (currentBucket.equals(bucket)) {
                    previousBucket.next = currentBucket.next;
                    break;
                } else {
                    previousBucket = currentBucket;
                    currentBucket = currentBucket.next;
                }
            }
        }
    }
}

Main.java

public class Main {

    static class KeyClazz {
        private Integer num;
        KeyClazz(int num) {
            this.num = num;
        }

        @Override
        public int hashCode() {
            return 2;
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof KeyClazz) {
                return num.equals(((KeyClazz)o).num);    
            }
            return false;
        }

        @Override
        public String toString() {
            return "KeyClazz: [num=" + num + "]";
        }
    }

    public static void main(String[] args) {
        //testInteger();
        testKeyClazz();
    }

    static void testInteger() {
        LinkedMap<Integer, Character> map = new LinkedMap<>();
        
        System.out.println("true " + map.isEmpty());
        map.put(1, 'c');
        map.put(2, 'c');
        map.put(3, 'd');
        map.put(2, 'a');
        map.put(4, 'e');
        System.out.println("false " + map.isEmpty());
        System.out.println("null " + map.get(10));
        System.out.println("a " + map.get(2));
        System.out.println("2 " + map.size());
        System.out.println(map);
        System.out.println("c " + map.remove(2));
        System.out.println("2 " + map.size());
        System.out.println(map);
    }

    static void testKeyClazz() {
        LinkedMap<KeyClazz, Character> map = new LinkedMap<>();
        
        System.out.println("true " + map.isEmpty());
        map.put(new KeyClazz(1), 'e');
        map.put(new KeyClazz(2), 'e');
        map.put(new KeyClazz(2), 'a');
        map.put(new KeyClazz(3), 'b');
        map.put(new KeyClazz(2), 'c');
        map.put(new KeyClazz(4), 'e');
        System.out.println("false " + map.isEmpty());
        System.out.println("null " + map.get(new KeyClazz(10)));
        System.out.println("c " + map.get(new KeyClazz(2)));
        System.out.println(map);
        System.out.println("c " + map.remove(new KeyClazz(2)));
        System.out.println("3 " + map.size());
        System.out.println(map);
    }
}