7.1. 散列表

散列表的基本思想，是通过一定的函数将需搜索的键值映射为一个整数，将这个整数视为索引值去访问某片连续的内存区域。理论上，在最优情况下，散列表能提供O(1)复杂度的搜索效率。

用于映射的函数称为散列函数（hash function），而映射后的值称为元素的散列值（hash value）。在散列表的实现中，所选择的散列函数的优劣将直接决定所实现的散列表的搜索效率的高低。

在使用散列表的过程中，不同的对象经过散列函数的作用，可能被映射为相同的散列值。而且随着需要存储的数据的增多，这样的冲突就会发生得越来越频繁。散列冲突是散列技术与生俱来的问题。

装载率是散列表中已使用空间和总空间的比值。如果散列表一共可以容纳10个元素，而当前已经装入了6个元素，那么装载率就是6/10。研究表明，当散列表的装载率大于2/3时，散列冲突发生的概率就