算法题设计哈希集合-智慧文博士

设计哈希集合

问题描述

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

实现MyHashSet类：

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

约束条件：

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

示例：

输入: ["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 ，（已被删除）

算法思路

方法一：布尔数组

核心思想：直接使用长度为10^6+1的布尔数组

方法二：链地址

核心思想：
- 使用桶数组存储链表
- 哈希函数：key % bucketSize
- 冲突处理：链表存储冲突的键

方法三：开放地址

核心思想：冲突时寻找下一个空槽位

方法四：位图（BitSet）

核心思想：使用位数组，每个位表示一个键的存在性

代码实现

方法一：布尔数组

classMyHashSet{privateboolean[]set;privatestaticfinalintMAX_KEY=1000000;/** * 初始化哈希集合 * 使用布尔数组直接映射 */publicMyHashSet(){set=newboolean[MAX_KEY+1];}/** * 向哈希集合中添加键 * * @param key 要添加的键 (0 <= key <= 10^6) */publicvoidadd(intkey){set[key]=true;}/** * 从哈希集合中删除键 * * @param key 要删除的键 */publicvoidremove(intkey){set[key]=false;}/** * 检查哈希集合是否包含指定键 * * @param key 要检查的键 * @return 如果包含返回true，否则返回false */publicbooleancontains(intkey){returnset[key];}}

方法二：链地址

importjava.util.LinkedList;importjava.util.List;classMyHashSet{privatestaticfinalintBUCKET_SIZE=1000;privateList<Integer>[]buckets;/** * 初始化哈希集合 * 使用链地址处理冲突 */@SuppressWarnings("unchecked")publicMyHashSet(){// 创建桶数组，每个桶是一个链表buckets=newLinkedList[BUCKET_SIZE];for(inti=0;i<BUCKET_SIZE;i++){buckets[i]=newLinkedList<>();}}/** * 哈希函数：计算键对应的桶索引 */privateinthash(intkey){returnkey%BUCKET_SIZE;}/** * 向哈希集合中添加键 */publicvoidadd(intkey){intbucketIndex=hash(key);List<Integer>bucket=buckets[bucketIndex];// 避免重复添加if(!bucket.contains(key)){bucket.add(key);}}/** * 从哈希集合中删除键 */publicvoidremove(intkey){intbucketIndex=hash(key);List<Integer>bucket=buckets[bucketIndex];// 从桶中删除键bucket.remove(Integer.valueOf(key));}/** * 检查哈希集合是否包含指定键 */publicbooleancontains(intkey){intbucketIndex=hash(key);List<Integer>bucket=buckets[bucketIndex];returnbucket.contains(key);}}

方法三：优化链地址

classMyHashSet{privatestaticfinalintBUCKET_SIZE=1000;privateNode[]buckets;// 链表节点定义privatestaticclassNode{intkey;Nodenext;Node(intkey){this.key=key;}}publicMyHashSet(){buckets=newNode[BUCKET_SIZE];}privateinthash(intkey){returnkey%BUCKET_SIZE;}publicvoidadd(intkey){intbucketIndex=hash(key);Nodehead=buckets[bucketIndex];// 检查是否已存在Nodecurrent=head;while(current!=null){if(current.key==key){return;// 已存在，无需添加}current=current.next;}// 在头部插入新节点NodenewNode=newNode(key);newNode.next=head;buckets[bucketIndex]=newNode;}publicvoidremove(intkey){intbucketIndex=hash(key);Nodehead=buckets[bucketIndex];if(head==null){return;}// 如果要删除的是头节点if(head.key==key){buckets[bucketIndex]=head.next;return;}// 在链表中查找并删除Nodecurrent=head;while(current.next!=null){if(current.next.key==key){current.next=current.next.next;return;}current=current.next;}}publicbooleancontains(intkey){intbucketIndex=hash(key);Nodecurrent=buckets[bucketIndex];while(current!=null){if(current.key==key){returntrue;}current=current.next;}returnfalse;}}

方法四：位图

classMyHashSet{privatestaticfinalintMAX_KEY=1000000;privatestaticfinalintINT_BITS=32;privateint[]bitSet;publicMyHashSet(){// 计算需要的整数数组大小intsize=(MAX_KEY+INT_BITS)/INT_BITS;bitSet=newint[size];}privateintgetArrayIndex(intkey){returnkey/INT_BITS;}privateintgetBitIndex(intkey){returnkey%INT_BITS;}publicvoidadd(intkey){intarrayIndex=getArrayIndex(key);intbitIndex=getBitIndex(key);// 设置对应位为1bitSet[arrayIndex]|=(1<<bitIndex);}publicvoidremove(intkey){intarrayIndex=getArrayIndex(key);intbitIndex=getBitIndex(key);// 设置对应位为0bitSet[arrayIndex]&=~(1<<bitIndex);}publicbooleancontains(intkey){intarrayIndex=getArrayIndex(key);intbitIndex=getBitIndex(key);// 检查对应位是否为1return(bitSet[arrayIndex]&(1<<bitIndex))!=0;}}

算法分析

时间复杂度：
- 布尔数组/位图：所有操作O(1)
- 链地址：平均O(1)，最坏O(n)（所有键哈希到同一桶）
空间复杂度：
- 布尔数组：O(10^6)
- 位图：O(10^6/32)
- 链地址：O(n)，n为实际存储的键数量

测试用例

publicclassTestMyHashSet{publicstaticvoidmain(String[]args){// 测试用例1：标准示例System.out.println("Test 1: ");MyHashSetmyHashSet1=newMyHashSet();myHashSet1.add(1);myHashSet1.add(2);System.out.println("contains(1): "+myHashSet1.contains(1));// trueSystem.out.println("contains(3): "+myHashSet1.contains(3));// falsemyHashSet1.add(2);// 重复添加System.out.println("contains(2): "+myHashSet1.contains(2));// truemyHashSet1.remove(2);System.out.println("contains(2): "+myHashSet1.contains(2));// falseSystem.out.println();// 测试用例2：边界值System.out.println("Test 2: ");MyHashSetmyHashSet2=newMyHashSet();myHashSet2.add(0);myHashSet2.add(1000000);System.out.println("contains(0): "+myHashSet2.contains(0));// trueSystem.out.println("contains(1000000): "+myHashSet2.contains(1000000));// truemyHashSet2.remove(0);myHashSet2.remove(1000000);System.out.println("contains(0): "+myHashSet2.contains(0));// falseSystem.out.println("contains(1000000): "+myHashSet2.contains(1000000));// falseSystem.out.println();// 测试用例3：重复操作System.out.println("Test 3: ");MyHashSetmyHashSet3=newMyHashSet();myHashSet3.add(5);myHashSet3.add(5);myHashSet3.add(5);System.out.println("contains(5): "+myHashSet3.contains(5));// truemyHashSet3.remove(5);myHashSet3.remove(5);// 重复删除myHashSet3.remove(5);System.out.println("contains(5): "+myHashSet3.contains(5));// falseSystem.out.println();// 测试用例4：大量操作System.out.println("Test 4:");MyHashSetmyHashSet4=newMyHashSet();for(inti=0;i<1000;i++){myHashSet4.add(i*1000);// 添加0, 1000, 2000, ..., 999000}// 验证添加的元素booleanallPresent=true;for(inti=0;i<1000;i++){if(!myHashSet4.contains(i*1000)){allPresent=false;break;}}// 删除一半元素for(inti=0;i<500;i++){myHashSet4.remove(i*1000);}// 验证删除的元素不存在，未删除的元素存在booleandeletionCorrect=true;for(inti=0;i<500;i++){if(myHashSet4.contains(i*1000)){deletionCorrect=false;break;}}for(inti=500;i<1000;i++){if(!myHashSet4.contains(i*1000)){deletionCorrect=false;break;}}System.out.println();// 测试用例5：空集合操作System.out.println("Test 5: ");MyHashSetmyHashSet5=newMyHashSet();System.out.println("contains(42): "+myHashSet5.contains(42));// falsemyHashSet5.remove(42);// 删除不存在的元素System.out.println("contains(42): "+myHashSet5.contains(42));// falsemyHashSet5.add(42);System.out.println("contains(42): "+myHashSet5.contains(42));// true}}

关键点

哈希函数：
- 简单取模：key % bucketSize
- 桶数量选择：通常选择质数或2的幂次
冲突处理：
- 链地址：每个桶维护一个链表
- 开放地址：寻找下一个空槽
- 再哈希：使用第二个哈希函数
去重处理：
- 添加前检查是否已存在
- 避免集合中出现重复元素
删除操作：
- 链表删除需要处理头节点和中间节点
- 布尔数组和位图直接设置对应位置

常见问题

为什么链地址的桶数量选择1000？
- 桶数量太小会导致链表过长，影响性能
- 桶数量太大会浪费空间
布尔数组会超内存？
- 10^6个布尔值约1MB内存，可以接受
如何处理负数键？
- key≥0，不需要处理负数
- 如果需要处理负数，哈希函数需要调整：(key % bucketSize + bucketSize) % bucketSize
链地址的最坏情况？
- 所有键都哈希到同一个桶，退化为链表
- 时间复杂度变为O(n)，概率很低