第一章 网站建设基本概述,凡科建站代理登录,广州最近流行传染疾病,wordpress 模板函数文章目录题目标题和出处难度题目描述要求示例数据范围前言解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目
标题和出处
标题#xff1a;设计哈希映射
出处#xff1a;706. 设计哈希映射
难度
3 级
题目描述
要求
不使用任何内建的哈希表库设计一个…
文章目录题目标题和出处难度题目描述要求示例数据范围前言解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目
标题和出处
标题设计哈希映射
出处706. 设计哈希映射
难度
3 级
题目描述
要求
不使用任何内建的哈希表库设计一个哈希映射。
实现 MyHashMap\texttt{MyHashMap}MyHashMap 类
MyHashMap()\texttt{MyHashMap()}MyHashMap() 用空映射初始化对象。voidput(intkey,intvalue)\texttt{void put(int key, int value)}void put(int key, int value) 向哈希映射插入一个键值对 (key,value)\texttt{(key, value)}(key, value)。如果 key\texttt{key}key 已经存在于映射中则更新其对应的值 value\texttt{value}value。intget(intkey)\texttt{int get(int key)}int get(int key) 返回特定的 key\texttt{key}key 所映射的 value\texttt{value}value如果映射中不包含 key\texttt{key}key 的映射返回 -1\texttt{-1}-1。voidremove(key)\texttt{void remove(key)}void remove(key) 如果映射中存在 key\texttt{key}key 的映射则移除 key\texttt{key}key 和它所对应的 value\texttt{value}value。
示例
示例 1
输入 [MyHashMap,put,put,get,get,put,get,remove,get]\texttt{[MyHashMap, put, put, get, get, put, get, remove, get]}[MyHashMap, put, put, get, get, put, get, remove, get] [[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]\texttt{[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]}[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] 输出 [null,null,null,1,-1,null,1,null,-1]\texttt{[null, null, null, 1, -1, null, 1, null, -1]}[null, null, null, 1, -1, null, 1, null, -1] 解释 MyHashMapmyHashMapnewMyHashMap();\texttt{MyHashMap myHashMap new MyHashMap();}MyHashMap myHashMap new MyHashMap(); myHashMap.put(1,1);\texttt{myHashMap.put(1, 1);}myHashMap.put(1, 1); // myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1]]\texttt{[[1,1]]}[[1,1]] myHashMap.put(2,2);\texttt{myHashMap.put(2, 2);}myHashMap.put(2, 2); // myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1],[2,2]]\texttt{[[1,1], [2,2]]}[[1,1], [2,2]] myHashMap.get(1);\texttt{myHashMap.get(1);}myHashMap.get(1); // 返回 1\texttt{1}1myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1],[2,2]]\texttt{[[1,1], [2,2]]}[[1,1], [2,2]] myHashMap.get(3);\texttt{myHashMap.get(3);}myHashMap.get(3); // 返回 -1\texttt{-1}-1未找到myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1],[2,2]]\texttt{[[1,1], [2,2]]}[[1,1], [2,2]] myHashMap.put(2,1);\texttt{myHashMap.put(2, 1);}myHashMap.put(2, 1); // myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1],[2,1]]\texttt{[[1,1], [2,1]]}[[1,1], [2,1]]更新已有的值 myHashMap.get(2);\texttt{myHashMap.get(2);}myHashMap.get(2); // 返回 1\texttt{1}1myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1],[2,1]]\texttt{[[1,1], [2,1]]}[[1,1], [2,1]] myHashMap.remove(2);\texttt{myHashMap.remove(2);}myHashMap.remove(2); // 删除键为 2\texttt{2}2 的数据myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1]]\texttt{[[1,1]]}[[1,1]] myHashMap.get(2);\texttt{myHashMap.get(2);}myHashMap.get(2); // 返回 -1\texttt{-1}-1未找到myHashMap\texttt{myHashMap}myHashMap 现在为 [[1,1]]\texttt{[[1,1]]}[[1,1]]
数据范围
0≤key≤106\texttt{0} \le \texttt{key} \le \texttt{10}^\texttt{6}0≤key≤106最多调用 104\texttt{10}^\texttt{4}104 次 put\texttt{put}put、get\texttt{get}get 和 remove\texttt{remove}remove
前言
这道题和「设计哈希集合」非常相似区别在于这道题存储的不是 key\textit{key}key 本身而是 (key,value)(\textit{key}, \textit{value})(key,value) 的键值对。这道题也可以使用「设计哈希集合」的解法。
解法一
思路和算法
由于 key\textit{key}key 和 value\textit{value}value 的取值范围是 [0,106][0, 10^6][0,106]因此可以创建长度为 106110^6 11061 的整型数组表示哈希表数组中的下标为 key\textit{key}key 的元素值表示 key\textit{key}key 映射的 value\textit{value}valuevalue≥0\textit{value} \ge 0value≥0 表示存在 key\textit{key}key 的映射value0\textit{value} 0value0 表示不存在 key\textit{key}key 的映射当 value0\textit{value} 0value0 时一定有 value−1\textit{value} -1value−1。
构造方法中将数组初始化为长度 106110^6 11061 的数组并将数组中的全部元素初始化为 −1-1−1。
对于 put\textit{put}put 操作将数组中的下标为 key\textit{key}key 的元素设为 value\textit{value}value。
对于 get\textit{get}get 操作返回数组中的下标为 key\textit{key}key 的元素。
对于 remove\textit{remove}remove 操作将数组中的下标为 key\textit{key}key 的元素设为 −1-1−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(C)O(C)各项操作的时间复杂度都是 O(1)O(1)O(1)其中 CCC 是 key\textit{key}key 的取值范围的元素个数这道题中 C1061C 10^6 1C1061。 构造方法需要创建长度为 CCC 的数组并将每个元素设为初始值时间复杂度是 O(C)O(C)O(C)。 各项操作只需要对数组中的一个元素赋值或返回元素值时间复杂度是 O(1)O(1)O(1)。 空间复杂度O(C)O(C)O(C)其中 CCC 是 key\textit{key}key 的取值范围的元素个数这道题中 C1061C 10^6 1C1061。需要创建长度为 CCC 的数组表示哈希集合。
解法二
思路和算法
哈希表的常见实现方法是链表数组数组的每个下标对应哈希函数可以映射到的索引当出现哈希冲突时使用链地址法解决哈希冲突。
用 BASE\textit{BASE}BASE 表示链表数组的长度则可以使用一个简单的哈希函数hash(x)xmodBASE\text{hash}(x) x \bmod \textit{BASE}hash(x)xmodBASE每个键经过哈希函数映射之后的值一定在范围 [0,BASE−1][0, \textit{BASE} - 1][0,BASE−1] 内。为了将哈希函数的值尽可能均匀分布降低哈希冲突的频率链表数组的长度应选择质数。此处取链表数组的长度为 101310131013。
由于哈希表存储的元素包含键和值因此链表中存储的元素为键值对。
构造方法中将链表数组初始化为长度 BASE\textit{BASE}BASE 的链表数组并将链表数组中的全部元素初始化为空链表。
对于各项操作首先计算 key\textit{key}key 对应的哈希值得到链表数组的下标根据下标在链表数组中得到相应的链表然后在链表中执行相应操作。
对于 put\textit{put}put 操作在链表数组中得到相应的链表之后遍历链表如果遇到元素的键等于 key\textit{key}key 则将元素的值设为 value\textit{value}value 并直接返回如果遍历结束没有遇到元素的键等于 key\textit{key}key 则在链表末尾添加元素 (key,value)(\textit{key}, \textit{value})(key,value)。
对于 get\textit{get}get 操作在链表数组中得到相应的链表之后遍历链表如果遇到元素的键等于 key\textit{key}key 则返回元素的值如果遍历结束没有遇到元素的键等于 key\textit{key}key 则返回 −1-1−1。
对于 remove\textit{remove}remove 操作在链表数组中得到相应的链表之后遍历链表如果遇到元素的键等于 key\textit{key}key 则将其删除如果遍历结束没有遇到元素的键等于 key\textit{key}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 LinkedListEntry[] map;public MyHashMap() {map new LinkedList[BASE];for (int i 0; i BASE; i) {map[i] new LinkedListEntry();}}public void put(int key, int value) {int index key % BASE;LinkedListEntry list map[index];IteratorEntry 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;LinkedListEntry list map[index];IteratorEntry 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;LinkedListEntry list map[index];IteratorEntry iterator list.iterator();while (iterator.hasNext()) {Entry entry iterator.next();if (entry.getKey() key) {iterator.remove();break;}}}
}复杂度分析 时间复杂度构造方法的时间复杂度是 O(BASE)O(\textit{BASE})O(BASE)各项操作的时间复杂度都是 O(nBASE)O\Big(\dfrac{n}{\textit{BASE}}\Big)O(BASEn)其中 nnn 是哈希集合中的元素个数BASE\textit{BASE}BASE 是链表数组的长度。 构造方法需要创建长度为 BASE\textit{BASE}BASE 的数组并将每个元素设为初始值时间复杂度是 O(BASE)O(\textit{BASE})O(BASE)。 各项操作需要根据哈希函数计算哈希值然后遍历链表。计算哈希值需要 O(1)O(1)O(1) 的时间假设哈希值分布均匀每个链表的平均长度是 O(nBASE)O\Big(\dfrac{n}{\textit{BASE}}\Big)O(BASEn)因此需要 O(nBASE)O\Big(\dfrac{n}{\textit{BASE}}\Big)O(BASEn) 的时间遍历哈希表。 空间复杂度O(nBASE)O(n \textit{BASE})O(nBASE)其中 nnn 是哈希集合中的元素个数BASE\textit{BASE}BASE 是链表数组的长度。存储 nnn 个元素需要 O(n)O(n)O(n) 的空间链表数组需要 O(BASE)O(\textit{BASE})O(BASE) 的空间。
