算法题 设计哈希映射

设计哈希映射

问题描述

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现MyHashMap类：

• void put(int key, int value)向哈希映射中插入键值对(key, value)。如果键已经存在，更新对应的值。
• int get(int key)返回特定的键所映射的值；如果映射中不包含该键，返回-1。
• void remove(key)如果映射中包含该键，移除这个键值对。

约束条件：

• 0 <= key, value <= 10^6
• 最多调用10^4次put、get和remove方法

示例：

输入: ["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); // map = {1:1} myHashMap.put(2, 2); // map = {1:1, 2:2} myHashMap.get(1); // 返回 1 myHashMap.get(3); // 返回 -1（未找到） myHashMap.put(2, 1); // map = {1:1, 2:1} myHashMap.get(2); // 返回 1 myHashMap.remove(2); // map = {1:1} myHashMap.get(2); // 返回 -1（已被删除）

算法思路

方法一：数组直接寻址

• 核心思想：使用长度为10^6+1的整数数组，索引表示键，值表示对应的值
• 特殊标记：用-1表示键不存在（因为value≥0）

方法二：链地址

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

方法三：开放地址

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

代码实现

方法一：数组直接寻址

classMyHashMap{privatestaticfinalintMAX_KEY=1000000;privatestaticfinalintNOT_EXIST=-1;privateint[]map;/** * 初始化哈希映射 * 使用数组直接寻址 */publicMyHashMap(){// 初始化数组，所有值设为-1表示不存在map=newint[MAX_KEY+1];for(inti=0;i<=MAX_KEY;i++){map[i]=NOT_EXIST;}}/** * 插入或更新键值对 * * @param key 键 (0 <= key <= 10^6) * @param value 值 (0 <= value <= 10^6) */publicvoidput(intkey,intvalue){map[key]=value;}/** * 获取键对应的值 * * @param key 要查找的键 * @return 如果存在返回对应的值，否则返回-1 */publicintget(intkey){returnmap[key];}/** * 删除键值对 * * @param key 要删除的键 */publicvoidremove(intkey){map[key]=NOT_EXIST;}}

方法二：链地址

importjava.util.LinkedList;importjava.util.List;classMyHashMap{privatestaticfinalintBUCKET_SIZE=1000;privateList<Entry>[]buckets;// 键值对定义privatestaticclassEntry{intkey;intvalue;Entry(intkey,intvalue){this.key=key;this.value=value;}}/** * 初始化哈希映射 * 使用链地址处理冲突 */@SuppressWarnings("unchecked")publicMyHashMap(){// 创建桶数组，每个桶是一个链表buckets=newLinkedList[BUCKET_SIZE];for(inti=0;i<BUCKET_SIZE;i++){buckets[i]=newLinkedList<>();}}/** * 哈希函数：计算键对应的桶索引 */privateinthash(intkey){returnkey%BUCKET_SIZE;}/** * 查找指定键在桶中的条目 */privateEntryfindEntry(intbucketIndex,intkey){List<Entry>bucket=buckets[bucketIndex];for(Entryentry:bucket){if(entry.key==key){returnentry;}}returnnull;}/** * 插入或更新键值对 */publicvoidput(intkey,intvalue){intbucketIndex=hash(key);EntryexistingEntry=findEntry(bucketIndex,key);if(existingEntry!=null){// 键已存在，更新值existingEntry.value=value;}else{// 键不存在，添加新条目buckets[bucketIndex].add(newEntry(key,value));}}/** * 获取键对应的值 */publicintget(intkey){intbucketIndex=hash(key);Entryentry=findEntry(bucketIndex,key);returnentry!=null?entry.value:-1;}/** * 删除键值对 */publicvoidremove(intkey){intbucketIndex=hash(key);List<Entry>bucket=buckets[bucketIndex];// 遍历桶中的条目，找到并删除for(inti=0;i<bucket.size();i++){if(bucket.get(i).key==key){bucket.remove(i);return;}}}}

方法三：优化链地址

classMyHashMap{privatestaticfinalintBUCKET_SIZE=1000;privateNode[]buckets;// 链表节点定义privatestaticclassNode{intkey;intvalue;Nodenext;Node(intkey,intvalue){this.key=key;this.value=value;}}publicMyHashMap(){buckets=newNode[BUCKET_SIZE];}privateinthash(intkey){returnkey%BUCKET_SIZE;}publicvoidput(intkey,intvalue){intbucketIndex=hash(key);Nodehead=buckets[bucketIndex];// 查找是否已存在该键Nodecurrent=head;while(current!=null){if(current.key==key){current.value=value;// 更新值return;}current=current.next;}// 键不存在，在头部插入新节点NodenewNode=newNode(key,value);newNode.next=head;buckets[bucketIndex]=newNode;}publicintget(intkey){intbucketIndex=hash(key);Nodecurrent=buckets[bucketIndex];while(current!=null){if(current.key==key){returncurrent.value;}current=current.next;}return-1;// 未找到}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;}}}

方法四：双重哈希

classMyHashMap{privatestaticfinalintTABLE_SIZE=2069;// 质数privatestaticfinalintEMPTY=-1;privatestaticfinalintDELETED=-2;privateint[]keys;privateint[]values;publicMyHashMap(){keys=newint[TABLE_SIZE];values=newint[TABLE_SIZE];// 初始化所有槽位为空for(inti=0;i<TABLE_SIZE;i++){keys[i]=EMPTY;}}privateinthash1(intkey){returnkey%TABLE_SIZE;}privateinthash2(intkey){// 第二个哈希函数，必须与TABLE_SIZE互质return1+(key%(TABLE_SIZE-1));}publicvoidput(intkey,intvalue){intindex=hash1(key);intstep=hash2(key);// 线性探测寻找空槽位或已存在的键while(keys[index]!=EMPTY&&keys[index]!=DELETED&&keys[index]!=key){index=(index+step)%TABLE_SIZE;}keys[index]=key;values[index]=value;}publicintget(intkey){intindex=hash1(key);intstep=hash2(key);while(keys[index]!=EMPTY){if(keys[index]==key){returnvalues[index];}index=(index+step)%TABLE_SIZE;}return-1;}publicvoidremove(intkey){intindex=hash1(key);intstep=hash2(key);while(keys[index]!=EMPTY){if(keys[index]==key){keys[index]=DELETED;// 标记为已删除return;}index=(index+step)%TABLE_SIZE;}}}

算法分析

• 时间复杂度：
  • 数组直接寻址：所有操作O(1)
  • 链地址：平均O(1)，最坏O(n)（所有键哈希到同一桶）
  • 开放地址：平均O(1)，最坏O(n)
• 空间复杂度：
  • 数组直接寻址：O(10^6)
  • 链地址：O(n)，n为实际存储的键值对数量
  • 开放地址：O(TABLE_SIZE)

测试用例

publicclassTestMyHashMap{publicstaticvoidmain(String[]args){// 测试用例1：标准示例MyHashMapmyHashMap1=newMyHashMap();myHashMap1.put(1,1);myHashMap1.put(2,2);System.out.println("get(1): "+myHashMap1.get(1));// 1System.out.println("get(3): "+myHashMap1.get(3));// -1myHashMap1.put(2,1);// 更新值System.out.println("get(2): "+myHashMap1.get(2));// 1myHashMap1.remove(2);System.out.println("get(2): "+myHashMap1.get(2));// -1System.out.println();// 测试用例2：边界值MyHashMapmyHashMap2=newMyHashMap();myHashMap2.put(0,0);myHashMap2.put(1000000,1000000);System.out.println("get(0): "+myHashMap2.get(0));// 0System.out.println("get(1000000): "+myHashMap2.get(1000000));// 1000000myHashMap2.remove(0);myHashMap2.remove(1000000);System.out.println("get(0): "+myHashMap2.get(0));// -1System.out.println("get(1000000): "+myHashMap2.get(1000000));// -1System.out.println();// 测试用例3：重复操作和更新MyHashMapmyHashMap3=newMyHashMap();myHashMap3.put(5,10);myHashMap3.put(5,20);// 更新myHashMap3.put(5,30);// 再次更新System.out.println("get(5): "+myHashMap3.get(5));// 30myHashMap3.remove(5);myHashMap3.remove(5);// 重复删除System.out.println("get(5): "+myHashMap3.get(5));// -1myHashMap3.put(5,40);// 重新添加System.out.println("get(5): "+myHashMap3.get(5));// 40System.out.println();// 测试用例4：空映射操作MyHashMapmyHashMap5=newMyHashMap();System.out.println("get(42): "+myHashMap5.get(42));// -1myHashMap5.remove(42);// 删除不存在的键System.out.println("get(42): "+myHashMap5.get(42));// -1myHashMap5.put(42,84);System.out.println("get(42): "+myHashMap5.get(42));// 84}}

关键点

1. 哈希函数：

   • 简单取模：key % bucketSize
   • 桶数量：通常选择质数
   • 双重哈希：使用两个哈希函数避免聚集

2. 冲突处理：

   • 链地址：每个桶维护一个链表存储键值对
   • 开放地址：冲突时寻找下一个空槽位
   • 删除标记：开放地址中删除需要特殊标记（DELETED）

3. 更新：

   • 如果键已存在，更新对应的值而不是添加新条目
   • 链地址需要遍历链表查找已存在的键

常见问题

1. 为什么链地址比开放地址更容易实现删除？
   • 链地址中，删除就是从链表中移除节点，不影响其他元素的查找
   • 开放地址中，删除一个元素后，如果设为空，会导致后续元素无法被找到