什么是哈希表？

哈希（Hashing）

到目前为止，在插入、删除和查找操作中，我们所能达到的时间复杂度通常为 O(nLogn)，在平衡二叉树中最优可达到 O(Logn)，这已经相当不错了。但如果希望这些操作都能在常数时间内完成呢？

🔍 哈希：是什么，为什么？

哈希是一种用于唯一标识对象的技术，它将每个对象存储在一个预先计算出的唯一索引位置，这个索引称为其 键（key）。因此，数据以 键值对 的形式存储，这类集合被称为“字典”。通过该 键 可以在 O(1) 时间内快速查找对应的对象。

当处理的数据量非常庞大时，即使是 O(nLogn) 的时间复杂度也会变得不可忽视，从而影响算法效率。理想情况下，我们需要一种数据结构，能够在常数时间内完成上述三种操作，以高效管理大量记录——这正是 哈希技术 的用武之地！

虽然哈希可能使查找逻辑略微复杂，但它极大地缩短了数据获取的时间。基于哈希思想的数据结构有多种，其中最常用的是 哈希表。

哈希表

哈希表的主要目标是尽可能减少任意数据的查找时间。

工作原理

哈希表通常使用 数组 来实现，因为数组是唯一能以常数 O(1) 时间访问元素的数据结构。

下面我们来解释它是如何工作的。

键值对

通过使用一个 键 将数据映射到数组中的某个位置，即可实现 O(1) 时间内的数据存取（计算这个键的方法有多种）。对于数组而言，可以直接将 键 作为索引存储数据。当你传入一个 键，就能直接获取对应的 值；换句话说（最简单的情况下）：

$value = arr[key]$

下图展示了 哈希表 如何通过哈希函数计算出索引（1,2,3,...,5），并将数据映射到数组中。（哈希函数将在后文详细讨论）

请看以下代码片段，其中根据传入的 键 返回对应的 值：

1class Hashing {
2   public static String getValue(int key)  
3   {    
4    String [] myString = // pun intended
5    { 
6      "I am a programmer, I have no life.",
7      "8 bytes walk into a bar, the bartenders asks \"What will it be?\"One of them says, \"Make us a double.\"",
8      "Computers are useless. They can only give you answers.\n-Pablo Picasso"
9    }; 
10    if (key < myString.length)
11      return myString[key];    // 常数时间内返回值
12    else 
13      System.out.println("Key Not Found!\n");  
14     return "";
15  }
16    public static void main( String args[] ) 
17    {
18        System.out.println( getValue(1) ); // 可测试其他键的输出
19    }
20}

影响因素

哈希常用于需要处理海量数据的场景。此时，用于查找的 键 可能非常大，无法直接作为数组索引。因此需要一个 函数() 将这个大键转换为较小的键，使其落在数组索引范围 0 到 n-1 内，其中 n 是数组的大小。这一转换可通过 哈希函数 实现。哈希结构的性能主要取决于以下三个因素：

1. 哈希函数

2. 哈希表的大小

3. 冲突处理方法