设计哈希集合

难度:

标签:

题目描述

代码结果

运行时间: 85 ms, 内存: 21.3 MB

/* 思路：
 * 1. 使用布尔数组来模拟哈希集合，数组大小为1000001（因为0 <= key <= 10^6）。
 * 2. add(key)：将数组中索引为key的位置设为true。
 * 3. contains(key)：返回数组中索引为key的位置的布尔值。
 * 4. remove(key)：将数组中索引为key的位置设为false。
 * 5. 虽然此实现中使用了Java Stream来进行一些额外操作，但在核心功能上与常规Java实现相同。
 */
import java.util.stream.IntStream;

public class MyHashSetStream {
    private boolean[] set;

    /** Initialize your data structure here. */
    public MyHashSetStream() {
        set = new boolean[1000001];
    }

    public void add(int key) {
        set[key] = true;
    }

    public boolean contains(int key) {
        return set[key];
    }

    public void remove(int key) {
        set[key] = false;
    }

    public void printSet() {
        IntStream.range(0, set.length).filter(i -> set[i]).forEach(System.out::println);
    }
}

解释

方法:

这个解决方案通过使用一个数组data来模拟哈希表的功能，每个数组元素是一个列表，用来处理哈希冲突。初始时，数组的长度被设置为1000，并且每个槽位初始化为空列表。哈希函数通过取模运算将键值映射到一个数组索引。添加、删除和检查键值存在性的操作都依赖于这个哈希函数。如果键已存在于集合中，则忽略添加操作。删除操作只有在键存在时才进行。检查键的存在性通过遍历特定索引下的列表完成。

时间复杂度:

O(N) in worst case; O(1) on average

空间复杂度:

O(N)

代码细节讲解

🦆

如何确定初始哈希表大小为1000是合理的？是否考虑了性能和空间效率的平衡？

▷

选择1000作为初始哈希表的大小是基于一般应用情境下的性能与空间效率的折中考虑。这个大小能够在保持较低的冲突率的同时，也不会占用过多的内存空间。此外，1000是一个足够大的数，可以减少哈希冲突，从而提高数据访问的速度。然而，这个值并不是固定的，实际应用中可以根据数据量和访问模式的不同进行调整。

🦆

在哈希冲突的处理中，为什么选择使用链地址法（每个数组元素是一个列表）而不是开放寻址法？

▷

链地址法相比开放寻址法，有几个显著的优点：首先，链地址法在处理哈希冲突时，通过链表可以容易地添加和删除元素，这使得操作相对简单；其次，链地址法不会因为删除操作而产生‘删除孔’，维持性能稳定；最后，链地址法对加载因子的敏感性较低，即使负载较高时也能维持较好的性能。而开放寻址法在负载因子增高时性能下降较快，且处理删除操作较为复杂。

🦆

如果哈希集合中的元素数量远超过1000，是否会考虑实现动态扩容以保持操作的高效性？

▷

是的，如果哈希集合中的元素数量远超过初始大小，将考虑实现动态扩容。动态扩容是通过创建一个更大的哈希表并重新散列所有现有元素来完成的。这样可以减少哈希冲突，维持或提升操作的效率。动态扩容通常会在加载因子（即元素数量与哈希表大小的比率）达到一定阈值时触发，例如常见的阈值是0.75。这样的设计可以使哈希集合在元素数量增加时仍然保持较高的性能。

相关问题

设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射（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 。

示例：

输入：
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]

解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1);    // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3);    // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2);    // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2);    // 返回 -1（未找到），myHashMap 现在为 [[1,1]]

提示：

0 <= key, value <= 10⁶
最多调用 10⁴ 次 put、get 和 remove 方法

香槟塔设计哈希映射