散列表

实现散列表的方法有很多种，在此介绍一种简单、常见的实现方式。

我们使用一个链表构成的数组与一个散列函数来实现散列表。当插入键(字符串或几乎其他所有数据类型)和值时，我们按照如下方法操作。

（1）首先，计算键的散列值。键的散列值通常为int或者long型。请注意，不同的键可能有相同的散列值。

（2）之后，将散列值映射为数组的索引。可以使用类似于hash(key) % array_length 的方式完成这一步骤。

（3）此数组索引处存储的元素是一系列由键和值为元素组成的链表。将映射到此索引的键和值存储在这里。由于存在冲突，我们必须使用链表。

时间复杂度

如果冲突发生很多次，最坏的情况下的时间复杂度是O(N) ，其中N是键的数量。

但是我们通常假设一个不错的实现

构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。

• 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k 或hash(k)=ak+b, 其中ab为常数（这种散列函数叫做自身函数）
• 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
• 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
• 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
• 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k)=k mod p, p<=m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。