哈希表（Hash table）

哈希表（Hash table），也称为散列表，是一种根据关键码值（Key value）直接进行访问的数据结构。它通过散列函数（Hash function）将关键码值映射到表中的一个位置，以此来访问记录，从而加快查找的速度。以下是关于哈希表的详细解释：

基本概念

散列函数：将关键码值映射到表中位置的函数，记作f(key)。给定关键字k，其值存放在f(k)的存储位置上。

冲突：对于不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为冲突。

同义词：具有相同函数值的关键字对该散列函数来说称做同义词。

实现方法

哈希表的实现主要有两种方法：

开放寻址法：所有的元素都存储在哈希表的数组中，冲突发生时会探测下一个可用的位置，直到找到一个空闲的位置。这种方法保持了元素的顺序，但可能导致聚集（clustering）。

链地址法：使用一个数组来存储指向链表头部的指针，每个链表存储具有相同哈希值的元素。如果发生冲突，新的元素将被添加到该链表的末尾。这种方法可以避免聚集，但不保持元素的顺序。

特点

高效性：哈希表可以在O(1)的平均时间复杂度下完成查找、插入和删除操作，这是因为它通过散列函数直接定位到元素在数组中的位置。

无序性：哈希表不保证元素的顺序，元素在表中的位置取决于其关键码值和散列函数。

空间利用率