哈希表

HashMap

底层实现

• HashMap内部维护一个节点数组，这是主体结构，数组的每个位置被称为“桶”。
  • 数组：数组是哈希表的基础。当创建一个HashMap时，系统会初始化一个具有一定容量的数组。每个数组元素可以存储一个键值对节点。
  • 链表：当两个或多个不同的Key经过哈希计算后，得到了相同的数组索引时，就会发生“哈希冲突”。为了解决这个问题，HashMap采用了“链地址法”。即将所有哈希冲突的键值对以链表的形式存储在同一个桶中。
  • 红黑树：在早期的Java版本中，即使哈希冲突严重，也只会使用链表。这会导致在极端情况下（所有键都映射到同一个桶），HashMap的性能会从O(1)退化到O(n)，相当于一个链表。为了优化这个问题，当一个桶中的链表长度超过一个特定阈值时，并且哈希表的总容量大于等于64时，这个链表就会被转化成一个红黑树。红黑树是一种自平衡的二叉查找树，其查找、插入和删除的时间复杂度都能保持在O(logn)，极大地提升了在哈希冲突严重时的性能。

关键工作流程

put(key,value)

1. 计算哈希值：调用key的hashcode()方法得到一个原始哈希码。为了让键的分布更均匀，减少哈希冲突，HashMap还会对这个哈希码进行二次处理。
2. 计算数组索引：使用处理后的哈希值与数组的长度减一进行按位与运算，得到该键值对应在数组中的存储位置（桶的索引）。等效于取模运算，但位运算的效率更高。
3. 处理存储逻辑：

• 桶为空：如果计算出的索引位置没有任何元素，直接创建一个新的节点并存入该节点。
• 桶不为空（发生冲突）：
  • 键已存在：遍历桶中的链表或红黑树，通过equals()方法检查是否存在一个键与当前要插入的键完全相同。如果找到，就用新的value覆盖旧的value，并且返回旧值。
  • 键不存在：
    • 如果当前桶是链表结构，则将新的键值对节点添加到链表的末尾。在添加后，检查链表长度是否达到“树化”阈值，如果达到，则将链表转换为红黑树。
    • 如果当前桶已经是红黑树结构，则直接将新节点插入到红黑树。

get(key)

1. 计算哈希和索引：对指定的key执行与put方法完全相同的哈希计算和索引定位过程，找到对应的桶。
2. 查找目标节点：

• 如果桶为空，直接返回null。
• 如果桶不为空，遍历该桶的链表或在红黑树中进行搜索。
• 在遍历/搜索过程中，首先比较哈希值，如果哈希值相同，再调用key的equals()方法进行精确匹配。
• 如果找到完全匹配的节点，则返回其对应的value；如果遍历/搜索完整个桶都没有找到，则返回null。

容量与加载因子

• HashMap 的性能受到两个重要参数的影响：
  • 初始容量：哈希表中桶的数量。
  • 加载因子：一个介于0.0 ~ 1.0的浮点数，表示哈希表在进行扩容之前可以达到的满度。
• 扩容机制：当 HashMap 中存储的元素数量超过 容量*加载因子 这个阈值时，就会触发扩容操作。
• 扩容过程
  • 创建新数组：创建一个容量是原数组两倍的新数组。
  • 重新计算和迁移：遍历旧数组中的所有键值对，为每个键值对重新计算其在新数组中的索引位置，然后将其迁移到新数组的对应位置。
  • 替换旧数组：将HashMap内部的table引用指向这个新数组。
• 扩容是一个相对耗时的操作，以为它需要重新处理所有已存在的元素。因此，如果在创建HashMap时能预估到要存储的元素数量，通过构造函数指定一个合适的初始容量，可以有效减少或避免扩容操作，从而提升性能。

hashcode() 与 equals()的重要性

1. equals()相等的对象，其hashCode()必须相等：保证在HashMap中能正确找到键的前提。
2. hashCode()相等的对象，其equals()不一定相等：哈希冲突的根源。
3. equals()相等的对象，其hashCode()尽可能不相等：有助于让键值对均匀地分布在数组的不同桶中，减少哈希冲突。

HashMap VS HashSet VS 数组

• 优先使用数组
  • 需要一个简单地，通过下标（数字，字母也可）来访问或修改元素，保证插入顺序，允许重复元素
• 优先使用HashSet
  • 保证元素不重复，快速检查某个元素是否存在于集合中，而不关心在哪里，不关心元素的存储顺序。
• 优先使用HashMap
  • 存储键值对映射关系，根据一个key快速查找对应的value，不关心元素的存储顺序。