企业官网建设流程全解析

目录

一、哈希表基础原理

1.1 哈希冲突（哈希碰撞）

1.2 两种解决哈希冲突的思路

② 开散列｜哈希桶（链地址法，HashMap 采用）

二、负载因子与扩容机制

三、手写简易哈希桶实现

手写代码关键点总结

四、简单实战：HashMap & HashSet 基础使用

五、横向对比

总结

上一篇们提到了TreeMap、TreeSet，底层依托红黑树实现，元素天然有序，增删查时间复杂度 O (logN)。但很多业务场景，我们并不关心元素顺序，只想要更快的查找速度，这时候就该哈希表登场，也就是我们今天的主角：HashMap和HashSet。

日常开发中，查找是一个非常高频的操作。 如果用普通数组遍历查找，时间复杂度 O (n)，数据量一大就会变得很慢； 二分查找虽然可以做到 O (logn)，但它依赖有序数组，更适合静态数据，面对频繁增删的动态数据就很无力。

红黑树解决了动态查找的问题，但是每一次查找，都要在树节点之间不断比较大小，依旧存在开销。 那有没有办法，不做多次比较，直接算出数据存放在哪里，一步就找到目标元素？哈希表就是为了这个理想目标诞生的。

简单区分两套集合：

• Tree 系列（TreeMap/TreeSet）：依靠元素大小比较完成存储，输出有序；
• Hash 系列（HashMap/HashSet）：依靠哈希函数计算存储下标完成存储，不保证顺序，但平均性能更好。

一、哈希表基础原理

哈希表的核心，就是哈希函数。 哈希函数接收 key，计算出一个整数，这个整数就是底层数组的下标。

• 插入元素：key 经过哈希函数计算得到数组下标，把数据放到下标对应的位置；
• 查找元素：传入要查找的 key，用同一个哈希函数算出下标，直接到对应位置读取数据。

理想状态下，插入、删除、查询都可以达到 O (1)。

1.1 哈希冲突（哈希碰撞）

理想很美好，但现实会遇到一个问题：哈希冲突。

不同的 key，经过哈希函数运算，得到了完全一样的数组下标，这种现象就叫哈希冲突，发生冲突的 key 被叫做同义词。

冲突是没有办法彻底消灭的。 key 的取值范围可以无限大，但是哈希表底层数组的容量是有限的，必然会出现多个 key 映射到同一个下标的情况。我们只能优化哈希函数，降低冲突发生的概率，做不到完全杜绝。

举个最简单的例子，哈希函数hash(key) = key%10。 4对10取模等于 4，14对10取模也等于 4，key=4 和 key=14 就发生了哈希冲突。

1.2 两种解决哈希冲突的思路

现在有了冲突，我们该怎么处理？主流分为两大类方案：

采⽤闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。⽐如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采⽤标记的伪删除法来删除⼀个元素。

2.二次探测

线性探测的缺陷是产⽣冲突的数据堆积在⼀块， 这与其找下⼀个空位置有关系， 因为找空位置的⽅式 就是挨着往后逐个去找， 因此⼆次探测为了避免该问题， 找下⼀个空位置的⽅法为： Hi = ( H0 + i2 )% m, 或者： Hi = ( H0 - i2 )% m其中： i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进⾏计算得到的位置， m是表的⼤⼩。 对于2.1中如果要插⼊44， 产⽣冲突， 使⽤解决后的情况 为：

② 开散列｜哈希桶（链地址法，HashMap 采用）

开散列法⼜叫链地址法(开链法)，⾸先对关键码集合⽤散列函数计算散列地址，具有相同地址的关键码归于同⼀⼦集合，每⼀个⼦集合称为⼀个桶，各个桶中的元素通过⼀个单链表链接起来，各链表的头结点存储在哈希表中

从上图可以看出，开散列中每个桶中放的都是发⽣哈希冲突的元素。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

二、负载因子与扩容机制

既然冲突不可避免，那我们怎么控制冲突的概率？这里就要引入负载因子。

负载因子 = 哈希表中有效元素的个数 / 底层数组的长度

负载因子和冲突率的关系粗略演⽰

负载因子用来描述哈希表数组的拥挤程度：

• 负载因子越大，数组存放的数据越多，冲突概率会急剧上升，查询性能下降；
• 负载因子越小，冲突越少，但是数组大量空间闲置，造成内存浪费。

HashMap默认负载因子阈值是0.75，这是工程上时间开销与内存开销的一个平衡点。

当元素个数 > 数组长度 * 0.75，就会触发扩容 rehash：

1. 创建一个长度为原来两倍的新数组；
2. 遍历旧哈希表每一个桶中的全部节点，用新数组的长度重新计算哈希下标；
3. 将节点挂载到新数组对应的桶位置；
4. 将底层数组引用指向新数组，旧数组等待垃圾回收。

注意：扩容不是简单复制数据，旧的哈希下标在新数组中不再生效，所有节点必须重新计算位置。

三、手写简易哈希桶实现

下面实现一个简化版开散列哈希表，完成 put 插入、get 查询、remove 删除、自动扩容。

package hash; //链表节点，存储key‑value class MyHashNode{ public int key; public int value; public MyHashNode next; public MyHashNode(int key,int value){ this.key=key; this.value=value; } } public class MyHashTable { //底层数组，每个位置存放链表头结点，初始为null private MyHashNode[] array=new MyHashNode[1000]; private int size=0; //哈希表里面有效元素数量 private static final double LOAD_FACTOR = 0.75; //哈希函数：除留余数法，计算数组下标 private int myHashCode(int key){ return key % array.length; } //插入：key存在就更新value；不存在则头插新节点 public void put(int key,int value){ int index=myHashCode(key); MyHashNode cur = array[index]; //遍历整条链表，包含尾结点 while(cur != null){ if(cur.key == key){ cur.value = value; return; } cur = cur.next; } //key不存在，执行头插 MyHashNode newNode=new MyHashNode(key,value); newNode.next = array[index]; array[index] = newNode; size++; //达到负载因子阈值，触发扩容 if(getLoadFactor()>LOAD_FACTOR){ realloc(); } } //计算负载因子 private double getLoadFactor(){ return ((double) size) / array.length; } //扩容rehash，迁移全部节点至新数组 private void realloc(){ MyHashNode[] newArray=new MyHashNode[array.length*2]; for(int i=0;i<array.length;i++){ MyHashNode cur = array[i]; while(cur != null){ MyHashNode next = cur.next; //提前保存后继，防止迁移时链表断裂 int newIndex = cur.key % newArray.length; //头插到新数组对应桶 cur.next = newArray[newIndex]; newArray[newIndex] = cur; cur = next; } } array = newArray; } //根据key查询，找不到返回null public Integer get(int key){ int index = myHashCode(key); MyHashNode cur = array[index]; while(cur != null){ if(cur.key == key){ return cur.value; } cur = cur.next; } return null; } //删除指定key对应的节点 public void remove(int key){ int index = myHashCode(key); MyHashNode head = array[index]; //当前桶为空，直接返回 if(head == null){ return; } //待删除的是链表头结点 if(head.key == key){ array[index] = head.next; size--; return; } //删除中间、尾部节点 MyHashNode prev = head; MyHashNode cur = head.next; while(cur != null){ if(cur.key == key){ prev.next = cur.next; size--; return; } prev = cur; cur = cur.next; } } //简单测试 public static void main(String[] args) { MyHashTable table = new MyHashTable(); table.put(1,100); table.put(1001,200); //产生哈希冲突 System.out.println(table.get(1)); System.out.println(table.get(1001)); table.remove(1); System.out.println(table.get(1)); } }

手写代码关键点总结

1. 数组存储链表头结点，数组元素初始值为null；
2. 遍历链表判断条件cur != null，避免丢失尾节点；
3. 扩容迁移节点前，要先保存 next 引用，防止链表断裂；
4. 负载因子 0.75，超过阈值执行扩容 rehash。

四、简单实战：HashMap & HashSet 基础使用

import java.util.HashMap; import java.util.HashSet; public class HashDemo { public static void main(String[] args) { //HashMap 键值对示例 HashMap<String,Integer> hashMap = new HashMap<>(); hashMap.put("张三",18); hashMap.put("李四",20); //key重复，会覆盖旧的value hashMap.put("张三",19); System.out.println(hashMap.get("张三")); //HashSet 去重示例 HashSet<String> hashSet = new HashSet<>(); hashSet.add("苹果"); hashSet.add("香蕉"); hashSet.add("苹果"); //重复元素，添加失败 System.out.println(hashSet); } }

五、横向对比

表格

总结

1. 哈希表通过哈希函数直接计算存储下标，目标实现平均 O (1) 的动态查找；哈希冲突无法彻底消除，Java HashMap 使用哈希桶（开散列）处理冲突，链表过长转换红黑树优化性能。
2. 负载因子控制哈希表拥挤程度，默认阈值 0.75；触发扩容之后全部节点需要重新计算哈希下标迁移。
3. HashSet 底层封装 HashMap，只利用 key 实现去重，所以本身是无序集合。
4. 哈希集合判等分为两步：hashCode 定位桶 + equals 比较对象内容。自定义类做 key，两个方法必须成对重写。
5. 选型小技巧：业务需要排序优先选 Tree 系列；追求读写速度不在乎顺序选 Hash；需要记住插入顺序使用 LinkedHash 系列。