数据结构之表，例如数组，哈希表，链表
表
hash 表
数组+链表（通过映射函数将key值映射为不同的整数，之后存入该整数对应的链表）
数组的特点： 寻址容易，插入和删除困难
链表的特点： 寻址困难，插入和删除容易
构造哈希
- 直接地址法
- 平方取中法
- 除留余数法（根据余数将该hash键值存入对应的数组中, JVM中桶的大小位 2 的 幂次，用 按位与 来快速计算取模）
hash冲突
关键字值不同的元素可能会映象到哈希表的同一地址上
- 开放定址法（当发生地址冲突时，根据再寻址的方法（探查序列--线性探查 不断+1，伪随机探测--随机数法），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止） 所有关键字都在位桶里
- 再哈希法--再散列（当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数）
- 链地址法（将所有哈希值相同的Key通过链表存储，key 按顺序插入到链表中）冲突的关键字在位桶外的链表里
- 建立公共溢出区等方法（采用一个溢出表处理产生冲突的关键字，在溢出表中再用其他方法处理冲突）SGL 版本使用链地址法，使用一个链表保持相同散列值的元素。虽然链地址法并不要求哈希桶长度必须为质数，但SGI STL 仍然以质数来设计哈希桶长度，并且将28 个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用来查询在这28 个质数之中，“最接近某数并大于某数”的质数。
考点：哈希表 负载因子 rehash
C++的hash 表中有一个负载因子loadFactor，当loadFactor<=1 时，hash 表查找的期望复杂度为O(1). 因此，每次往hash 表中添加元素时，我们必须保证是在loadFactor <1 的情况下，才能够添加。
因此，当Hash 表中loadFactor==1 时，Hash 就需要进行rehash。rehash 过程中，会模仿C++的vector 扩容方式，Hash 表中每次发现loadFactor ==1 时，就开辟一个原来桶数组的两倍空间，称为新桶数组，然后把原来的桶数组中元素全部重新哈希到新的桶数组中。
Deque
是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。
两端插入、删除为o(1)，遍历最差为o(N)
在 deque 中，随机存取任何元素都能在常数时间内完成（但速度慢于vector）。它相比于 vector 的优点是，vector 在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而 deque 在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。