一、定义哈希表是编程中高频且高效的数据结构核心作用是实现 [ 键-值Key-Value] 的快速映射能把查找、插入、删除的平均时间复杂度做到O(1)这也是它能优化暴力解法双层for循环遍历各种情况具体例子可以见我上一篇文章将时间复杂度从O(n2)到O(n)的关键二、为什么需要哈希表本质是在数组中找值对应元素的过程中执行效率太低了而哈希表的核心优势是把值作为键Key索引作为Value能直接通过值查到对应的索引不用循环查找三、核心原理本质是数组哈希函数冲突解决1.数组--哈希表的基础骨架哈希表的底层都是一个数组也叫「哈希桶」。数组的每个下标桶位对应一个哈希值范围所有 Key-Value 对首先会通过「哈希函数」计算出哈希值然后被分配到对应的数组下标位置。这是哈希表的核心没有数组就没有哈希表的快速寻址能力O(1) 的基础2.哈希函数--核心映射规则哈希表底层是一个普通数组但数组是通过下标访问的而我们的「键Key」可能是数字、字符串等任意类型这时候需要哈希函数把「任意类型的 Key」转换成「数组的合法下标」。举个例子如果 Key 是整数比如nums里的元素值 2、7、11哈希函数可以简单设计为hash(key) key % 数组长度取余运算。比如数组长度是 10key7 → hash (7)7key11 → hash (11)1这样就把 Key 映射到了数组的具体下标。哈希函数要求相同的 Key 必须得到相同的哈希值确定性哈希值要尽可能均匀分布减少冲突计算要快保证 O(1) 效率3.哈希冲突--必须要解决的问题理想情况下每个 Key 应该映射到数组的唯一下标但现实中一定会出现「不同 Key 算出相同哈希值」的情况这就是哈希冲突。比如数组长度 10key7 → hash7key17 → hash7两个不同的 Key 映射到了同一个下标这就是冲突。4.冲突解决--哈希表能用的关键常见的冲突解决方式有两种1链地址法拉链法最常用Java 的HashMap就是用这种方式。原理数组的每个下标位置不再只存一个值而是挂一个「链表或红黑树」。如果多个 Key 映射到同一个下标就把它们依次放到这个链表中。比如下标 7 位置的链表既存 key7值 0又存 key17值 5。挂链表是把所有冲突的Key-Value 对依次串在链表上但如果链表太长比如几十上百个元素查询这个链表的时间会退化成On效率大幅下降因此引出红黑树红黑树的提出是为了解决长链表的效率问题当某个数组下标下的链表长度超过8且数组总长度超过64时链表会自动转换成「红黑树」红黑树是一种平衡二叉树查询 / 插入 / 删除的时间复杂度是 O(logn)远优于长链表的 O(n)反之如果红黑树的元素数量减少到6以下会重新转回链表因为少量元素时链表的开销比红黑树小。2开放寻址法如果当前下标被占用就按规则找下一个空位置比如往后挪 1 位适合数组空间紧凑的场景。四、哈希表的核心操作1.插入(put)MapInteger, Integer map new HashMap(); map.put(key, value);2.查询(containsKeyget)用哈希函数计算complement的哈希值--找到数组对应下标--遍历该位置的链表匹配Key--找到则返回Value没有则返回null// 检查是否存在目标值键 if (map.containsKey(complement)) { // 获取目标值对应的索引值 return map.get(complement); }3.删除(remove)找到Key对应的位置从链表中移除该节点五、关键特性1.时间复杂度平均情况插入 / 查询 / 删除都是 O(1)最坏情况所有 Key 都冲突链表退化成单链表O(n)优化Java 1.8 后当链表长度超过 8会转成红黑树最坏情况优化到 O(logn)。2.无序性哈希表的 Key 是无序的不像数组 / 链表有顺序比如HashMap遍历结果和插入顺序无关如果需要有序用LinkedHashMap。3.不能存重复 Key如果插入相同 Key新的 Value 会覆盖旧的比如map.put(2,0)后再map.put(2,1)最终 Key2 对应 Value1。六、小舟有话说哈希表是数据结构中最重要的知识点一定要掌握它的核心原理能解决大量“快速查找/匹配”类问题希望大家能够多多练习如果觉得这篇文章还不错的话请点点关注下次不迷路~