【LeetCode 哈希表专项】设计哈希集合(705)

文章目录

1. 题目

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

实现 MyHashSet 类:

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

1.1 示例

输入:
["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 ,(已移除)

1.2 说明

1.3 限制

  • 0 ≤ key ≤ 1 0 6 0 \le \text{key} \le 10^6 0≤key≤106
  • 最多调用 1 0 4 10^4 104 次 addcontainsremove 方法

2. 解法一(分离链接法)

2.1 分析

实际上,基于哈希表实现的集合与映射,二者的实现原理基本相同,区别基本仅在于映射中保存的是键值对,而集合中保存的只有键。

因此,本文给出的两种实现和【LeetCode 哈希表专项】设计哈希映射(706)中的解答基本一致,详细分析同样请参考:【数据结构Python描述】仿照Python解释器使用哈希表手动实现一个字典

2.2 解答

下面使用链表作为每个 bucket 发生哈希碰撞时所使用的二级容器。

from random import randrange


class _ListNode:
    def __init__(self, key=0, next=None):
        self.key = key
        self.next = next


class _LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.n = 0

    def append(self, key: int):
        node = _ListNode(key)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next
        self.n += 1

    def remove(self, key: int):
        dummy = _ListNode()
        dummy.next = self.head
        predecessor, cursor = dummy, dummy.next
        while cursor:
            if cursor.key == key:
                predecessor.next = cursor.next
                self.n -= 1
                self.head = dummy.next
                return
            predecessor, cursor = cursor, cursor.next
        raise KeyError('Key does not exist!')

    def __len__(self):
        return self.n


class MyHashSet:

    def __init__(self, cap=11, p=109345121):
        """创建一个空的映射"""
        self._table = [_LinkedList() for _ in range(cap)]
        self._n = 0
        self._prime = p  # MAD压缩函数中大于哈希表容量的大质数
        self._scale = 1 + randrange(p - 1)  # MAD压缩函数中的缩放系数a
        self._shift = randrange(p)  # MAD压缩函数中的偏移系数b

    def _hash_function(self, key):
        """哈希函数"""
        return (self._scale * hash(key) + self._shift) % self._prime % len(self._table)

    def __len__(self):
        return self._n

    def contains(self, key):
        j = self._hash_function(key)
        bucket = self._table[j]
        cursor = bucket.head
        while cursor:
            if cursor.key == key:
                return True
            cursor = cursor.next
        return False

    def add(self, key):
        j = self._hash_function(key)
        size = len(self._table[j])
        bucket = self._table[j]
        cursor = bucket.head
        while cursor:
            if cursor.key == key:
                return
            cursor = cursor.next
        self._table[j].append(key)  # 集合中不存在键key
        if len(self._table[j]) > size:  # key为新的元素
            self._n += 1
        if self._n > len(self._table) // 2:  # 确保负载系数小于0.5
            self._resize(2 * len(self._table) - 1)  # 通常2 * n - 1为质数

    def remove(self, key):
        j = self._hash_function(key)
        bucket = self._table[j]
        try:
            bucket.remove(key)
            self._n -= 1
            return
        except KeyError:
            return

    def _resize(self, cap):
        """将哈希表容量调整为cap"""
        old = list(self)  # 通过迭代获得已有的所有键值对
        self._table = [_LinkedList() for _ in range(cap)]
        self._n = 0
        for key in old:
            self.add(key)

    def __iter__(self):
        for bucket in self._table:
            cursor = bucket.head
            while cursor:
                yield cursor.key
                cursor = cursor.next

需要注意的是,上述解法在 LeetCode 提交时,有时可以通过有时不可以通过,但单独考察不通过的测试案例时,对比上述解答的输出和期望输出又没有发现区别,希望和看到的小伙伴一起交流一下。

3. 解法二(线性查找法)

3.1 分析

详细分析请参考:【数据结构Python描述】仿照Python解释器使用哈希表手动实现一个字典

3.2 解答

from random import randrange


class MyHashSet:

    _AVAIL = object()  # 哨兵标识,用于标识被键值对被删除的哈希表单元

    def __init__(self, cap=11, p=109345121):
        """初始化一个空集合"""
        self._table = [None for _ in range(cap)]
        self._n = 0
        self._prime = p
        self._scale = 1 + randrange(p - 1)
        self._shift = randrange(p)

    def _hash_function(self, key):
        """哈希函数"""
        return (self._scale * hash(key) + self._shift) % self._prime % len(self._table)

    def _is_available(self, j):
        """判断哈希表索引为j的单元处是否引用None或者引用的业务元素被删除"""
        return self._table[j] is None or self._table[j] is MyHashSet._AVAIL

    def _find_slot(self, j, key):
        """
        查找哈希表索引为j的单元处是否有元素key,
        该方法的返回值为一个二元组,且返回情况如下:
        - 当在索引为j的哈希表单元处找到元素key,则返回(True, j),
        - 当未在哈希表任何单元处找到元素key,则返回(False, index),index表示第一个可用单元
        """
        first_avail = None
        while True:
            if self._is_available(j):
                if first_avail is None:
                    first_avail = j
                if self._table[j] is None:
                    return False, first_avail
            elif key == self._table[j]:
                return True, j
            j = (j + 1) % len(self._table)

    def add(self, key: int) -> None:
        j = self._hash_function(key)
        found, s = self._find_slot(j, key)
        if not found:
            self._table[s] = key
            self._n += 1
        else:
            return
        if self._n > len(self._table) // 2:
            self._resize(2 * len(self._table) - 1)

    def _resize(self, cap: int):
        old = list(self)
        self._table = [None for _ in range(cap)]
        self._n = 0
        for key in old:
            self.add(key)

    def remove(self, key: int) -> None:
        j = self._hash_function(key)
        found, s = self._find_slot(j, key)
        if not found:
            return
        self._table[s] = MyHashSet._AVAIL
        self._n -= 1
        if self._n // 2 < len(self._table):
            self._resize((len(self._table) + 1) // 2)

    def contains(self, key: int) -> bool:
        j = self._hash_function(key)
        found, s = self._find_slot(j, key)
        if not found:
            return False
        else:
            return True

    def __iter__(self):
        size = len(self._table)
        for j in range(size):
            if not self._is_available(j):
                yield self._table[j]
上一篇:【1.6 C案例】请君与我用C语言写一个千行的学生管理系统


下一篇:SAP Spartacus 升级时关于 schematics 的更新