[Apple Question] Design HashMap

Problem: Design a HashMap without using any built-in hash table libraries. Here are the methods you must support:

• put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
• get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Notes: 

1. All keys and values will be in the range of [0, 1000000].
2. The number of operations will be in the range of [1, 10000].

Approach: Basically, we can use Array of Doubly Linked List here. We can use a prime number say 2069 as the Array length and we will store key value at (key % 2069)th index. If a key-value is already in that Linked List(collision), we will just add this new key-value pair at the end of the linked list.

Implementation in C#:

public class MyHashMap 

{

    public MyHashMap() 

    {

        this.size = 2069;

        this.buckets = new LinkedList<KeyValuePair<int, int>>[2069];

    }

   

    public void Put(int key, int value) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            this.buckets[index] = new LinkedList<KeyValuePair<int, int>>();

        }

        else

        {

            LinkedListNode<KeyValuePair<int, int>> node = this.buckets[index].First;

            while (node != null)

            {

                if (node.Value.Key == key)

                {

                    this.buckets[index].Remove(node);

                    break;

                }

                node = node.Next;

            }

        }

        this.buckets[index].AddLast(new KeyValuePair<int, int>(key, value));

    }

    

    public int Get(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            return -1;

        }

        LinkedListNode<KeyValuePair<int, int>> node = this.buckets[index].First;

        while (node != null)

        {

            if (node.Value.Key == key)

            {

                return node.Value.Value;

            }

            node = node.Next;

        }

        return -1;

    }

    

    public void Remove(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            return;

        }

        LinkedListNode<KeyValuePair<int, int>> node = this.buckets[index].First;

        while (node != null)

        {

            if (node.Value.Key == key)

            {

                this.buckets[index].Remove(node);

                break;

            }

            node = node.Next;

        }

    }

    

    LinkedList<KeyValuePair<int, int>>[] buckets;

    int size;

}

Complexity: O(n/k) where k = 2069 (number of buckets) and n is all unique keys.