散列表

散列表的最坏情况是O(N)，最好情况是O(1)

散列表的效率取决于以下因素。

1. 要存多少数据。
2. 有多少可用的格子。
3. 用什么样的散列函数。

一个好的散列函数，应当能将数据分散到所有可用的格子里去。

使用散列表时所需要权衡的：既要避免冲突，又要节约空间。

要想解决这个问题，可参考计算机科学家研究出的黄金法则：每增加7个元素，就增加10个格子。

数据量与格子数的比值称为负载因子。理想的负载因子是0.7（7个元素/10个格子）

如果你一开始就将7个元素放进散列表，那么计算机应该会创建出一个含有10个格子的散列表。随着你添加元素，计算机也会添加更多的格子来扩展这个散列表，并改变散列函数，使新数据能均匀地分布到新的格子里去。

高效的软件离不开散列表，因为其O(1)的读取和插入带来了无与伦比的性能优势。