力扣706. 手写简单hash表（2022.7.30）

706. 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

• MyHashMap() 用空映射初始化对象
• void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
• int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
• void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

在手写hash表之前，我们首先得了解hash表底层是怎样构成的。hash表在1.8之后是由数组+链表+红黑树构成的，当链表长度大于8并且数组长度大于64时，会发生链表转红黑树，在这道题中，我们不用考虑那么多，只需要实现数组加链表即可

首先我们需要一个数组和链表节点，数组长度我们设为1009，是1000之后的第一个质数，长度为质数时数据可以尽量的均匀分配在数组中

代码如下

class MyHashMap {

    Node[] table;
    int len = 1009;

    class Node {

        int key;
        int val;
        Node next;

        Node() {
        }

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

        public int getKey() {
            return key;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }
    }

    public MyHashMap() {
        table = new Node[len];
        for (int i = 0; i < table.length; i++) {
            table[i] = new Node();
        }
    }

    public void put(int key, int value) {
        int hash = hash(key);
        Node node = table[hash];
        Node t = node;
        while (true) {
            if (t.getKey() == key && t != node) {
                t.setVal(value);
                return;
            }
            if (t.next == null) break;
            t = t.next;
        }
        t.next = new Node(key, value);
    }

    public int get(int key) {
        int hash = hash(key);
        Node node = table[hash];
        Node t = node.next;
        while (t != null) {
            if (t.getKey() == key) return t.getVal();
            t = t.next;
        }
        return -1;
    }

    public void remove(int key) {
        int hash = hash(key);
        Node node = table[hash];
        Node t = node;
        while (t.next != null) {
            if (t.next.getKey() == key) {
                t.next = t.next.next;
                return;
            }
            t = t.next;
        }
    }

    private int hash(int key) {
        return key % len;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

在上述代码中有一个细节，就是数组初始值为链表的虚拟头节点，这样就可以避免每次处理链表头的麻烦。

 

根据HashSet源码，我们可根据这个hash表实现MyHashSet

代码如下

class MyHashSet {

    private MyHashMap map;
    private int val;

    public MyHashSet() {
        map = new MyHashMap();
        val = 1;
    }

    public void add(int key) {
        map.put(key, val);
    }

    public void remove(int key) {
        map.remove(key);
    }

    public boolean contains(int key) {
        return map.get(key) != -1;
    }
}

class MyHashMap {

    Node[] table;
    int len = 1009;

    class Node {

        int key;
        int val;
        Node next;

        Node() {
            this.key = Integer.MIN_VALUE;
        }

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

        public int getKey() {
            return key;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }
    }

    public MyHashMap() {
        table = new Node[len];
        for (int i = 0; i < table.length; i++) {
            table[i] = new Node();
        }
    }

    public void put(int key, int value) {
        int hash = key % len;
        Node node = table[hash];
        Node t = node;
        while (true) {
            if (t.getKey() == key) {
                t.setVal(value);
                return;
            }
            if (t.next == null) break;
            t = t.next;
        }
        t.next = new Node(key, value);
    }

    public int get(int key) {
        int hash = key % len;
        Node node = table[hash];
        Node t = node;
        while (t != null) {
            if (t.getKey() == key) return t.getVal();
            t = t.next;
        }
        return -1;
    }

    public void remove(int key) {
        int hash = key % len;
        Node node = table[hash];
        Node t = node;
        while (t.next != null) {
            if (t.next.getKey() == key) {
                t.next = t.next.next;
                return;
            }
            t = t.next;
        }
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */