力扣705-设计哈希集合（简单）

题目描述

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

• void add(key) 向哈希集合中插入值 key 。
• bool contains(key) 返回哈希集合中是否存在这个值 key 。
• void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

方法一：链地址法

分析：

设哈希表的大小为 base，则可以设计一个简单的哈希函数：hash(x)=x mod base

算法：

我们开辟一个大小为base的数组，数组的每个位置是一个链表。当计算出哈希值之后，就插入到对应位置的链表当中。

由于我们使用整数除法作为哈希函数，为了尽可能避免冲突，应当将base取为一个质数。在这里，我们取 base = 769。

①官方代码（使用）

class MyHashSet {
    private static final int BASE = 769;
    private LinkedList[] data;

    /** Initialize your data structure here. */
    public MyHashSet() {
        data = new LinkedList[BASE];
        for (int i = 0; i < BASE; ++i) {
            data[i] = new LinkedList<Integer>();
        }
    }
    
    public void add(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element == key) {
                return;
            }
        }
        data[h].offerLast(key);
    }
    
    public void remove(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element == key) {
                data[h].remove(element);
                return;
            }
        }
    }
    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = data[h].iterator();
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element == key) {
                return true;
            }
        }
        return false;
    }

    private static int hash(int key) {
        return key % BASE;
    }
}

②我的代码（牺牲空间）

class MyHashSet {
    static int base = 1000001;

    MyNode[] myNodes;

    public MyHashSet() {
        myNodes = new MyNode[base];
    }

    public void add(int key) {
        MyNode newMyNode = myNodes[key];
        if (newMyNode == null) {
            MyNode node = new MyNode();
            myNodes[key] = node;
        }
        // MyNode node = new MyNode();
        // node.next = myNodes[key];
        // myNodes[key] = node;
    }

    public void remove(int key) {
        MyNode newMyNode = myNodes[key];
        if (newMyNode == null) {
            return;
        }
        myNodes[key] = newMyNode.next;
    }

    public boolean contains(int key) {
        MyNode newMyNode = myNodes[key];
        return newMyNode != null;
    }

    class MyNode {
        MyNode next;
    }
}

方法二：开放地址法

当发现哈希值h处产生冲突时，根据某种策略，从h出发找到下一个不冲突的位置。例如，一种最简单的策略是，不断地检查 h+1,h+2,h+3,…这些整数对应的位置。

方法三：在哈希法

当发现哈希冲突后，使用另一个哈希函数产生一个新的地址。