1.哈希表介绍
前面我们已经介绍了许多类型的数据结构。在想要查询容器内特定元素时，有序向量使得我们能使用二分查找法进行精确的查询((O(logN)对数复杂度，很高效)。
可人类总是不知满足，依然在寻求一种更高效的特定元素查询的数据结构，哈希表/散列表(hash table)就应运而生啦。哈希表在特定元素的插入，删除和查询时都能够达到O(1)常数的时间复杂度,十分高效。
1.1 哈希算法
哈希算法的定义：把任意长度的输入通过哈希算法转换映射为固定长度的输出，所得到的输出被称为哈希值(hashCode = hash(input))。哈希映射是一种多对一的关系，即多个不同的输入有可能对应着一个相同的哈希值输出；也意味着，哈希映射是不可逆，无法还原的。
举个例子：我们有一个好朋友叫熊大,大家都叫他老熊。可以理解为是一个hash算法：对于一个人名，我们一般称呼为"老" + 姓氏(单姓) (hash(熊大) = 老熊)。同时，我们还有一个好朋友叫熊二,我们也叫他老熊(hash(熊二) = 老熊)。当熊大和熊二两个好朋友同时和我们聚会时，都称呼他们为老熊就不太合适啦，因为这时出现了hash冲突。老熊这个称呼同时对应了多个人，多个不同的输入对应了相同的哈希值输出。
java在Object这一最高层对象中实现了hashCode方法，并允许子类重写更适应自身，冲突概率更低的hashCode方法。
1.2 哈希表实现的基本思路
哈希表存储的是key-value键值对结构的数据，其基础是一个数组。
由于采用hash算法会出现hash冲突，一个数组下标对应了多个元素。常见的解决hash冲突的方法有：开放地址法、重新哈希法、拉链法等等，我们的哈希表实现采用的是拉链法解决hash冲突。
采用拉链法的哈希表将内部数组的每一个元素视为一个插槽(slot)或者桶(bucket)，并将数据存放在键值对节点(EntryNode)中。EntryNode除了存放key和value，还维护着一个next节点的引用。为了解决hash冲突，单个插槽内的多个EntryNode构成一个简单的单向链表，插槽指向链表的头部节点，新的数据将会插入当前链表的尾部。
key值不同但映射的hash值相同的元素在哈希表的同一个插槽中以链表的形式共存。
1.3 哈希表的负载因子(loadFactor)：
哈希表在查询数据时通过直接计算数据hash值对应的插槽，迅速获取到key值对应的数据，进行非常高效的数据查询。
但依然存在一个问题：虽然设计良好的hash函数可以尽可能的降低hash冲突的概率，但hash冲突还是不可避免的。当发生频繁的哈希冲突时，对应的插槽内可能会存放较多的元素，导致插槽内的链表数据过多。而链表的查询效率是非常低的，在极端情况下，甚至会出现所有元素都映射存放在同一个插槽内，此时的哈希表退化成了一个链表，查询效率急剧降低。
一般的，哈希表存储的数据量一定时，内部数组的大小和数组插槽指向的链表长度成反比。换句话说，总数据量一定，内部数组的容量越大(插槽越多)，平均下来桶链表的长度也就越小，查询效率越高。
同等数据量下，哈希表内部数组容量越大，查询效率越高，但同时空间占用也越高，这本质上是一个空间换时间的取舍。
哈希表允许用户在初始化时指定负载因子(loadFactor)：负载因子代表着存储的总数据量和内部数组大小的比值。插入新数据时，判断哈希表当前的存储量和内部数组的比值是否超过了负载因子。当比值超过了负载因子时，哈希表认为内部过于拥挤，查询效率太低，会触发一次扩容的rehash操作。rehash会对内部数组扩容，将存储的元素重新进行hash映射，使得哈希表始终保持一个合适的查询效率。
通过指定自定义的负载因子，用户可以控制哈希表在空间和时间上取舍的程度，使哈希表能更有效地适应用户的使用场景。
指定的负载因子越大，哈希表越拥挤(负载高，紧凑)，查询效率越低，空间效率越高。
指定的负载因子越小，哈希表越稀疏(负载小，松散)，查询效率越高，空间效率越低。
2.哈希表ADT接口
和之前介绍的链表不同，我们在哈希表的ADT接口中暴露出了哈希表内部实现的EntryNode键值对节点。通过暴露出去的public方法，用户在使用哈希表时，可以获得内部的键值对节点，灵活的访问其中的key、value数据(但没有暴露setKey方法，不允许用户自己设置key值)。
public interface Map <K,V>{ /** * 存入键值对 * @param key key值 * @param value value * @return 被覆盖的的value值 */ V put(K key,V value); /** * 移除键值对 * @param key key值 * @return 被删除的value的值 */ V remove(K key); /** * 获取key对应的value值 * @param key key值 * @return 对应的value值 */ V get(K key); /** * 是否包含当前key值 * @param key key值 * @return true：包含 false：不包含 */ boolean containsKey(K key); /** * 是否包含当前value值 * @param value value值 * @return true：包含 false：不包含 */ boolean containsValue(V value); /** * 获得当前map存储的键值对数量 * @return 键值对数量 * */ int size(); /** * 当前map是否为空 * @return true：为空 false：不为空 */ boolean isEmpty(); /** * 清空当前map */ void clear(); /** * 获得迭代器 * @return 迭代器对象 */ Iterator<EntryNode<K,V>> iterator(); /** * 键值对节点 内部类 * */ class EntryNode<K,V>{ final K key; V value; EntryNode<K,V> next; EntryNode(K key, V value) { this.key = key;
