1.概念
散列：使用一个散列函数，将一个键映射到一个索引上
java集合框架定义了Map接口来对映射表建模。三个具体的实现类为HashMap、LinkedHashMap、TreeMap。
HashMap：使用散列实现
LinkedHashMap：是哟个LinkedList实现
TreeMap：使用红黑树实现-
散列函数
散列函数将键映射到散列表中的索引上
散列函数从一个键获得索引，并使用索引来获取该键的值。
-
完美散列函数
我们希望设计一个函数，将每个搜索的键映射到散列表中的不同索引上。这样的函数被称为完美散列函数。然而，很难找到一个完美散列函数，当多个键映射到一个散列值上时，我们称产生了一个冲突。
2.散列函数和散列码
典型的散列函数首先将搜索键转换成一个称为散列码的整数值，然后将散列码压缩为散列表中的索引。
3.使用开放地址法处理冲突
是在冲突发生时，在散列表中找到一个开放位置的过程。
1）线性探测
-
按顺序寻找下一个可用的位置。例如：如果冲突发生在hashTable[k%N],则检查hashTable[（k+1）%N]是否可用，不可用再检查hashTable[（k+2）%N]，当探测到终点时，则返回表的起点，因此散列表是循环的。
- 删除条目时，查找匹配键的条目，如果条目找到，放置一个特殊的标记表示该条目是可用的。
- 散列表中每个单元具有三个可能的状态：被占的、标记的或者空的。
- 存在的问题：容易导致散列表中连续的单元组被占用。当连续单元组越来越大，会放慢查找的时间。
2）二次探测法
线性探测法问题：
- 避免了线性探测成簇的问题，但有自己本身的成簇问题，称为二次成簇。
- 线性探测法可以保证只要表不是满的，一个可用的单元总是可以被找到用于插入新的元素，然而，二次探测法不能保证。
3）再哈希法
4.使用链地址法处理冲突
链地址法将具有同样的散列索引的条目都放在一个位置，而不是寻找一个新的位置。链地址法的每个位置使用一个桶来放置多个条目。
5.装填因子和再散列
装填因子：衡量一个散列表有多满。是元素数目和散列表的比值。对于开放地址而言，需要位置装填因子在0.5之下，对于链地址，维持在0.9之下。Hashmap采用0.75为装填因子。
再散列：如果装填因子溢出，则增加散列表的大小，并重新装载条目到一个新的更大的散列表中，这称为再散列。
6.使用散列实现映射表
使用链地址法实现映射表，对照java.util.Map来设计自定义的Map接口，命名为MyMap，具体类命名为MyHashMap。
7.使用散列实现set
使用链地址法
