哈希表与链表组合原理
raw/articles/2026/05/哈希表与链表组合原理
核心要点
1. Golang map 的随机遍历顺序
Golang 的 map 每次遍历顺序都不同，这是故意设计的，目的是防止开发者依赖哈希表的遍历顺序。
实现原理：
- 不触发扩缩容时，底层
table数组的存储顺序是固定的 - 遍历时不是从数组头部开始，而是从一个随机位置开始
- 利用环形数组技巧遍历整个
table数组 - 这样既保证随机性，又不牺牲太多性能
示例遍历顺序变化：
| 1 2 3 4 5
5 | 1 2 3 4
2 3 4 5 | 1
| 1 2 3 4 5
2. Java LinkedHashMap 的插入顺序维护
Java 的 LinkedHashMap 可以按照插入顺序遍历键值对，底层使用了哈希链表结构。
哈希链表（Hash Linked List）：
- 组合了哈希表和双向链表两种数据结构
- 兼具哈希表 O(1) 的增删查改效率
- 同时可以像链表一样保持键的插入顺序
关键概念
| 概念 | 说明 |
|---|---|
| 哈希链表 | 哈希表 + 链表组合结构，维护插入顺序的同时保持 O(1) 操作 |
| LinkedHashMap | Java 标准库提供的有序哈希表实现 |
| 环形数组遍历 | 从随机位置开始，利用模运算循环遍历数组的技巧 |
相关概念
相关实体
- labuladong：算法学习平台作者