散列表为什么可以在O(1)时间复杂度内查找散列值?

一、散列表为什么可以在O(1)时间复杂度内查找散列值

因为哈希函数的功能就是完成键到哈希值的映射，映射到的哈希值就是一个数字，被用来当作数组的下标，这个元素就是存储在数组的这个下标内。散列表用的其实是数组随机存取的特性。数组随机存取的复杂度就是O(1)，所以散列表的查找效率就是O(1)。

什么是散列表

散列表（hash table），我们平时叫它哈希表或者Hash 表，你肯定经常听到它。

散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

由定义我们可以知道，散列表用的是数组支持下标访问数据的特性，所以散列表是数组的一种扩展，有数组演化而来。

延伸阅读：

二、开放寻址法

开发寻址法就是但我们遇到了哈希冲突，我们就重新探索一个空闲位置，然后插入。

我们探索空闲位置有以下几种方法。

当我们往散列表中插入数据时，经过散列函数发现位置已经被占用了，我们就从当前位置开始，依次往后查找，直到找到空闲位置为止。

比如一个散列表的大小为 10，一个数据经过散列函数之后，到了下标为 8 的位置，但是发现这个位置已经有数据了，那么就依次往后遍历，如果到了尾部，还是没有找到空闲位置，那么就再从头开始找，直到找到空闲位置。

查找元素和插入类似，通过散列函数计算出哈希值，然后找到对应位置数据，然后与查找的元素进行比较，如果相等，则它就是我们要找的数据，如果不相等，就依次往后遍历，如果遍历到空闲位置还没找到，就说明元素不在散列表中。

但是删除的时候稍微有点特别，我们不能直接删除数据，因为我们在查找的时候，如果找到一个空闲位置，就说元素不在散列表中，如果我们直接删除了之后可能会导致某些元素找不到。所以我们将要删除的元素，标记为 deleted，当我们查找的时候，遇到标记为 deleted 的元素，继续往下遍历。

线性探测法存在很大的问题，当散列表中插入的元素越来越多时，发生散列冲突的概率就越来越大，空闲的位置就越来越少，先行探索的时间就会越来越长，甚至在极端情况下，我们需要遍历整个散列表。

二次探索，和线性探索原理一样，先行探索每次的步长为 1 ，探索的下标依次为 hash(key)+0，hash(key)+1，hash(key)+2…，二次探索每次的步长变为原来的二次方，所以每次探索的下边为 hash(key)+0，hash(key)+1^2，hash(key)+2^2。

原来我们使用一个散列函数，双重散列，我们使用多个散列函数，我们先用名列前茅个散列函数，如果计算得到的位置已经被占用，就使用第二个散列函数，以此类推，直到找到空闲时的位置。

不管用哪个探索方法，当空闲位置变少的时候，散列冲突的概率会变得很高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子来表示空位的多少。 装载因子 = 填入散列表的元素个数 / 散列表的长度