java容器系列之 ------------ HashMap的实现原理

        HashMap的实现原理在JDK1.8的时候有做一些修改。

        JDK1.7的时候HashMap是hash表加链表的数据结构，如果通过key计算出来的hash值出现了hash碰撞，就将node添加到链表中，直到hash表需要扩容的时候，再进行rehash。JDK7的数据结构如下图：

         JDK1.8中针对之前的HashMap的结构，做了优化，因为之前的结构中是有缺陷的。在JDK1.7中，有一种极端情况，就是如果所有数据都有相同的hash值，那么所有数据都在一个链表中，这是时间复杂度就是O(n)。所以，在JDK1.8中，正对链表接口做了修改，当链表的长度大于8的时候，就会将链表结构修改为红黑树。结构如下：

​​​​​​​ 

         一下是JDK1.8的HashMap的数据结构，一个是链表的节点，一个是红黑树的节点：

// 这个只是HashMap中Node类的部分代码，表明：这个是链表的节点，
// 有数据（key,value）和指针（next）
static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
}

// 这个只是HashMap中TreeNode类的部分代码，表明：这个是红黑树的节点，
// 有数据（key,value，继承至linkedHashMap,而linkedHashMap是继承了HashMap）
// 和指针（parent, left,right）和颜色（boolean = red,默认是红节点）
static final class TreeNode extends linkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node next) {
        super(hash, key, val, next);
    }
}