hash表实际上由size个的桶组成一个桶数组table[0...size-1] 。

当一个对象经过哈希之后。得到一个对应的value , 于是我们把这个对象放到桶table[ value ]中。当一个桶中有多个对象时。我们把桶中的对象组织成为一个链表。

这在冲突处理上称之为拉链法。

 

负载因子（load factor）

 

     如果一个hash表中桶的个数为 size , 存储的元素个数为used .则我们称 used / size 为负载因子loadFactor . 一般的情况下，当loadFactor<=1时，hash表查找的期望复杂度为O(1). 因此。每次往hash表中加入元素时。我们必须保证是在loadFactor <1的情况下，才可以加入。

 

 

容量扩张（Expand）& 分摊转移

 

      当我们加入一个新元素时。一旦loadFactor大于等于1了，我们不能单纯的往hash表里边加入元素。

由于加入完之后，loadFactor将大于1，这样也就不能保证查找的期望时间复杂度为常数级了。这时。我们应该对桶数组进行一次容量扩张，让size增大 。

这样就能保证加入元素后 used / size 仍然小于等于1 ， 从而保证查找的期望时间复杂度为O(1).可是。怎样进行容量扩张呢？ C++中的vector的容量扩张是一种好方法。

 

于是有了例如以下思路 ：　Hash表中每次发现loadFactor==1时，就开辟一个原来桶数组的两倍空间（称为新桶数组），然后把原来的桶数组中元素所有转移过来到新的桶数组中。注意这里转移是须要元素一个个又一次哈希到新桶中的。原因后面会讲到。

      这样的方法的缺点是，容量扩张是一次完毕的，期间要花非常长时间一次转移hash表中的全部元素。这样在hash表中loadFactor==1时。往里边插入一个元素将会等候非常长的时间。