Subject to introduce

Buckle 706: leetcode-cn.com/problems/de…

Method one: chain address method

We assume that the reader has completed the topic “705. Designing Hash Sets”.

The “design hash map” is close to the “705. Design Hash set” solution, the only difference being that instead of storing keys, we store (key,value) pairs. Other than that, the code is basically similar.

The code is as follows:

class MyHashMap {
    private class Pair {
        private int key;
        private int value;

        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public int getKey(a) {
            return key;
        }

        public int getValue(a) {
            return value;
        }

        public void setValue(int value) {
            this.value = value; }}private static final int BASE = 769;
    private LinkedList[] data;

    /** Initialize your data structure here. */
    public MyHashMap(a) {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++i) {
            data[i] = newLinkedList<Pair>(); }}/** value will always be non-negative. */
    public void put(int key, int value) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.getKey() == key) {
                pair.setValue(value);
                return;
            }
        }
        data[h].offerLast(new Pair(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) {
        int h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.getKey() == key) {
                returnpair.value; }}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 h = hash(key);
        Iterator<Pair> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Pair pair = iterator.next();
            if (pair.key == key) {
                data[h].remove(pair);
                return; }}}private static int hash(int key) {
        returnkey % BASE; }}Copy the code

Complexity analysis

• Time complexity: O(N/b). Where n is the number of elements in the hash table and b is the number of linked lists. Assuming that the hash values are uniformly distributed, each list is approximately n/b in length.

• Space complexity: O(n+ B).