Java中的Hash表和hashCode()

哈希表

哈希表（Hash table），也称为散列表，是一种常用的数据结构，用于实现键值对的存储和快速查找。它通过将键映射到一个哈希值，然后将该哈希值作为索引来访问数据，从而实现高效的插入、删除和查找操作。 哈希表的核心思想是使用哈希函数将键转换为唯一的哈希值，然后将该哈希值与数组的索引进行关联。当需要插入或查找一个键值对时，通过哈希函数计算出哈希值，并使用该哈希值直接访问数组中的位置。这样可以在平均情况下以常数时间复杂度（O(1)）进行插入、删除和查找操作。 然而，由于不同的键可能会映射到相同的哈希值（称为哈希冲突），哈希表需要解决冲突的问题。常见的解决冲突的方法有两种：开放寻址法和链表法。开放寻址法是在发生冲突时，通过探测空槽位来寻找下一个可用位置。链表法是在哈希表的每个槽位上维护一个链表，将哈希值相同的键值对存储在同一个链表中。 哈希表在实际应用中非常常见，例如在编程语言中的字典、集合等数据结构，以及数据库索引、缓存等场景中都广泛使用了哈希表来提高数据的访问效率。 哈希表可以用来存储键值对数据，并通过哈希函数将键映射到数组中的一个索引位置。下面是一个示例的哈希表图：

+--------+ | Index | +--------+ | 0 | +--------+ | 1 | +--------+ | 2 | +--------+ | 3 | +--------+ | 4 | +--------+ | 5 | +--------+ | 6 | +--------+ | 7 | +--------+ | 8 | +--------+ | 9 | +--------+

在哈希表中，索引位置类似于数组的下标，每个索引位置可以存储一个键值对。当需要通过键查找值时，哈希函数将计算键的哈希值，并根据哈希值得到对应的索引位置，然后就可以在该位置找到对应的值。

需要注意的是，实际的哈希表可能会更复杂，可能包含冲突处理机制（例如链地址法或开放寻址法），以及动态调整大小等功能。但以上是哈希表的基本结构。 开放寻址法是哈希表中解决冲突的一种方法，它的基本思想是当发生冲突时，直接在哈希表中寻找下一个可用的空槽来存储冲突的键值对。

在开放寻址法中，每个哈希表的槽都可以存储一个键值对。当进行插入操作时，首先使用哈希函数计算键的哈希值，然后根据哈希值找到对应的槽。如果该槽为空，则直接将键值对存储在该槽中；如果该槽不为空，说明发生了冲突，此时会继续寻找下一个空槽，可以使用如下的方法：

线性探测：顺序地检查下一个槽，直到找到一个空槽。
二次探测：以二次方递增地检查下一个槽，直到找到一个空槽。
双重哈希：使用第二个不同的哈希函数计算下一个槽的位置，直到找到一个空槽。

当进行查找操作时，使用哈希函数计算键的哈希值，并根据哈希值找到初始槽。然后，按照相同的探测方法依次检查后续的槽，直到找到目标键或者遇到空槽。

开放寻址法的优点是比较简单，没有额外的链表开销，对于小型哈希表来说，它的性能可能比较好。然而，它的缺点是当哈希表填充度过高时，会导致冲突增多，而且插入和查找操作的效率可能会降低。

因此，在设计哈希表时，需要根据实际情况选择适合的冲突处理方法，包括开放寻址法和链地址法等。

当使用开放寻址法解决冲突时，哈希表的每个槽可以存储一个键值对。下面是使用开放寻址法的哈希表图示例：

+--------+--------+
| Index  |  Value |
+--------+--------+
|   0    | (k,v)  |
+--------+--------+
|   1    |        |
+--------+--------+
|   2    | (k,v)  |
+--------+--------+
|   3    | (k,v)  |
+--------+--------+
|   4    |        |
+--------+--------+
|   5    | (k,v)  |
+--------+--------+
|   6    |        |
+--------+--------+
|   7    | (k,v)  |
+--------+--------+
|   8    |        |
+--------+--------+
|   9    |        |
+--------+--------+

在这个哈希表中，使用开放寻址法处理冲突。键值对 (k,v) 被插入到哈希表中时，首先通过哈希函数计算键 k 的哈希值，然后根据哈希值找到对应的索引位置。

在这个例子中，我们假设哈希函数计算键 k 的哈希值后得到索引位置为 0，但是该位置已经被占用。根据开放寻址法，我们需要找到下一个可用的空槽来存储冲突的键值对。

我们顺序地检查下一个槽，直到找到一个空槽，例如索引位置 1。然后，将键值对 (k,v) 存储在该槽中。

又假设另一个键值对 (k',v') 的哈希值计算后得到索引位置 2，但是该位置也已经被占用。在这种情况下，我们需要继续寻找下一个空槽，依次检查索引位置 3、4、5，直到找到空槽，例如索引位置 6。然后，将键值对 (k',v') 存储在该槽中。

类似地，当遇到另一个键值对 (k'',v'') 的哈希值计算后得到索引位置 3，但是该位置已经被占用时，我们需要再次寻找下一个空槽。假设索引位置 4 是空槽，那么将键值对 (k'',v'') 存储在该槽中。

需要注意的是，在使用开放寻址法时，当进行查找操作时，我们会根据相同的探测方法依次检查后续的槽，直到找到目标键或者遇到空槽。

这是一个简单的展示，实际上开放寻址法可能会使用更复杂的探测策略，例如二次探测和双重哈希，以获得更好的性能和均匀分布的键值对存储。 当使用链地址法解决哈希表中的冲突时，每个哈希表槽可以包含一个链表。下面是结合链表法的哈希表图示例：

±-------±---------------------------+

| Index | Chain |

±-------±---------------------------+

| 0 | → (k1,v1) → (k4,v4) |

±-------±---------------------------+

| 1 | |

±-------±---------------------------+

| 2 | → (k2,v2) |

±-------±---------------------------+

| 3 | → (k3,v3) → (k5,v5) |

±-------±---------------------------+

| 4 | |

±-------±---------------------------+

| 5 | → (k6,v6) |

±-------±---------------------------+

| 6 | |

±-------±---------------------------+

| 7 | → (k7,v7) |

±-------±---------------------------+

| 8 | |

±-------±---------------------------+

| 9 | |

±-------±---------------------------+

-----------------------------------

在这个哈希表中，每个索引位置包含一个链表，用于存储冲突的键值对。当键值对 (k1,v1) 被插入到哈希表时，通过哈希函数计算键 k1 的哈希值，得到索引位置 0。如果该位置为空，直接将键值对插入到该位置；否则，通过链表将键值对添加到该位置的链表的末尾。

例如，在索引位置 0 中，已经有一个链表，它包含键值对 (k1,v1) 和 (k4,v4)。当我们插入键值对 (k4,v4) 时，根据哈希函数计算 k4 的哈希值，该值与索引位置 0 的哈希值相同，因此将键值对 (k4,v4) 添加到链表的末尾。

类似地，当键值对 (k2,v2) 被插入时，计算其哈希值得到索引位置 2，将键值对添加到索引位置 2 的链表的末尾。

当进行查找操作时，通过哈希函数计算键的哈希值，然后根据哈希值找到对应的索引位置。然后，在该位置的链表中，按顺序查找目标键，并返回对应的值。

需要注意的是，当链表长度较长时，查找操作的效率可能会降低，因此，为了避免链表过长，可采取一些策略，例如链表长度超过一定阈值时将其转换为其他数据结构，如平衡二叉搜索树。

链地址法是一种弥补哈希表冲突的有效方法，它允许在每个哈希表槽中存储多个键值对，并通过链表或其他数据结构来解决冲突。