Java集合包（六）——Map实现类之HashMap、HashTable 原理分析

转载请注明原文地址：https://www.cnblogs.com/ygj0930/p/13565926.html 

一：HashMap特征

　　1、HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

　　2、HashMap是无序的。

　　3、HashMap是非线程安全的，只适合在单线程环境下使用。

　　4、HashMap的key和value允许为空。

二：HashMap继承与实现关系

　　1、继承层次

java.lang.Object
   ↳     java.util.AbstractMap<K, V>
         ↳     java.util.HashMap<K, V>

　　2、类定义与实现

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable { }

　　继承AbstractMap，实现了Map、Cloneable、java.io.Serializable接口，具备了通用的键值对操作能力、克隆能力、序列化能力。

三：HashMap原理

　　HashMap的重要成员与概念解析

　　1、table数组：一个Entry[]数组，每个数组位置称之为一个“桶”，每个桶位都对应一个hash值，每个桶位存储一个Entry实例。而Entry实例实际上是一个单向链表，每个链表节点存储一个键值对。

　　　　　　   在jdk1.8之前，Entry数组中存储的是链表的表头，一个链表存储hash值相同的键值对们。键值对的hash值相同称之为“hash冲突”，解决hash冲突有多种方法，HashMap采用的是拉链法。

　　　　　　　　1）拉链法

　　　　　　　　　  这种方法的思路是：把同一个散列槽（在我们这里就是数组的每一个桶位）中的所有元素放到一个链表中，也就是说：把hash值相同的键值对，保存到同一个链表中。

　　　　　　　　　 往HashMap中put一个元素时：首先通过散列函数计算键值对的hash值，得到其在table数组中的桶位。如果该桶位中没有元素，则生成一个Entry实例保存键值对后插入该桶位；

　　　　　　　　　　　　　　　　　　　　　　　如果有元素，则检查key值的唯一性：如果key值和我们要插入的数据不一样，则生成一个Entry实例保存键值对后，插入到该桶位的链表中；如果存在和我们要插入数据相同key的键值对，我们就把value进行更换即可。

　　　　　　　　2）再哈希法

　　　　　　　　　　这种方法的思路是：当出现hash值相同的键值对时，进行再次hash计算，直到出现不冲突的位置为止。这样会导致时间成本增加，不采用。

　　　　　　　　3）开放地址法

　　　　　　　　　　这种方法的思路是：插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。

　　　　　　　　　　所以这种方法又称为再散列法。

　　　　　　　jdk1.8引入了新的实现方式来解决hash冲突，当某个entry链表长度大于8时，会转化成红黑树进行存储；当某个entry树的小于6个元素时，又会转回链表存储。

　　　　　　　　这样做的原因是：

　　　　　　　　1）原因：
　　　　　　　　红黑树的平均查找长度是log(n)，当长度为8，查找长度为log(8)=3；

　　　　　　　　链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，此时开始有转换成树的必要；

　　　　　　　　链表长度如果是小于等于6，6/2=3，因此小于等于6时链表形式的速度已足够快，虽然红黑树的速度会更快，但是转化为树结构也需要时间开销，因此最终性能表现差距不大，无谓再转成红黑树。

　　　　　　　　2）选择6和8的原因是：
　　　　　　　　中间有个差值7可以防止链表和树之间频繁的转换。

　　　　　　　　3）引入红黑树而不是AVL平衡二叉树的原因

　　　　　　　　红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。

　　　　　　　　但对于插入删除等操作，红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，省去了很多没有必要的平衡调整操作，因此性能更优。

　　2、初始容量：容量 是指哈希表中桶的数量，一个桶存储一个键值对。最大容量必须是2的幂且小于2的30次方，传入容量过大将被这个值替换。

　　　　　　　初始容量 指哈希表在创建时的一开始的容量，默认的初始容量是16，必须是2的幂。

　　3、加载因子loadFactor：指触发哈希表扩容的一个当前大小的临界值。

　　　　　　　当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作进行扩容，将容量扩大一倍。

　　　　　　    默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本。

　　4、阈值threshold：用于判断是否需要调整HashMap的容量，threshold="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。

　　5、size：存储当前键值对的数量，即HashMap的大小。

　　6、modCount：实现fail-fast机制的判断依据。

四：HashMap关键方法

　　1、遍历键值对

Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 获取key
    key = (String)entry.getKey();
        // 获取value
    integ = (Integer)entry.getValue();
}

　　第一步：根据entrySet()获取HashMap的“键值对”的Set集合，并获取其迭代器。
　　第二步：通过Iterator迭代器遍历键值对的Set集合，并通过entry提供的getKey和getValue方法提取键、值。

　　2、遍历键

Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
        // 获取key
    key = (String)iter.next();
}

　　第一步：根据keySet()获取HashMap的“键”的Set集合。
　　第二步：通过Iterator迭代器遍历“第一步”得到的集合。

　　3、遍历值

Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

　　第一步：根据value()获取HashMap的“值”的Collection集合。【此处是Collection而不是Set，因为值是允许重复的】
　　第二步：通过Iterator迭代器遍历“第一步”得到的集合。

五：HashTable【已过时】

　　1）HashTable也是存储键值对和操作键值对的，其底层数据结构原理与HashMap几乎一样，也有容量、加载因子、自动扩容机制等，也是通过拉链法解决哈希冲突，用链表保存键值对。

　　2）HashTable的key和value不允许为空，这是与HashMap的不同之处。

　　3）HashTable提供的键值对操作方法大多与HashMap一致，不同的地方在于它的方法都被 synchronized 修饰，从而实现线程安全。

　　4）HashTable继承了Dictionary类，因此其迭代方式比HashMap多出一种选择：除了使用Iterator迭代器，还可以使用Enumeration枚举类迭代。

　　Iterator和Enumeration的不同之处：

　　Enumeration:

package java.util;

public interface Enumeration<E> {

    boolean hasMoreElements();

    E nextElement();
}

　　Iterator:

package java.util;

public interface Iterator<E> {
    boolean hasNext();

    E next();

    void remove();
}

　　可见：

　　1）函数接口不同

        Enumeration只有2个函数接口。通过Enumeration，我们只能读取集合的数据，而不能对数据进行修改。
        Iterator只有3个函数接口。Iterator除了能读取集合的数据之外，也能数据进行删除操作。

　　2）Iterator支持fail-fast机制，而Enumeration不支持。

　　3）Enumeration 比 Iterator 的遍历速度更快

　　因为，Iterator添加了对fail-fast机制的支持，所以遍历要慢一点点。