哈希表可以理解为一个加强版的数组。

数组可以通过索引在 O(1)O(1) 的时间复杂度内查找到对应元素，索引是一个非负整数。

哈希表是类似的，可以通过 key 在 O(1)的时间复杂度内查找到这个 key 对应的 value。key 的类型可以是数字、字符串等多种类型。

怎么做的？特别简单，哈希表的底层实现就是一个数组（我们不妨称之为 table）。它先把这个 key 通过一个哈希函数（我们不妨称之为 hash）转化成数组里面的索引，然后增删查改操作和数组基本相同：

几个关键概念及原理

key是唯一的，value 可以重复

哈希表中，不可能出现两个相同的 key，而 value 是可以重复的。

明白了上面讲的原理应该很好理解，你直接类比数组就行了：

数组里面每个索引都是唯一的，不可能说你这个数组有两个索引 0。至于数组里面存什么元素，随便你，没人 关心。

所以哈希表是一样的，key 的值不可能出现重复，而 value 的值可以随意。

哈希函数

哈希函数的作用是把任意长度的输入（key）转化成固定长度的输出（索引）。

你也看到了，增删查改的方法中都会用到哈希函数来计算索引，如果你设计的这个哈希函数复杂度是 O(N)，那么哈希表的增删查改性能就会退化成 O(N)，所以说这个函数的性能很关键。

这个函数还要保证的一点是，输入相同的 key，输出也必须要相同，这样才能保证哈希表的正确性。不能说现在你计算 hash("123") = 5，待会儿计算 hash("123") = 6，这样的话哈希表就废了。

哈希冲突

如果两个不同的 key 通过哈希函数得到了相同的索引，怎么办呢？这种情况就叫做「哈希冲突」。