Java集合的学习先理清数据结构：

 

一、属性

//哈希桶，存放链表。 长度是2的N次方，或者初始化时为0.    transient Node
     
      [] table;    //最大容量 2的30次方    static final int MAXIMUM_CAPACITY = 1 << 30;    //默认的加载因子    static final float DEFAULT_LOAD_FACTOR = 0.75f;    //加载因子，用于计算哈希表元素数量的阈值。  threshold = 哈希桶.length * loadFactor;    final float loadFactor;    //哈希表内元素数量的阈值，当哈希表内元素数量超过阈值时，会发生扩容resize()。    int threshold;
     

二、构造函数

public HashMap() {        //默认构造函数，赋值加载因子为默认的0.75f        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted    }    public HashMap(int initialCapacity) {        //指定初始化容量的构造函数        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    //同时指定初始化容量 以及 加载因子， 用的很少，一般不会修改loadFactor    public HashMap(int initialCapacity, float loadFactor) {        //边界处理        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        //初始容量最大不能超过2的30次方        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        //显然加载因子不能为负数        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        this.loadFactor = loadFactor;        //设置阈值为>=初始化容量的 2的n次方的值        this.threshold = tableSizeFor(initialCapacity);    }    //新建一个哈希表，同时将另一个map m 里的所有元素加入表中    public HashMap(Map
      m) {        this.loadFactor = DEFAULT_LOAD_FACTOR;        putMapEntries(m, false);    }

三、主要方法

get

/**     * get     * 1.先从数组中取，取到hash值相等且equals的，直接返回     * 2.先从数组中取，取到hash值相等且!equals，到链表/红黑树中取     */    // 每一个节点结构    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;        }    }        public V get(Object key) {        Node
         
           e;        return (e = getNode(hash(key), key)) == null ? null : e.value;    }        final Node
          
            getNode(int hash, Object key) { Node
           
            [] tab;//Entry对象数组 Node
            
              first,e; //在tab数组中经过散列的第一个位置 int n; K k; /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/ //也就是说在一条链上的hash值相同的 if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { /*检查第一个Node是不是要找的Node*/ if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同 return first; /*检查first后面的node*/ if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode
             
              )first).getTreeNode(hash, key); /*遍历后面的链表，找到key值和hash值都相同的Node*/ do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
             
            
           
          
         
        
       
      
     

 

put

/**     * put     * 1.数组下标没有对应hash值，直接newNode()添加     * 2.数组下标有对应hash值，添加到链表最后     * 3.链表超过最大长度(8)，将链表改为红黑树再添加元素     */    public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }        final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {         //tab存放 当前的哈希桶， p用作临时链表节点           Node
     
      [] tab; Node
      
        p; int n, i;         //如果当前哈希表是空的，代表是初始化         if ((tab = table) == null || (n = tab.length) == 0)             //那么直接去扩容哈希表，并且将扩容后的哈希桶长度赋值给n             n = (tab = resize()).length;         //如果当前index的节点是空的，表示没有发生哈希碰撞。 直接构建一个新节点Node，挂载在index处即可。         //这里再啰嗦一下，index 是利用 哈希值 & 哈希桶的长度-1，替代模运算         if ((p = tab[i = (n - 1) & hash]) == null)             tab[i] = newNode(hash, key, value, null);         else {
   //否则 发生了哈希冲突。             //e             Node
       
         e; K k;             //如果哈希值相等，key也相等，则是覆盖value操作             if (p.hash == hash &&                 ((k = p.key) == key || (key != null && key.equals(k))))                 e = p;//将当前节点引用赋值给e             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);                         //如果追加节点后，链表数量》=8，则转化为红黑树                         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;                 }             }             //如果e不是null，说明有需要覆盖的节点，             if (e != null) { // existing mapping for key                 //则覆盖节点值，并返回原oldValue                 V oldValue = e.value;                 if (!onlyIfAbsent || oldValue == null)                     e.value = value;                 //这是一个空实现的函数，用作LinkedHashMap重写使用。                 afterNodeAccess(e);                 return oldValue;             }         }         //如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。                 //修改modCount         ++modCount;         //更新size，并判断是否需要扩容。         if (++size > threshold)             resize();         //这是一个空实现的函数，用作LinkedHashMap重写使用。         afterNodeInsertion(evict);         return null;    }
        
       
      
     

 

remove

/**     * reomve     */    public V remove(Object key) {        Node
     
       e;        return (e = removeNode(hash(key), key, null, false, true)) == null ? null                : e.value;    }    final Node
      
        removeNode(int hash, Object key, Object value,            boolean matchValue, boolean movable) {        Node
       
        [] tab;        Node
        
          p;        int n, index;        if ((tab = table) != null && (n = tab.length) > 0                && (p = tab[index = (n - 1) & hash]) != null) {            Node
         
           node = null, e;            K k;            V v;            if (p.hash == hash                    && ((k = p.key) == key || (key != null && key.equals(k))))                node = p;            else if ((e = p.next) != null) {                if (p instanceof TreeNode)                    node = ((TreeNode
          
           ) p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key .equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value .equals(v)))) { if (node instanceof TreeNode) ((TreeNode
           
            ) node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }
           
          
         
        
       
      
     

resize

final Node
     
      [] resize() {        //oldTab 为当前表的哈希桶        Node
      
       [] oldTab = table;        //当前哈希桶的容量 length        int oldCap = (oldTab == null) ? 0 : oldTab.length;        //当前的阈值        int oldThr = threshold;        //初始化新的容量和阈值为0        int newCap, newThr = 0;        //如果当前容量大于0        if (oldCap > 0) {            //如果当前容量已经到达上限            if (oldCap >= MAXIMUM_CAPACITY) {                //则设置阈值是2的31次方-1                threshold = Integer.MAX_VALUE;                //同时返回当前的哈希桶，不再扩容                return oldTab;            }//否则新的容量为旧的容量的两倍。             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)//如果旧的容量大于等于默认初始容量16                //那么新的阈值也等于旧的阈值的两倍                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;//此时新表的容量为默认的容量 16            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的阈值为默认容量16 * 默认加载因子0.75f = 12        }        if (newThr == 0) {
   //如果新的阈值是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) {                //取出当前的节点 e                Node
         
           e;                //如果当前桶中有元素,则将链表赋值给e                if ((e = oldTab[j]) != null) {                    //将原哈希桶置空以便GC                    oldTab[j] = null;                    //如果当前链表中就一个元素，（没有发生哈希碰撞）                    if (e.next == null)                        //直接将这个元素放置在新的哈希桶里。                        //注意这里取下标 是用 哈希值 与 桶的长度-1 。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高                        newTab[e.hash & (newCap - 1)] = e;                        //如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树（暂且不谈 避免过于复杂， 后续专门研究一下红黑树）                    else if (e instanceof TreeNode)                        ((TreeNode
          
           )e).split(this, newTab, j, oldCap); //如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。 else { // preserve order //因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位= low位+原哈希桶容量 //低位链表的头结点、尾节点 Node
           
             loHead = null, loTail = null; //高位链表的头节点、尾节点 Node
            
              hiHead = null, hiTail = null; Node
             
               next;//临时节点 存放e的下一个节点 do { next = e.next; //这里又是一个利用位运算 代替常规运算的高效点： 利用哈希值 与 旧的容量，结果只有两种 0或者oldCap，结果是0则存放在低位，否则存放在高位 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); //将低位链表存放在原index处， if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //将高位链表存放在新index处 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
             
            
           
          
         
        
       
      
     

 

遍历

/**     * 遍历 主要看方法nextNode()     */    final class KeyIterator extends HashIterator implements Iterator
     
       {        public final K next() {            return nextNode().key;        }    }    final class ValueIterator extends HashIterator implements Iterator
      
        {        public final V next() {            return nextNode().value;        }    }    final class EntryIterator extends HashIterator implements            Iterator
       
        
         > {        public final Map.Entry
         
           next() {            return nextNode();        }    }        abstract class HashIterator {        Node
          
            next; // next entry to return Node
           
             current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node
            
             [] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do { } while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } final Node
             
               nextNode() { Node
              
               [] t; Node
               
                 e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do { } while (index < t.length && (next = t[index++]) == null); } return e; } public final void remove() { Node
                
                  p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount)　　 throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }
                
               
              
             
            
           
          
         
        
       
      
     

 

四、数组的长度是2的次幂？ 数组下表计算e.hash & (table.length- 1)？ hash()方法(h = key.hashCode()) ^ (h >>> 16)？

1、tableSizeFor(int cap)保证数组容量是2的次幂

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;    }

 

2、2的次幂-1（即table.length- 1）得到是数用二进制表示每一位都是1。

3、将e.hash放进table数组中，需要e.hash%(table.length- 1)得到下标；

这里用e.hash&(table.length- 1)代替e.hash%(table.length- 1)，位运算代替除法；

e.hash&(table.length- 1)类似Integer类的toUnsignedLong() 方法：((long) x) & 0xffffffffL，只保留低位；

4、因为e.hash&(table.length- 1)时，比(table.length- 1)高的位都成0了，只用到了e.hash的低位；

e.hash = (h = key.hashCode()) ^ (h >>> 16)，使key的hashCode值高16位不变，低16位 由（高16位）^（低16位）得到；

e.hash&(table.length- 1)时用到的e.hash的低位也有高16位参与进来，减少了冲突碰撞。

 举例可参考：

 

 

参考资料：