news 2026/5/1 9:05:36

算法题 设计哈希集合

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
算法题 设计哈希集合

设计哈希集合

问题描述

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

关键点

  1. 哈希函数：

    • 简单取模：key % bucketSize
    • 桶数量选择：通常选择质数或2的幂次

  2. 冲突处理：

    • 链地址：每个桶维护一个链表
    • 开放地址：寻找下一个空槽
    • 再哈希：使用第二个哈希函数

  3. 去重处理：

    • 添加前检查是否已存在
    • 避免集合中出现重复元素

  4. 删除操作：

    • 链表删除需要处理头节点和中间节点
    • 布尔数组和位图直接设置对应位置

常见问题

  1. 为什么链地址的桶数量选择1000？

    • 桶数量太小会导致链表过长，影响性能
    • 桶数量太大会浪费空间

  2. 布尔数组会超内存？

    • 10^6个布尔值约1MB内存，可以接受

  3. 如何处理负数键？

    • key≥0，不需要处理负数
    • 如果需要处理负数，哈希函数需要调整：(key % bucketSize + bucketSize) % bucketSize

  4. 链地址的最坏情况？

    • 所有键都哈希到同一个桶，退化为链表
    • 时间复杂度变为O(n)，概率很低
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/5/1 6:51:17

3步掌握AI图像修复：零代码集成IOPaint的完整指南

3步掌握AI图像修复&#xff1a;零代码集成IOPaint的完整指南 【免费下载链接】IOPaint 项目地址: https://gitcode.com/GitHub_Trending/io/IOPaint 还在为图片中的水印、多余物体烦恼吗&#xff1f;IOPaint作为开源的AI图像修复工具&#xff0c;让图像编辑变得简单高效…

作者头像 李华
网站建设 2026/4/29 16:02:07

Linux命令-get_module命令（显示Linux内核模块的详细内部信息）

&#x1f9ed; 说明 get_module 命令用于显示Linux内核模块的详细内部信息&#xff0c;例如其状态、引用计数、参数以及内存中的节区&#xff08;Sections&#xff09;地址等。下面是一个快速用法指南。 &#x1f50d; 命令语法与示例 命令的基本语法非常简单&#xff1a; get_…

作者头像 李华
网站建设 2026/5/1 8:01:43

脚本 手机跑.简易go服务器

termux 运行即可package mainimport ("log" // 1. 导入日志包"net/http" // 2. 导入HTTP服务包 )// 3. 主函数 - 程序入口点 func main() {// 4. 创建文件服务器&#xff0c;服务当前目录fs : http.FileServer(http.Dir("."))// 5. 注册路由…

作者头像 李华
网站建设 2026/5/1 6:18:28

动态规划解决堆箱子问题：从原理到代码实现

动态规划解决堆箱子问题&#xff1a;从原理到代码实现在算法领域中&#xff0c;堆箱子问题是经典的动态规划应用场景之一。它不仅考察对问题的建模能力&#xff0c;更能深入体现动态规划“分解子问题、存储中间状态、复用最优解”的核心思想。本文将从问题定义出发&#xff0c;…

作者头像 李华