设计哈希映射

LeetCode每日一题，706. Design HashMap

先看题目描述

大意就是自己实现一个哈希表数据结构

算法和思路

链地址法

设计哈希表，主要就是考虑解决这几个问题：

• 哈希函数
• 冲突处理
• 哈希表扩容

哈希函数可以考虑 key 对桶数取模，冲突处理有链地址法，开放地址法和再哈希法，这里使用的是链地址法，即将哈希冲突的键值对使用链表串联起来

算法源码

链地址法

下面使用的方法是在哈希表内部存储一个链表数组，键值对作为节点，键对桶数取模得到该节点应置于链表数组的哪个链表中，然后加至链表末尾。add()，put() 和 remove() 方法均使用迭代器 Iterator 来对链表中节点进行迭代

class MyHashMap {
    private final int BASE = 789;
    private LinkedList[] data = new LinkedList[BASE];

    /** Initialize your data structure here. */
    public MyHashMap() {
        for (int i = 0; i < BASE; i++) {
            data[i] = new LinkedList<Node>();
        }
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int map = hash(key);
        ListIterator<Node> iterator = data[map].listIterator();
        while (iterator.hasNext()) {
            Node node = iterator.next();
            if (node.key == key) {
                node.val = value;
                return;
            }
        }
        iterator.add(new Node(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 map = hash(key);
        Iterator<Node> iterator = data[map].iterator();
        while (iterator.hasNext()) {
            Node node = iterator.next();
            if (node.key == key) {
                return node.val;
            }
        }
        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 map = hash(key);
        Iterator<Node> iterator = data[map].iterator();
        while (iterator.hasNext()) {
            Node node = iterator.next();
            if (node.key == key) {
                iterator.remove();
            }
        }
    }
    
    public int hash(int key) {
        return key % BASE;
    }

    private class Node {
        private int key;
        private int val;

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

/**
 * 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);
 */

下面使用的也是链地址法，但哈希表内部存储的不是链表数组，而是节点数组。不过节点有 next 指针，指向其下一个节点，相当于节点本身串成链表，数组中存储的是每个链表的头节点

class MyHashMap {
    private final int BASE = 789;
    private Node[] data = new Node[BASE];

    /** Initialize your data structure here. */
    public MyHashMap() {

    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        int map = hash(key);
        Node node = data[map];
        if (node == null) {
            data[map] = new Node(key, value);
            return;
        }
        while (node.next != null) {
            if (node.key == key) {
                node.val = value;
                return;
            }
            node = node.next;
        }
        if (node.key == key) {
            node.val = value;
            return;
        }
        node.next = new Node(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 map = hash(key);
        Node node = data[map];
        while (node != null) {
            if (node.key == key) {
                return node.val;
            }
            node = node.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 map = hash(key);
        Node node = data[map];
        Node preNode = null;
        while (node != null) {
            if (node.key == key) {
                if (preNode == null) {
                    data[map] = node.next;
                    return;
                }
                preNode.next = node.next;
                return;
            }
            preNode = node;
            node = node.next;
        }
    }

    public int hash(int key) {
        return key % BASE;
    }

    private class Node {
        private int key;
        private int val;
        private Node next = null;

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

由于题目限定了 key 的范围为 0 - 10的6次方，所以也可以直接使用长度为 10的6次方 + 1 的整型数组，相当于哈希函数为 x -> x，不会发生哈希冲突，直接将 value 存于 data[key] 即可，但是运行效率较低

class MyHashMap {
    int[] data = new int[(int)1e6 + 1];
    {
        Arrays.fill(data, -1);
    }

    /** Initialize your data structure here. */
    public MyHashMap() {

    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        data[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 data[key];
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        data[key] = -1;
    }
}

/**
 * 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);
 */