AlgoPress | AlgoPress

0705-设计哈希集合

https://leetcode.cn/problems/design-hashset

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

实现 MyHashSet 类：

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

示例：

输入：
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]

解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

提示：

0 <= key <= 10^6
最多调用 10^4 次 add、remove 和 contains

思路

题目叫设计哈希映射，key 是 int 值，所以我们用最简单的 Hash 办法，取模。取一个大的质数作为基准，比如 769 这样每个 key 传入的时候，就映射为 key / 769 作为 hashKey. 那这样必然会冲突，比如 0 和 769都会映射为0，冲突的解决方式可以用链表。即每个元素中储存的是链表，链表的 key 和 value 保存为实际的key和value 当 hasKey 相同的时候，在链表中查找真实的key，如果不存在，就追加一个节点储存值。

本地因为只要存储key，所以可以初始化 key = key, value = -1 表示不存在，这样链表的首节点就一定存在

参考代码

csharp

public class MyHashSet {

    public class LinkedList{
        public LinkedList Next;
        private int key;
        private int value;
        public LinkedList(int key, int value){
            this.key = key;
            this.value = value;
        }
        public int GetKey(){
            return key;
        }
        public void SetValue(int value){
            this.value = value;
        }
        public int GetValue(){
            return this.value;
        }
    }

    private int baseValue = 769;
    private int Hash(int value){
        return value % baseValue;
    }
    private List<LinkedList> list;

    public MyHashSet() {
        list = new List<LinkedList>();
        for(int i=0; i<baseValue; i++){
            list.Add(new LinkedList(i,-1));
        }
    }
    
    public void Add(int key) {
        int hashKey = Hash(key);
        LinkedList node = list[hashKey];
        LinkedList pre = null;
        while(node != null){
            if(node.GetKey() == key){
                node.SetValue(key);
                return;
            }
            pre = node;
            node = node.Next;
        }
        LinkedList newNode = new LinkedList(key,key);
        pre.Next = newNode;
    }
    
    public void Remove(int key) {
        int hashKey = Hash(key);
        LinkedList node = list[hashKey];
        while(node != null && node.GetKey() != key){
            node = node.Next;
        }
        if(node != null){
            node.SetValue(-1);
        }
    }
    
    public bool Contains(int key) {
        int hashKey = Hash(key);
        LinkedList node = list[hashKey];
        while(node != null && node.GetKey() != key){
            node = node.Next;
        }
        if(node != null && node.GetValue() != -1){
            return true;
        }
        return false;
    }
}

0705-设计哈希集合 #

思路 #

参考代码 #

0705-设计哈希集合

思路

参考代码