广州网站建设推荐wordpress 轻论坛

广州网站建设推荐,wordpress 轻论坛,公司网站后台怎么上传图片,农业开发公司好名字设计哈希集合 问题描述 不使用任何内建的哈希表库设计一个哈希集合#xff08;HashSet#xff09;。 实现 MyHashSet 类#xff1a; void add(key) 向哈希集合中插入一个值 key。bool contains(key) 返回哈希集合中是否包含这个值 key。void remove(key) 将给定值 key 从哈希…设计哈希集合问题描述不使用任何内建的哈希表库设计一个哈希集合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^61的布尔数组方法二链地址核心思想使用桶数组存储链表哈希函数key % bucketSize冲突处理链表存储冲突的键方法三开放地址核心思想冲突时寻找下一个空槽位方法四位图BitSet核心思想使用位数组每个位表示一个键的存在性代码实现方法一布尔数组classMyHashSet{privateboolean[]set;privatestaticfinalintMAX_KEY1000000;/** * 初始化哈希集合 * 使用布尔数组直接映射 */publicMyHashSet(){setnewboolean[MAX_KEY1];}/** * 向哈希集合中添加键 * * 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_SIZE1000;privateListInteger[]buckets;/** * 初始化哈希集合 * 使用链地址处理冲突 */SuppressWarnings(unchecked)publicMyHashSet(){// 创建桶数组每个桶是一个链表bucketsnewLinkedList[BUCKET_SIZE];for(inti0;iBUCKET_SIZE;i){buckets[i]newLinkedList();}}/** * 哈希函数计算键对应的桶索引 */privateinthash(intkey){returnkey%BUCKET_SIZE;}/** * 向哈希集合中添加键 */publicvoidadd(intkey){intbucketIndexhash(key);ListIntegerbucketbuckets[bucketIndex];// 避免重复添加if(!bucket.contains(key)){bucket.add(key);}}/** * 从哈希集合中删除键 */publicvoidremove(intkey){intbucketIndexhash(key);ListIntegerbucketbuckets[bucketIndex];// 从桶中删除键bucket.remove(Integer.valueOf(key));}/** * 检查哈希集合是否包含指定键 */publicbooleancontains(intkey){intbucketIndexhash(key);ListIntegerbucketbuckets[bucketIndex];returnbucket.contains(key);}}方法三优化链地址classMyHashSet{privatestaticfinalintBUCKET_SIZE1000;privateNode[]buckets;// 链表节点定义privatestaticclassNode{intkey;Nodenext;Node(intkey){this.keykey;}}publicMyHashSet(){bucketsnewNode[BUCKET_SIZE];}privateinthash(intkey){returnkey%BUCKET_SIZE;}publicvoidadd(intkey){intbucketIndexhash(key);Nodeheadbuckets[bucketIndex];// 检查是否已存在Nodecurrenthead;while(current!null){if(current.keykey){return;// 已存在无需添加}currentcurrent.next;}// 在头部插入新节点NodenewNodenewNode(key);newNode.nexthead;buckets[bucketIndex]newNode;}publicvoidremove(intkey){intbucketIndexhash(key);Nodeheadbuckets[bucketIndex];if(headnull){return;}// 如果要删除的是头节点if(head.keykey){buckets[bucketIndex]head.next;return;}// 在链表中查找并删除Nodecurrenthead;while(current.next!null){if(current.next.keykey){current.nextcurrent.next.next;return;}currentcurrent.next;}}publicbooleancontains(intkey){intbucketIndexhash(key);Nodecurrentbuckets[bucketIndex];while(current!null){if(current.keykey){returntrue;}currentcurrent.next;}returnfalse;}}方法四位图classMyHashSet{privatestaticfinalintMAX_KEY1000000;privatestaticfinalintINT_BITS32;privateint[]bitSet;publicMyHashSet(){// 计算需要的整数数组大小intsize(MAX_KEYINT_BITS)/INT_BITS;bitSetnewint[size];}privateintgetArrayIndex(intkey){returnkey/INT_BITS;}privateintgetBitIndex(intkey){returnkey%INT_BITS;}publicvoidadd(intkey){intarrayIndexgetArrayIndex(key);intbitIndexgetBitIndex(key);// 设置对应位为1bitSet[arrayIndex]|(1bitIndex);}publicvoidremove(intkey){intarrayIndexgetArrayIndex(key);intbitIndexgetBitIndex(key);// 设置对应位为0bitSet[arrayIndex]~(1bitIndex);}publicbooleancontains(intkey){intarrayIndexgetArrayIndex(key);intbitIndexgetBitIndex(key);// 检查对应位是否为1return(bitSet[arrayIndex](1bitIndex))!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: );MyHashSetmyHashSet1newMyHashSet();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: );MyHashSetmyHashSet2newMyHashSet();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: );MyHashSetmyHashSet3newMyHashSet();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:);MyHashSetmyHashSet4newMyHashSet();for(inti0;i1000;i){myHashSet4.add(i*1000);// 添加0, 1000, 2000, ..., 999000}// 验证添加的元素booleanallPresenttrue;for(inti0;i1000;i){if(!myHashSet4.contains(i*1000)){allPresentfalse;break;}}// 删除一半元素for(inti0;i500;i){myHashSet4.remove(i*1000);}// 验证删除的元素不存在未删除的元素存在booleandeletionCorrecttrue;for(inti0;i500;i){if(myHashSet4.contains(i*1000)){deletionCorrectfalse;break;}}for(inti500;i1000;i){if(!myHashSet4.contains(i*1000)){deletionCorrectfalse;break;}}System.out.println();// 测试用例5空集合操作System.out.println(Test 5: );MyHashSetmyHashSet5newMyHashSet();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)概率很低