本文共 11783 字，大约阅读时间需要 39 分钟。

正文

我们来看看HashMap的put数据的时候，是怎么处理的:

/**     * Implements Map.put and related methods     *     * @param hash hash for key     * @param key the key     * @param value the value to put     * @param onlyIfAbsent if true, don't change existing value     * @param evict if false, the table is in creation mode.     * @return previous value, or null if none     */    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node
   
    [] tab; Node
    
      p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        else {            Node
     
       e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode
      
       )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                            treeifyBin(tab, hash);                        break;                    }                    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;    }
      
     
    
   

计算HashCode的操作:

/**     * Computes key.hashCode() and spreads (XORs) higher bits of hash     * to lower.  Because the table uses power-of-two masking, sets of     * hashes that vary only in bits above the current mask will     * always collide. (Among known examples are sets of Float keys     * holding consecutive whole numbers in small tables.)  So we     * apply a transform that spreads the impact of higher bits     * downward. There is a tradeoff between speed, utility, and     * quality of bit-spreading. Because many common sets of hashes     * are already reasonably distributed (so don't benefit from     * spreading), and because we use trees to handle large sets of     * collisions in bins, we just XOR some shifted bits in the     * cheapest possible way to reduce systematic lossage, as well as     * to incorporate impact of the highest bits that would otherwise     * never be used in index calculations because of table bounds.     */    static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }

解决冲突的核心逻辑代码:

Node
   
     e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode
    
     )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                            treeifyBin(tab, hash);                        break;                    }                    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;            }这里再贴一下创建Node的代码:Node
     
       newNode(int hash, K key, V value, Node
      
        e) {        LinkedHashMap.Entry
       
         p =            new LinkedHashMap.Entry
        
         (hash, key, value, e); linkNodeLast(p); return p; }
        
       
      
     
    
   

HashMap的扩容

说道HashMap的扩容，我们先来看看HashMap的resize()方法。

/**     * Initializes or doubles table size.  If null, allocates in     * accord with initial capacity target held in field threshold.     * Otherwise, because we are using power-of-two expansion, the     * elements from each bin must either stay at same index, or move     * with a power of two offset in the new table.     *     * @return the table     */    final Node
   
    [] resize() {        Node
    
     [] oldTab = table;        int oldCap = (oldTab == null) ? 0 : oldTab.length;        int oldThr = threshold;        int newCap, newThr = 0;        if (oldCap > 0) {            if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE;                return oldTab;            }            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)                newThr = oldThr << 1; // double threshold        }        else if (oldThr > 0) // initial capacity was placed in threshold            newCap = oldThr;        else {               // zero initial threshold signifies using defaults            newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }        if (newThr == 0) {            float ft = (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);        }        threshold = newThr;        @SuppressWarnings({"rawtypes","unchecked"})            Node
     
      [] newTab = (Node
      
       [])new Node[newCap];        table = newTab;        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {                Node
       
         e;                if ((e = oldTab[j]) != null) {                    oldTab[j] = null;                    if (e.next == null)                        newTab[e.hash & (newCap - 1)] = e;                    else if (e instanceof TreeNode)                        ((TreeNode
        
         )e).split(this, newTab, j, oldCap); else { // preserve order Node
         
           loHead = null, loTail = null; Node
          
            hiHead = null, hiTail = null; Node
           
             next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
           
          
         
        
       
      
     
    
   

HashMap默认的容量是DEFAULT_INITIAL_CAPACITY，16。

默认容量大小和阈值:

newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

DEFAULT_LOAD_FACTOR负载因子: 0.75。至于为什么是0.75,这里查阅了一下资料:

JDK中的解释就是尽量减少rehash的次数，并且在时间和空间上做了一个很好的折中。同时，如果这个值设置的比较大的话，桶中的键值碰撞的几率就会大大上升。

扩容的核心代码:

for (int j = 0; j < oldCap; ++j) {            Node
   
     e;            if ((e = oldTab[j]) != null) {                oldTab[j] = null;                if (e.next == null)                    newTab[e.hash & (newCap - 1)] = e;                else if (e instanceof HashMap.TreeNode)                    ((HashMap.TreeNode
    
     )e).split(this, newTab, j, oldCap);                else { // preserve order                    Node
     
       loHead = null, loTail = null;                    Node
      
        hiHead = null, hiTail = null;                    Node
       
         next;                    do {                        next = e.next;                        if ((e.hash & oldCap) == 0) {                            if (loTail == null)                                loHead = e;                            else                                loTail.next = e;                            loTail = e;                        }                        else {                            if (hiTail == null)                                hiHead = e;                            else                                hiTail.next = e;                            hiTail = e;                        }                    } while ((e = next) != null);                    if (loTail != null) {                        loTail.next = null;                        newTab[j] = loHead;                    }                    if (hiTail != null) {                        hiTail.next = null;                        newTab[j + oldCap] = hiHead;                    }                }            }        }
       
      
     
    
   

这个桶中的内容有可能是链表，也有可能是红黑树。

Node
   
     loHead = null, loTail = null;Node
    
      hiHead = null, hiTail = null;Node
     
       next;do {    next = e.next;    if ((e.hash & oldCap) == 0) {        if (loTail == null)            loHead = e;        else            loTail.next = e;        loTail = e;    }    else {        if (hiTail == null)            hiHead = e;        else            hiTail.next = e;        hiTail = e;    }} while ((e = next) != null);if (loTail != null) {    loTail.next = null;    newTab[j] = loHead;}if (hiTail != null) {    hiTail.next = null;    newTab[j + oldCap] = hiHead;}
     
    
   

以上是针对链表结构的一个扩容。

loHead这部分表示的是在扩容之后，在table中的位置没有变动的数据，然后将他们拼装到链表中，然后在后面拼接到newTab[j]中。

hiHead这部分表示的是在扩容之后，位置有发生变动，然后将他们拼装的链表拼接到newTab[j + oldCap]中。

注意: 在我们这个Jdk1.8中，不会发生扩容的死循环.

当我们的链表的大小超过7的时候，就会将链表转换成红黑树:

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            treeifyBin(tab, hash);        break;    }    if (e.hash == hash &&        ((k = e.key) == key || (key != null && key.equals(k))))        break;    p = e;}

TREEIFY_THRESHOLD这里的数值是为8

树的分裂

关于红黑树的原理，建议参考这篇文章: 

((TreeNode
   
    )e).split(this, newTab, j, oldCap);
   

/** * Splits nodes in a tree bin into lower and upper tree bins, * or untreeifies if now too small. Called only from resize; * see above discussion about split bits and indices. * * @param map the map * @param tab the table for recording bin heads * @param index the index of the table being split * @param bit the bit of hash to split on */final void split(HashMap
   
     map, Node
    
     [] tab, int index, int bit) {    TreeNode
     
       b = this;    // Relink into lo and hi lists, preserving order    TreeNode
      
        loHead = null, loTail = null;    TreeNode
       
         hiHead = null, hiTail = null;    int lc = 0, hc = 0;    for (TreeNode
        
          e = b, next; e != null; e = next) { next = (TreeNode
         
          )e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } }}/* ------------------------------------------------------------ */// Red-black tree methods, all adapted from CLR
         
        
       
      
     
    
   

欢迎在留言区留下你的观点，一起讨论提高。如果今天的文章让你有新的启发，学习能力的提升上有新的认识，欢迎转发分享给更多人。

Android开发资料+面试架构资料 免费分享 点击链接 即可领取

转载地址：http://vnjhb.baihongyu.com/