文章目录一. 什么是哈希表?二. 哈希冲突与解决1. 冲突2. 解决方案(1) 预防冲突 - 优化哈希函数(2) 预防冲突 - 调节负载因子(3) 解决策略 - 闭散列1 线性探测2 二次探测(4) 解决策略 - 开散列 - 链地址法三. 简单实现1. 初始化2. 添加 put3. 获取 get4. 扩容 resize5. 删除 remove四. 习题复习 力扣 [138. 随机链表的复制](https://leetcode.cn/problems/copy-list-with-random-pointer/submissions/755167716/)1. 题目解析2. 算法原理3. 代码带大家理解哈希表的组成原理到手把手实现一. 什么是哈希表?通过对前面链表、顺序表、栈、队列、堆等等数据结构的学习, 会发现它们会在特定情况下 查找/修改 的时间复杂度会到 O(N), 例如链表的删除和顺序表的查找。而我们可能会有些疑问有没有一种数据结构可以让增删查改的时间复杂度都是O(1)。有的, 就是哈希表哈希表是一种最常见最重要的一种数据结构, 底层是通过数组链表/树实现的键值对结构, 哈希表增删查改的平均时间复杂度都为O(1), 可以说是当之无愧的性能王者组成部分作用key元素对应的唯一标识, 不可重复value元素的本身值, 可重复hash函数通过哈希函数将key转化为哈希值, 以此来实现快速定位负载因子哈希表的最大负载度, 与存入的元素个数成正比二. 哈希冲突与解决1. 冲突哈希表的底层是数组, 数组是通过地址来进行存储与查找元素的, 因此在哈希表中对于元素的存储首先也要根据关键字 key 计算哈希地址 , 而当有两个数据元素的 key 不相同时(假设为 k1、k2), 但通过相同的哈希函数计算的道德哈希值相等, 这种现象就是哈希冲突 (或叫哈希碰撞)2. 解决方案分为两类, 一类是预防冲突的方案, 另一类是冲突发生后的解决策略(1) 预防冲突 - 优化哈希函数一个设计合理的哈希函数能大幅减少冲突概率, 即通过哈希函数将元素的 key 均匀地分布到各个位置经典哈希函数 -除留余数法:hash(k) k mod m, k 对 m 进行取余, 其中 k 为 元素的关键字, m 为最接近哈希表长度的素数 (注意: m≤len)但我们要知道: 随着元素的增多, 必然至少有两个键映射到同一个地址, 因此冲突是不可彻底避免的, 优化哈希函数能做的就是尽量降低冲突概率(2) 预防冲突 - 调节负载因子当要存储的元素越来越多时, 哈希表中可用的空间会越来越小, 负载因子也会逐渐变大, 这时发生冲突的概率会变大, 因此我们需要对哈希表适时的扩容。对于扩容时机的把控也很重要, 过早会导致空间浪费, 过晚则会导致冲突概率过大, 因此负载因子的设定极为重要(3) 解决策略 - 闭散列闭散列别名又叫为开放定址法和内散列, 指的是将冲突元素仍然放在哈希表数组的内部, 常见的就是线性探测(一次探测) 与 二次探测1 线性探测发生哈希冲突时, 将冲突的 key 放入到下一个空位置去, 查找下一个位置的方法为: hash(k, i) (hash(k) i) mod m, 其中 k 为 元素的关键字, m 为哈希表的长度, i 为第几次探测该位置(i从0开始)缺点:会将冲突的数据堆积到一起, 连续占用一片区域导致探测(搜索)变长2 二次探测为了避免线性探测的连续堆积问题, 可以将查找下一个位置的方法变为: hash(k, i) (hash(k) i²) mod m, 其中 k 为 元素的关键字, m 为哈希表的长度, i 为第几次探测该位置(i从0开始)(4) 解决策略 - 开散列 - 链地址法开散列指的是将冲突元素放在外部的容器中, 哈希表数组的每个槽叫一个“桶, 每个槽不直接存一个元素而是存一个桶的入口引用, 常见的有链地址法(开链法)Java 对于哈希桶的实现, 不局限于单一的数据结构, 而是当冲突严重时, 会将单链表转化为红黑树, 以此来提高查询效率(当桶内链表长度 8 且数组容量 64 时)三. 简单实现这里我们实现的是链地址法, 并且假设所有数值都是整型1. 初始化哈希表底层为数组, 数组里面存储的是单链表头结点的引用, 所以在内部要有节点, 链表的节点又要有 key 和 value 以及 next 域负载因子我们设置为 0.75publicstaticclassNode{privateintkey;privateintvalue;privateNodenext;publicNode(intkey,intvalue){this.keykey;this.valuevalue;}}publicMyMap(){arraynewNode[10];size0;}// 负载因子privatestaticfinaldoubleDEFAULT_LOAD_FACTOR0.75;// 哈希表元素的个数privateintsize;Node[]array;2. 添加 put计算地址(哈希值)key存在key不存在≥负载因子keyindex遍历挂载的链表修改并返回旧值头插进链表扩容publicintput(intkey,intvalue){intindexhash(key);// 存在就修改值for(Nodecurarray[index];cur!null;curcur.next){if(cur.keykey){intoldValuecur.value;cur.valuevalue;returnoldValue;}}// 不存在就头插法(写起来简单)NodenodenewNode(key,value);node.nextarray[index];array[index]node;size;if(loadFactor()DEFAULT_LOAD_FACTOR){resize();}return-0x3fffffff;}3. 获取 get对 key 哈希得到地址, 遍历链表进行寻找publicintget(intkey){intindexhash(key);for(Nodecurarray[index];cur!null;curcur.next){if(cur.keykey){returncur.value;}}return-0x3fffffff;}4. 扩容 resize创建 2 倍容量的新的节点数组遍历数组的每个槽, 再遍历槽中的链表重新计算所有节点 key 的哈希地址, 映射到新的哈希表上(头插法)映射过程中唯一注意的就是节点的 next 域可能会丢失, 需要提前存储起来// 扩充哈希表大小privatevoidresize(){Node[]newArraynewNode[array.length*2];for(Nodenode:array){Nodenext;for(Nodecurnode;cur!null;curnext){intindexhash(cur.key);nextcur.next;cur.nextnewArray[index];newArray[index]cur;}}arraynewArray;}5. 删除 remove先获取 key 的哈希地址遍历链表找到要删除的节点要注意头结点被删除时需要特殊处理删除必须维护前置节点 prevpublicintremove(intkey){intindexhash(key);Nodeprevarray[index];for(Nodecurarray[index];cur!null;curcur.next){if(cur.keykey){if(curprev){array[index]cur.next;}prev.nextcur.next;cur.nextnull;size--;returncur.value;}prevcur;}return-0x3fffffff;}四. 习题复习 力扣138. 随机链表的复制1. 题目解析意思就是创建一个新链表新链表中每个新节点的 next 和 random 域, 所指向的新节点的值, 要和原链表中节点一致下面是效果图2. 算法原理遍历链表, 创建新节点作为val,旧节点作为key,存储到哈希表遍历哈希表, 找到新旧节点的映射关系, 来对域进行修改3. 代码/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val val; this.next null; this.random null; } } */classSolution{publicNodecopyRandomList(Nodehead){MapNode,NodehashnewHashMap();for(Nodecurhead;cur!null;curcur.next){NodenodenewNode(cur.val);hash.put(cur,node);}for(Map.EntryNode,Nodee:hash.entrySet()){NodeoldNodee.getKey();NodenewNodee.getValue();newNode.nexthash.get(oldNode.next);newNode.randomhash.get(oldNode.random);}returnhash.get(head);}}