哈希表介绍
哈希表，也常被称为散列表，这种数据结构精妙地实现了键（Key）与值（Value）之间的映射。只要你提供一个 Key，它就能以接近 O(1) 的时间复杂度，高效地检索出对应的 Value。这背后到底是怎么实现的呢？
其核心在于哈希函数。哈希函数能将任意长度的输入数据，通过特定的哈希算法，转换成固定长度的输出，这个输出值就是哈希值或散列值。哈希表正是依靠哈希函数，完成了从 Key 到数组下标的转换，从而构建起高效的查询基础。
哈希表的读写操作与扩容
1. 写操作
在哈希表中插入新的键值对，也就是写操作，具体是如何实现的？我们把它拆解为两步：
- 第一步：通过哈希函数，将 Key 转换为一个数组下标。
- 第二步：检查这个下标对应的数组位置。如果该位置是空的，没有任何元素，那么这个键值对就会被直接填充进去。
不过，现实往往不如预想中顺利。随着数据量增加，不同的 Key 可能会计算出相同的数组下标，这种情况就是我们常说的 哈希冲突。别担心，解决冲突的经典方法主要有两种：开放寻址法和链表法。
- 开放寻址法：思路很直接，当发现一个位置已经被占用时，就从这个位置开始向后探测，逐一检查，直到找到一个空的槽位，然后将键值对存放进去。
- 链表法：这种方法更为常见。如果新键值对被分配到了一个已被占用的位置，它不会去别处寻找空位，而是直接以当前位置为链表的头节点，将自己作为新节点“挂”在这条链的末尾。每个数组槽位都关联一条链表，所有哈希冲突的元素都在这条链表上排排坐。
2. 读操作
读操作与写操作相对应，过程相对直观：
- 第一步：再次通过哈希函数，依据 Key 找到它本应归属的数组下标。
- 第二步：定位到那个下标位置。如果该位置存储了多个元素（即存在链表），那就不只是简单地取第一个，而是需要顺着链表逐个向下查找，直到找到那个与 Key 完全匹配的节点，并返回它的 Value。
3. 扩容
为什么要扩容？想象一下，如果链表变得越来越长，沿着链表逐个查找的效率自然会下降，这显然不符合我们追求 O(1) 效率的初衷。因此，在合适的时机对哈希表进行扩容就变得至关重要。扩容的决策主要由两个因素共同决定：
- Capacity：哈希表当前的总长度，也就是数组的槽位数量。
- LoadFactor：哈希表的负载因子，这是一个用于衡量哈希表填充程度的关键比例。
扩容的触发条件，通常满足以下公式即可：
HashMap.Size >= Capacity × LoadFactor
当哈希表中的元素数量达到或超过当前容量与负载因子的乘积时，数组就会进行一次扩容。扩容后，通常需要重新计算所有现存元素的位置（即 Rehashing），将它们均匀地分布到新的、更大的数组中，以此来维持高效的查询性能。 | 
发表于 2 小时前
|
查看: 2|
回复: 0
