706. Design HashMap

706. Design HashMap

My Solutions:

1. Hashtable is synchronized, whereas HashMap is not. This makes HashMap better for non-threaded applications, as unsynchronized Objects typically perform better than synchronized ones.

2. Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.

Hash Table

A data structure that stores data as keys/value pair. Data is stored in arrays of buckets using hash keys. Hash key is calculated by hashing. In hashing, it computes keys by hash function. The idea of hashing is to distribute entries evenly across an array, so that a data set of an arbitrary size maps to a data set of fixed size in a hash table.

For collision, if the hash function is not good enough, it generates the same index for more than one key. If there are a large number of possible keys, collision is relatively unavoidable. Usually, once the load factor is about 0.75, the size of hash table need to be enlarged because the chance of collision is too large, where load factor = number of entries in the hash table / table length.

There are several ways to handle collisions. One way is that in each index bucket, it has a list of entries with the same index. The time for searching is the time to find the bucket plus the time to find the specific entry in the list. Another common way is called open addressing. In this way, once a new entry is inserted but the calculated index of bucket is occupied already, some kinds of probing can be applied until an empty spot is found and the new entry will be inserted there. There are several ways of probing. For example, we can probe each bucket until one empty spot is found. Or, we can compute another hash function to find how many intervals between buckets we are going to probe.

The worst time complexity for search is O(n), for insertion is O(n) and for deletion is O(n) too.

//This method use the index bucket. Data is stored as linked-list

public class MyHashMap {
    
    class Data {
    int key, val;
    Data next;
    
    Data(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
    
    Data[] map;
    int size;

    /** Initialize your data structure here. */
    public MyHashMap() {
        map = new Data[10];
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        int hash = key % map.length;
        
        if (map[hash] == null) {
            map[hash] = new Data(key, value);
        } else if (map[hash].key == key) {
            map[hash].val = value;
        } else { //need to link to the last Data
            Data d = map[hash];
            while (d.next != null && d.next.key != key) d = d.next;
            if (d.next != null) d.next.val = value;
            else d.next = new Data(key, value);
        }
        
        size++;
        if (size * 1.0 / map.length > 0.75) rehash();
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int hash = key % map.length;
        Data d = map[hash];
        while (d != null) {
            if (d.key == key) return d.val;
            else d = d.next;
        }
        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int hash = key % map.length;
        if (map[hash] == null) return;
        if (map[hash].key == key) map[hash] = map[hash].next;
        else {
            Data d = map[hash];
            while (d.next != null && d.next.key != key) d = d.next; //find the d.next.key == key to remove
            if (d.next != null) d.next = d.next.next; //if there is a next one which d.next.key == key, remove it; otherwise, it means it's already the end of the list, do nothing
        }
    }
    
    public void rehash() {
        Data[] old = map;
        map = new Data[map.length * 2];
        for (int i = 0; i < old.length; i++) {
            Data d = old[i];
            while (d != null) {
                put(d.key, d.val);
                d = d.next;
            }
        }
        
    }
}

根据题目给的条件，也可以用Naive 方法，存在int array里。

Note:

• All keys and values will be in the range of [0, 1000000].

• The number of operations will be in the range of [1, 10000].

• Please do not use the built-in HashMap library.

class MyHashMap {
    
    int[] map;

    /** Initialize your data structure here. */
    public MyHashMap() {
        map = new int[1000001];
        for (int i = 0; i < 1000001; i++) {
            map[i] = -1;
        }
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        map[key] = value;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        return map[key];
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        map[key] = -1;
    }
}