乐趣区

关于hashmap:HashMap-的底层结构

jiezi 
 几个重要的成员变量：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
/**
* 构造函数中没有指明负载因子的时候默认为 0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 数化的阈值
static final int TREEIFY_THRESHOLD = 8;
// 进化为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 可对桶进行树型化（变为红黑树）的最小表容量。*（否则，如果一个桶中的节点太多，则会调整表的大小。）* 应至多为 4 *TREEIFY_THRESHOLD，以防止调整大小和树调整阈值之间的抵触。*/
static final int MIN_TREEIFY_CAPACITY = 64; // 链表变为红黑树时数组容量的最小值

// resize 的阈值 (capacity * load factor).
int threshold;

HashMap 是一个用于存储 Key-Value 键值对的汇合，每一个键值对也叫做 Node(jdk 1.7 中为 Entry)。

transient Node<K,V>[]table;
 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
       consrtuctor;
       Getter /setter ;
       hashCode;
       equals;
       ...
}

常应用的是两个办法：Get 和 Put。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
public V putIfAbsent(K key, V value) {return putVal(hash(key), key, value, true, true);
}

put 和 putIfAbsent 的区别就在于传入的一个参数（onlyIfAbsent）的不同。也就是 putIfAbsent 办法插入数据的时候，如果没有呈现过这个值，就插入，呈现过这个值就不笼罩，不写入。put 办法在插入数据时，如果呈现过，间接笼罩之前的数据。

Java8 之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去。Java7 的时候是采纳头插法，然而在多线程的状况下会呈现死循环的状况。
Jdk1.8 开始采纳尾插法

Put() 办法的过程：

例如 map.put(“key01″,”value01”);

刚开始，如果 tab 是空的或者表长度为 0，就会对 tab 进行扩容。
而后依据 key 的 hash 值去计算 key 在 tab 中的下标。(n – 1) & hash。咱们将计算的构造记为 i，即 tab[i] 代表以后节点。如果 tab[i] 为 null，那么间接将该节点插入这个地位。

 如果不是雷同的节点，它就会判断书否为一个红黑树的节点，如果是的话，就将该节点插入红黑树。如果不是红黑树的节点，那么会遍历整个链表，并判断是否存在和以后节点（key）雷同的节点，如果存在雷同的节点，那么将这个节点的 value 笼罩之前的, 并且会查看以后链表的大小，如果大于阈值，会将这个链表进行树化，变为一颗红黑树。最初会对这个 tab 的大小进行查看，看减少节点后的 tab 是否须要进行扩容，这个阈值等于容量乘负载因子。
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab;
         Node<K,V> p; 
         int n, i;
        // 如果 tab 为空或者长度为 0，则 resize() 扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
         // 计算 index 
        if ((p = tab[i = (n - 1) & hash]) == null)
         // tab[i] 为 null，直接插入
            tab[i] = newNode(hash, key, value, null);
        else {//  tab[i] 不为空的状况下
            Node<K,V> e; K k;
            // 判断 tab[i] 的 key.hash 是否和以后插入节点的 key 的 hash 相等
            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
               // e 节点指向 tab[i]，也就是 p
                e = p;
            // 如果不相等，判断是否是一个树节点 
            else if (p instanceof TreeNode)
              // 是一个树节点，那么将这个节点插入这可红黑树中
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 不是一颗树节点
                for (int binCount = 0; ; ++binCount) {// 遍历链表达到尾部
                    if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                        // 判断是否达到树化的阈值
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 对 tab 进行树化
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 判断两个节点的 key 是否雷同，雷同则跳出循环
                    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                 // 是否须要对原来的进行笼罩
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

为啥 tab 的大小必须为 2 的 n 次的幂

为啥是这样算的呢？因为

计算出来的 hash 值有些不在 tab 中，为了映射到 tab 中，就须要对 hash 值进行取模运算，即 hash%n。当 n 为 2 的幂的时候，hash%n 就等于 (n – 1) & hash 了。采纳二进制位操作 &，绝对于 % 可能进步运算效率，这也就是为什么 tab 的长度为 2 的幂了。

举例:

若 a = 10 , b = 8 , 10 与 8 取余应得 2.

8 的二进制为: 1000 ; 7 的二进制为: 0111.

10—> 1011

7 —> 0111

1011

0111

0011

resize（）办法这篇文章不错 –> 深刻了解 HashMap(四): 要害源码逐行剖析之 resize 扩容

退出移动版