HashMap jdk8

• 构造函数，负载因子默认0.75F，影响map扩容//TODO，提供根据参数计算负载因子
• 继承AbstractMap，实现Map，大部分API都在AbstractMap抽象类中模板方法实现

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

• put，hashMap中维护了一个数组，其中存放链表。超过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) {        Node
    
     [] tab; Node
     
       p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        //根据table的长度位算法（i = (n - 1) & hash）分配一个index，空则填入node        //@one        if ((p = tab[i = (n - 1) & hash]) == null)            //没有hash碰撞的情况下，put完毕            tab[i] = newNode(hash, key, value, null);        else {            Node
      
        e; K k;            //新k-v全等于已有元素，进入@four覆盖            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) {                    //@two，相同hash值，添加为链表下一节点                    //有hash碰撞的情况下，put完毕                    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;                }            }            //@four 覆盖已有值            if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        //防止foreach异常//TODO        ++modCount;        if (++size > threshold)            //重新分配map            resize();        afterNodeInsertion(evict);        return null;    }
       
      
     
    

• get

public V get(Object key) {        Node
    
      e;        return (e = getNode(hash(key), key)) == null ? null : e.value;    }    /**     * Implements Map.get and related methods     *     * @param hash hash for key     * @param key the key     * @return the node, or null if none     */    final Node
     
       getNode(int hash, Object key) {        Node
      
       [] tab; Node
       
         first, e; int n; K k;        //同put算法(n - 1) & hash，定位数组中相同hash的链表        if ((tab = table) != null && (n = tab.length) > 0 &&            (first = tab[(n - 1) & hash]) != null) {            //这里always check是，可能大部分情况hashMap碰撞情况很小            if (first.hash == hash && // always check first node                ((k = first.key) == key || (key != null && key.equals(k))))                return first;            if ((e = first.next) != null) {                //红黑树操作                if (first instanceof TreeNode)                    return ((TreeNode
        
         )first).getTreeNode(hash, key);                do {                    //开始遍历相同hash的链表，直到找到为止                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        return e;                } while ((e = e.next) != null);            }        }        return null;    }
        
       
      
     
    

• EntrySet
• entrySet返回Set<Node>结构，真正在遍历map时，会遍历HashMap里table[]，Node链表。见nextNode();

public Set
    
     
      > entrySet() {        Set
      
       
        > es;        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;    }    final class EntrySet extends AbstractSet
        
         
          > { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator
          
           
            > iterator() { return new EntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry
             e = (Map.Entry
            ) o; Object key = e.getKey(); Node
            
              candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } final class EntryIterator extends HashIterator implements Iterator
             
              
               > { public final Map.Entry
               
                 next() { return nextNode(); } } final Node
                
                  nextNode() { Node
                 
                  [] t; Node
                  
                    e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); //table[]赋值 if ((next = (current = e).next) == null && (t = table) != null) { //真正遍历table[] ，链表 do {} while (index < t.length && (next = t[index++]) == null); } return e; }
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

• KeySet,values，同理，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; }}
     
    

• TODO map扩容