java1.8-HashMap

类图结构

类文件说明

我们知道java sdk里的注释是最好的doc文档。每个源码文件开始都有一大段注释来说明此文件所描述的内容，在这儿我们可以对源码有个大概的了解。

一：

HashMap和HashTable类似，不同之处在于HashMap是非同步的即不是线程安全的；HashMap允许key、value为null

二：

HashMap不保证插入元素所存放的顺序，甚至不保证元素的存放顺序会一直保持不变

三：

假定hash函数散列性能比较好，基本的get、put操作都是O(1) 性能。对Map的遍历操作性能则和Map的capacity(桶深)、size（键值对个数）成比例，所以如果对遍历性能要求比较高的话，则不要将initial capacity设置太高，也不要将loadFactor设置过低

四：

HashMap有两个重要的影响性能的参数：initial capacity和loadFactor。initial capacity是哈希表创建时哈希数组的初始大小。loadFactor(负载因子)是哈希表自动扩容前所允许哈希数组的已使用容量，当已使用容量超过loadFactor时，哈希表自动扩容到两倍之前的capacity，重新构建内部结构。loadFactor为0.75时，时间空间复杂度最好。loadFactor大于0.75时，空间消耗少，时间消耗增加。loadFactor小于0.75时，空间消耗增加，时间消耗少。所以在初始化HashMap时要根据loadFactor来设置initial capacity，以减少扩容(影响性能)的次数。

五：

HashMap是通过key的hashcode来确定所对应的存放bucket，所以为了HashMap的性能，需要让key的hashcode尽量不重复

六：

HashMap不是线程安全的，所以有多个线程同时访问同一个HashMap时，如果至少有一个线程修改了HashMap的结构(增加或删除元素等操作)，则需要对这个HashMap加上Synchronized同步。一个使HashMap成为线程安全的方法如下：

Map m = Collections.synchronizedMap(new HashMap(...));

七：

在HashMap上取Iterator之后，如果不是通过Iterator自己的方法来改变HashMap的结构（增加或删除元素等操作），Iterator将会失效，后续基于Iterator的代码将会抛异常：java.util.ConcurrentModificationException。

public class HashMapTest {
    private static  Map<String, String> employers = new HashMap<> (  );

    public static void main(String[] args) {
        employers.put ( "1", "qiaojian" );
        employers.put ( "2", "leo" );
        employers.put ( "3", "guo" );
        employers.put ( "4", "min" );

        Iterator<Map.Entry<String, String>> iter = employers.entrySet ().iterator ();
        while (iter.hasNext ()) {
            employers.put ( "5", "bab" ); //此行代码导致抛出异常
            Map.Entry<String, String> next = iter.next ();
            if (next.getKey ().equals ( "2" )) {
                iter.remove (); //通过Iterator自己的方法删除元素是正确的
            }
        }
        System.out.println ( employers.size () );
    }
}

八：

泊松分布在HashMap中的应用：HahsMap默认loadFactor为0.75时，key的hash散列良好时，插入节点在数组的分布满足λ =0.5的泊松分布。此时在一个索引下出现链表的size大小满足以下概率：

* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

因此，设置链表转红黑树阈值TREEIFY_THRESHOLD=8，表示真的出现使用红黑树的情况的概率很小很小。

serialVersionUID

serialVersionUID 用来表明类的不同版本间的兼容性。

对于实现了Serializable接口的类表示此类可以被序列化和反序列化。

serialVersionUID是根据类名、接口名、成员方法及属性等来生成一个64位的哈希字段。

Java的反序列化即是通过传过来的serialVersionUID和本地定义的类的serialVersionUID作比对来确保反序列化的正确性。

显示的定义serialVersionUID可以在反序列化时，确保类版本的兼容性。即使某个类在与之对应的对象已经序列化出去后做了修改，该对象依然可以被正确反序列化（当serialVersionUID相同时，它就会将不一样的field以type的预设值Deserialize，确保兼容性）。

关于HashMap的序列化

1. 首先 HashMap 实现了 Serializable 接口，可以序列化
2. serialVersionUID 用于保证版本的兼容性
3. static和final属性不会被序列化
4. transient修饰的属性不会被序列化
5. HashMap的 table、entrySet、size和modCount属性都被标记为transient
6. HashMap实现了自己的序列化方法: writeObject 和反序列化方法 readObject，表示不会使用JDK中默认的序列化方法
7. Java的序列化使用ObjectOutputStream类的各种方法（writeInt、writeBoolean、writeObject等），反序列化使用ObjectInputStream的各种方法（readInt、readBoolean、readObject等），而writeObject和readObject会判断被序列化对象是否重写了对应的方法来调用被序列化对象自己的方法完成自定义的序列化和反序列化
8. HashMap为什么要自己实现序列化和反序列化方法？ 因为HashMap中，由于Entry的存放位置是根据Key的Hash值来计算，然后存放到数组中的，对于同一个Key，在不同的JVM实现中计算得出的Hash值可能是不同的。而Key的Hash值不同会导致table结构的不同，导致JDK默认序列化出来的数据也不同。而HashMap自定义的序列化方法writeObject中将table里每个Node的key和value分别序列化。在自定义的反序列化方法readObject中将key、value提取出来重新计算hash，重新put形成table

tableSizeFor

/*
 * Returns a power of two size for the given target capacity.
 * 此函数的作用是：根据当前传入的cap，计算出table size（为2的幂次方，等于 capacity * loadfactor）
 * 比如：new Hashmap<> (5); 则根据5计算出 table size为8
 */
static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//为什么要保持table size是2的幂次方？
//因为：在put元素时是根据（hash(key) % capacity）来确定元素要存放的index：
//而：取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。
//所以上式等同于下式
index = e.hash % newCap
//等同于
index = e.hash & (newCap - 1);
//所以保持table size是2的幂次方是为了根据hash来计算index可以通过&运算完成以提供性能

hash(key)

//由下可见，在put元素时，根据key计算hash值
public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}
//hash值的计算规则：取key的hashCode与其自身的高16位进行异或运算
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//为什么hash计算要取key的hashCode与其自身的高16位进行异或运算？
//因为上面我们提到index的运算规则是e.hash & (newCap - 1)。
//由于newCap是2的幂次方，那么newCap - 1的高位应该为0。
//如果e.hash值只用自身的hashcode的话，那么newCap - 1只会和e.hash低位做&操作(e.hash有32位值，而newCap - 1 通常没有那么大)。这样一来，e.hash的值就只有低位参与运算，高位未参与计算，从而会带来哈希冲突的风险。
//所以在计算key的哈希值的时候，用其自身hashcode值与其高16位做异或操作。这也就让高位参与到index的计算中来了，即降低了哈希冲突的风险又不会带来太大的性能问题。

Node< K ,V >[]

Node<K,V>[] table是HashMap底层存储的数据结构，是一个Node数组。Node类为元素维护了一个单向链表。这样设计的原因是考虑到遇到哈希冲突的时候，同index的value值就用单向链表来维护。当单链表的长度超过TREEIFY_THRESHOLD (默认8)时，将内部结构单链表转为红黑树存储，红黑树节点由Node的子类TreeNode表示

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next; //单链表
  ... ...
}

构造函数

由下可知HashMap一共有四个构造函数：均未在构造函数里初始化hash table数组，只是设置属性：

loadFactor 和 threshhold

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  putMapEntries(m, false);
}

resize()

在put元素时会根据table是否为空来初始化table，或者在put元素后根据table的元素size是否超过threshold来扩容。而初始化table和对table进行扩容均是通过resize()实现的。如果table为null，则将threshold里的值作为initial capacity来初始化table。table不为空，则进行table size加倍扩容。由于使用的幂扩展，扩容后新table里的元素要么维持原来的index不变，要么index移动2的幂次方(oldCap)。

modCount

modCount记录HashMap结构化改变的次数，用于Iterator遍历HashMap时的并发修改异常探测(仅是do the best 不是绝对可靠，因为没加锁。。。)
Iterator的时候，每次遍历取Next，或执行remvoe的时候都要去检测modCount和Iterator初始化时的expectModCount相同，不同则会抛异常ConcurrentModificationException
同时，通过Iterator的remove方法在遍历的时候去删除元素会同时修改modCount和Iterator的expectModCount，所以没有问题(do the best)
Fast-Fail Iterator & Fail-Safe Iterator
Fast-Fail Iterator: 在iterator遍历时，不通过iterator的结构修改会抛异常ConcurrentModificationException
Fail-Safe Iterator：在iterator遍历时，可以不通过iterator来修改集合的结构，不会抛异常
JDK中使用Fast-Fail模式的集合：ArrayList、HashMap、Vector等
JDK中使用Fail-Safe模式的集合：ConcurrentHashMap、CopyOnWriteAraayList

put

//LinkedHashMap 移除旧节点示例
public static void main(String[] args) {
  // LinkedHashMap removeEldestEntry() 默认实现返回false，不起作用
  final int MAX = 2;

  // 构造匿名类继承自LinkedHashMap，并实现removeEldestEntry，每次插入节点时检测大小超过阈值，则自动删除旧节点
  LinkedHashMap<Integer, String> li_hash_map =
    new LinkedHashMap<Integer, String>() {
    protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest)
    {
      return size() > MAX;
    }
  };
  // 插入2个节点
  li_hash_map.put(1, "One");
  li_hash_map.put(2, "Two");

  //{1=One, 2=Two}
  System.out.println("" + li_hash_map);

  // 插入第三个节点，超出阈值
  li_hash_map.put(3, "Three");
  //{2=Two, 3=Three}
  System.out.println("" + li_hash_map);

  // 插入第四个节点，超出阈值
  li_hash_map.put(4, "Four");
  //{3=Three, 4=Four}
  System.out.println("" + li_hash_map);
}

get

首先根据key计算hash，然后通过hash与table length取余运算得出key-value所在的table的index，取出index处的key-value，再比较key，若没找到，再遍历链表比较。注意图中1和2处key的比较，使用 == 和 equals，表示HashMap的两个key相等的判断条件是：同样的key对象或者自定义的key.equals相等。由此也可知作为HashMap的Key对象必须实现hashCode方法和equals方法。hashCode用于确定key-value在数组中的index，equals用于比较查找key-value。

computeIfAbsent

1.8 HashMap computeIfAbsent存在数据丢失bug，参见https://bugs.openjdk.java.net/browse/JDK-8071667

1.8 ConcurrentHashMap computeIfAbsent存在死循环bug，参见https://bugs.openjdk.java.net/browse/JDK-8062841

1.7 与1.8区别

1.7采用数组+单链表，1.8采用数组+单链表+红黑树

1.7向单链表插入元素是头插（最近插入的元素被访问的概率更大），1.8向单链表插入元素是尾插（避免了链表成环的问题）。

1.7头插在扩容时，多线程下会导致链表成环。1.7扩容代码如下所示：

/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
  Entry[] src = table;
  int newCapacity = newTable.length;
  for (int j = 0; j < src.length; j++) {
    Entry<K,V> e = src[j];
    if (e != null) {
      src[j] = null;
      do {
        Entry<K,V> next = e.next; // 两个线程同时执行到此，然后发生线程切换
        int i = indexFor(e.hash, newCapacity); 
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
      } while (e != null);
    }
  }
}

1.7 和1.8 多线程插入数据时都会存在数据覆盖的现象：

比如两个线程同时put时，计算出的索引位置一样时，由于CPU时间片切换可能导致一个线程插入的值被另一个线程后插入的值覆盖了，而不是插入两个形成单链表。

再比如插入成功后都会对size++，很明显多线程环境下size++是线程不安全的，数据覆盖可能导致size少加了。

链表转红黑树

//链表长度超过8时，转红黑树
final void treeifyBin(java.util.HashMap.Node<K,V>[] tab, int hash) {
  int n, index; java.util.HashMap.Node<K,V> e;
  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    // 数组大小小于64，则走扩容，扩容数组至2倍原来大小
    resize();
  //找到链表头节点
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    //遍历Node链表，将Node链表元素转TreeNode链表
    java.util.HashMap.TreeNode<K,V> hd = null, tl = null;
    do {
      //调用replacementTreeNode，根据Node链表节点构造TreeNode节点
      java.util.HashMap.TreeNode<K,V> p = replacementTreeNode(e, null);
      if (tl == null)
        //TreeNode链表为空，则将TreeNode节点设置为首节点
        hd = p;
      else {
        //TreeNode链表不为空，则向TreeNode链表后添加TreeNode元素
        p.prev = tl;
        tl.next = p;
      }
      tl = p;
    } while ((e = e.next) != null);
    if ((tab[index] = hd) != null)
      //hd即是TreeNode链表，调用treeify将TreeNode链表转为红黑树
      hd.treeify(tab);
  }
}

treeifyBin将Node链表转化成TreeNode链表，然后调用hd.treeify将TreeNode链表转为红黑树：

hd指向的TreeNode链表如图所示：

红黑树

定义

关于红黑树：是一颗自平衡二叉树，通过它的5个特性限制确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。包含n个内部节点的红黑树的高度是O(logn)。因此它可以在O(logn)时间内完成查找，插入和删除。

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NULL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

红黑树的平衡：满足以上性质的红黑树即是平衡的

关于旋转（左旋和右旋）和变色：

在插入和删除操作之后，红黑树可能会失去平衡，通过旋转和变色可以使得红黑树重新达到平衡。

插入

插入前提：

1. 待插入节点默认为红色，因为插入红色节点不会破坏之前的平衡状态，减少由于不平衡需要进行的旋转变色操作
2. 所有插入操作都是在叶子节点进行的，这点是由二叉树的特性保证的

插入情形1: 没有父节点

插入节点就是根节点，修改颜色为红色即可

插入情形2: 有父节点，且父节点是黑色

直接插入红色节点，不会破坏平衡

插入情形3: 有父节点，且父节点是红色，此时插入节点后，有两个连续的红色节点了，需要进行调整，调整的依据是根据周边环境来调整。而且插入之前是平衡的，则肯定存在祖父节点，且祖父节点是黑色。

插入情形3.1: 父节点是红色，且存在叔父节点，则叔父节点必是红色，因为插入之前是平衡的

注意：为什么要把PP设为红色呢，PP保持黑色，还是平衡的，不更简单吗？因为黑色越多，树就越高，查询次数越多。

此时PP是红色，但是树已经是平衡的了，只是可能还不满足性质【不能有两个连续的红色节点】，需要将PP当作新插入的节点继续处理，继续处理可能会碰到【存在叔父节点，叔父节点是黑色】的情况。

插入情形3.2: 父亲节点是红色，不存在叔父节点或存在叔父节点，叔父节点是黑色（这种情况只能是自底向上递归时才存在，此时整颗树已经是黑色节点平衡的了，和初次插入【父亲节点是红色，不存在叔父节点】的处理方式一样）

插入操作中的自底向上gif参考：

删除

红黑树删除操作步骤：

1. 查找待删除的节点

2. 从待删除节点开始查找代替节点（待删除节点的左子树的最大节点或者右子树的最小节点）【跟二叉树的删除一样，要么用待删除节点的左子树顶上，要么用待删除节点的右子树顶上】

3. 复制代替节点的值到待删除节点，待删除节点颜色不变，删除操作转移到代替节点。

4. 删除代替节点（代替节点必定是叶子节点（不考虑NIL节点））

5. 如果被删除的代替节点是红色，直接删除即可，不破坏平衡。

6. 如果被删除的代替节点是黑色，需要分情况处理，重新处理自平衡

   首先代替节点是黑色，则代替节点必然有兄弟节点，然后分别考虑各种情况如下：

   情况1: 兄弟节点是黑色，兄弟节点没有子节点

   此时，兄弟节点没有红色节点可借，需要进行自底向上的处理，处理之前由于删掉了R，为了保持当前子树的平衡需要将S置为红色，然后将P当作待删除的黑色节点进行自底向上的继续处理。意思就是我保证当前子树平衡，后续的平衡交给父节点处理。

   情况2: 兄弟节点是黑色，兄弟节点有红色子节点

   此时可以通过旋转和变色来保证删除R后，当前子树依然是黑色节点平衡的。

   

   情况3: 兄弟节点是红色，则父亲节点必是黑色，兄弟节点必有两个黑色节点

   此时，可以通过旋转变色即可重新达到平衡。

以上讨论的是待删除节点是父节点的左子节点的情况，待删除节点是父节点的右子节点的处理情况同上， 只是操作方向相反。

删除操作中的自底向上gif参考：

如果对红黑树的插入删除情况理解有困难可以参考红黑树Virsualization。