哈希表题目：设计哈希映射

题目

标题和出处

标题：设计哈希映射

出处：706. 设计哈希映射

难度

3 级

题目描述

要求

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

实现 $\text{MyHashMap}$ 类：

• $\text{MyHashMap()}$ 用空映射初始化对象。
• $\text{void put(int key, int value)}$ 向哈希映射插入一个键值对 $\text{(key, value)}$。如果 $\text{key}$ 已经存在于映射中，则更新其对应的值 $\text{value}$。
• $\text{int get(int key)}$ 返回特定的 $\text{key}$ 所映射的 $\text{value}$；如果映射中不包含 $\text{key}$ 的映射，返回 $\text{-1}$。
• $\text{void remove(key)}$ 如果映射中存在 $\text{key}$ 的映射，则移除 $\text{key}$ 和它所对应的 $\text{value}$。

示例

示例 1：

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

数据范围

• $\text{0}\le \text{key}\le {\text{10}}^{\text{6}}$
• 最多调用 ${\text{10}}^{\text{4}}$ 次 $\text{put}$、$\text{get}$ 和 $\text{remove}$

前言

这道题和「设计哈希集合」非常相似，区别在于这道题存储的不是 $\text{key}$ 本身，而是 $(\text{key},\text{value})$ 的键值对。这道题也可以使用「设计哈希集合」的解法。

解法一

思路和算法

由于 $\text{key}$ 和 $\text{value}$ 的取值范围是 $[0,10^6]$，因此可以创建长度为 $10^6+1$ 的整型数组表示哈希表，数组中的下标为 $\text{key}$ 的元素值表示 $\text{key}$ 映射的 $\text{value}$，$\text{value}\ge 0$ 表示存在 $\text{key}$ 的映射，$\text{value}<0$ 表示不存在 $\text{key}$ 的映射，当 $\text{value}<0$ 时一定有 $\text{value}=-1$。

构造方法中，将数组初始化为长度 $10^6+1$ 的数组，并将数组中的全部元素初始化为 $-1$。

对于 $\text{put}$ 操作，将数组中的下标为 $\text{key}$ 的元素设为 $\text{value}$。

对于 $\text{get}$ 操作，返回数组中的下标为 $\text{key}$ 的元素。

对于 $\text{remove}$ 操作，将数组中的下标为 $\text{key}$ 的元素设为 $-1$。

需要说明的是，该解法虽然实现简单，但是不适合在面试中使用。

代码

class MyHashMap {int[] map;public MyHashMap() {map = new int[1000001];Arrays.fill(map, -1);}public void put(int key, int value) {map[key] = value;}public int get(int key) {return map[key];}public void remove(int key) {map[key] = -1;}
}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(C)$，各项操作的时间复杂度都是 $O(1)$，其中 $C$ 是 $\text{key}$ 的取值范围的元素个数，这道题中 $C=10^6+1$。
  构造方法需要创建长度为 $C$ 的数组并将每个元素设为初始值，时间复杂度是 $O(C)$。
  各项操作只需要对数组中的一个元素赋值或返回元素值，时间复杂度是 $O(1)$。

• 空间复杂度：$O(C)$，其中 $C$ 是 $\text{key}$ 的取值范围的元素个数，这道题中 $C=10^6+1$。需要创建长度为 $C$ 的数组表示哈希集合。

解法二

思路和算法

哈希表的常见实现方法是链表数组，数组的每个下标对应哈希函数可以映射到的索引，当出现哈希冲突时，使用链地址法解决哈希冲突。

用 $\text{BASE}$ 表示链表数组的长度，则可以使用一个简单的哈希函数：$\text{hash}(x)=x\mathrm{mod}\text{BASE}$，每个键经过哈希函数映射之后的值一定在范围 $[0,\text{BASE}-1]$ 内。为了将哈希函数的值尽可能均匀分布，降低哈希冲突的频率，链表数组的长度应选择质数。此处取链表数组的长度为 $1013$。

由于哈希表存储的元素包含键和值，因此链表中存储的元素为键值对。

构造方法中，将链表数组初始化为长度 $\text{BASE}$ 的链表数组，并将链表数组中的全部元素初始化为空链表。

对于各项操作，首先计算 $\text{key}$ 对应的哈希值，得到链表数组的下标，根据下标在链表数组中得到相应的链表，然后在链表中执行相应操作。

对于 $\text{put}$ 操作，在链表数组中得到相应的链表之后，遍历链表，如果遇到元素的键等于 $\text{key}$ 则将元素的值设为 $\text{value}$ 并直接返回，如果遍历结束没有遇到元素的键等于 $\text{key}$ 则在链表末尾添加元素 $(\text{key},\text{value})$。

对于 $\text{get}$ 操作，在链表数组中得到相应的链表之后，遍历链表，如果遇到元素的键等于 $\text{key}$ 则返回元素的值，如果遍历结束没有遇到元素的键等于 $\text{key}$ 则返回 $-1$。

对于 $\text{remove}$ 操作，在链表数组中得到相应的链表之后，遍历链表，如果遇到元素的键等于 $\text{key}$ 则将其删除，如果遍历结束没有遇到元素的键等于 $\text{key}$ 则不执行任何操作。

实现方面，为了提升运行效率，使用迭代器遍历链表和执行删除操作。

代码

class MyHashMap {private class Entry {private int key;private int value;public Entry(int key, int value) {this.key = key;this.value = value;}public int getKey() {return key;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}}private static final int BASE = 1013;private LinkedList<Entry>[] map;public MyHashMap() {map = new LinkedList[BASE];for (int i = 0; i < BASE; i++) {map[i] = new LinkedList<Entry>();}}public void put(int key, int value) {int index = key % BASE;LinkedList<Entry> list = map[index];Iterator<Entry> iterator = list.iterator();while (iterator.hasNext()) {Entry entry = iterator.next();if (entry.getKey() == key) {entry.setValue(value);return;}}list.offerLast(new Entry(key, value));}public int get(int key) {int index = key % BASE;LinkedList<Entry> list = map[index];Iterator<Entry> iterator = list.iterator();while (iterator.hasNext()) {Entry entry = iterator.next();if (entry.getKey() == key) {return entry.getValue();}}return -1;}public void remove(int key) {int index = key % BASE;LinkedList<Entry> list = map[index];Iterator<Entry> iterator = list.iterator();while (iterator.hasNext()) {Entry entry = iterator.next();if (entry.getKey() == key) {iterator.remove();break;}}}
}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(\text{BASE})$，各项操作的时间复杂度都是 $O\left(\frac{n}{\text{BASE}}\right)$，其中 $n$ 是哈希集合中的元素个数，$\text{BASE}$ 是链表数组的长度。
  构造方法需要创建长度为 $\text{BASE}$ 的数组并将每个元素设为初始值，时间复杂度是 $O(\text{BASE})$。
  各项操作需要根据哈希函数计算哈希值，然后遍历链表。计算哈希值需要 $O(1)$ 的时间，假设哈希值分布均匀，每个链表的平均长度是 $O\left(\frac{n}{\text{BASE}}\right)$，因此需要 $O\left(\frac{n}{\text{BASE}}\right)$ 的时间遍历哈希表。

• 空间复杂度：$O(n+\text{BASE})$，其中 $n$ 是哈希集合中的元素个数，$\text{BASE}$ 是链表数组的长度。存储 $n$ 个元素需要 $O(n)$ 的空间，链表数组需要 $O(\text{BASE})$ 的空间。