FHCY-Study05-哈希表
type
status
date
slug
summary
tags
category
icon
password
哈希表（Hash Table）是一种基于哈希函数实现的高效键值对（key-value）存储数据结构，广泛应用于快速查找、插入和删除操作。
HashMap 工作原理简述:
- 通过 key 的
hashCode()计算哈希值，再通过扰动函数计算桶下标。
- 桶为链表或红黑树（当链表过长时转换为红黑树以提高性能）。
- 插入时，如果冲突发生，元素加入链表尾部（或红黑树）。
- 查找时根据桶找到对应链表或树，逐个匹配 key。
- 通过 哈希函数 将键（key）映射到数组的索引（桶 bucket）位置。
- 理想情况下，哈希函数能将键均匀分布，查找时间接近。
- 由于哈希冲突，实际查找可能需要处理冲突。
哈希冲突处理方式
1️⃣ 链地址法（Separate Chaining）
- 每个桶存储一个链表（或其他结构），所有哈希到同一桶的元素都放在该链表中。
- 查找时遍历链表。
2️⃣ 开放地址法（Open Addressing）
- 当发生冲突时，寻找下一个空桶存放元素。
- 常用探查策略：
- 线性探查（Linear Probing）
- 二次探查（Quadratic Probing）
- 双重哈希（Double Hashing）
Java 中的哈希表
类 | 特点 |
HashMap | 线程不安全，允许 null key/value |
Hashtable | 线程安全，不允许 null key/value |
LinkedHashMap | 保持插入顺序或访问顺序 |
ConcurrentHashMap | 高并发环境下的线程安全实现 |
上一篇
04-队列
下一篇
06-二叉树
Loading...