哈希表（Hash table，也叫散列表），是一种键-值对，通过输入关键字k，进行计算得到一个值v。计算过程是一个哈希函数，值v组成一张哈希表，每一项对应一个指针，可访问内存中的数据结构。这加快了查询速度，算法的时间复杂度为O(1)。

若关键字是k，哈希函数为f(x)，则f(k)为k所对应的值，对于不同的k得到的f(k)组成一个哈希表。

对于不同关键字得到同样的散列值，即若k1≠k2，f(k1)=f(k2)，这种情况叫冲突。散列函数f(x)处理冲突的方式大致是将有冲突的所有关键字映射到连续的地址空间，并以散列值作为地址空间的“像”。

对于关键字集合中的任一关键字，经哈希函数映射到地址集合中任一地址的概率相同，这样的散列函数最大程度地减少了冲突。

哈希函数的分类：

直接地址法：哈希函数是一个线性函数，如f(k) = k或f(k) = a·k + b，其中a，b为常数；数字分析法：若哈希函数的关键字是事先知道的，且以r为基数，则可取关键字的若干数位为地址；平方取中法：关键字事先未知，取关键字平方的中间几位作为地址，地址的位数由表长确定，这样使关键字随机分布，得到的哈希地址也随机；折叠法：将关键字转换成二进制数，分割成几部分，每一部分相加（舍去进位），得到哈希地址；除留余数法：关键字除以不大于表大小的数p后得到余数，p一般取表大小或素数，p的取值影响冲突的概率；随机数法

处理冲突的方式：单独链表法，将映射到同一哈希地址的键值对存储在一个链表上，一般压入栈中。

哈希表的查找：

哈希地址通过输入的关键字和哈希函数得到，有一些关键字经过哈希函数的转换会发生冲突。查找的效率取决于冲突发生的多少，冲突越少，效率越高，冲突越多，效率越低。影响冲突多少的因素主要有：哈希函数的随机度、处理冲突的算法和哈希表的载荷因子。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。