hashMap浅析

Java

于福豪

字数统计: 11.2k阅读时长: 54 min

 2019/01/17   Share

HashMap原理浅析

手写一个简单的hashmap

public class MyHashMap<K, V> {
    private Entry[] table;               //定义一个Entry类型的数组
    private static Integer CAPACITY = 8; //数组容量
    private int size = 0;                //定义元素个数

//初始化MyHashMap并创建Entry数组
    public MyHashMap() {
        this.table = new Entry[CAPACITY];
    }
//获取MyHashMap中元素个数
    public int size() {
        return size;
    }
//get方法
    public V get(K key) {
        int hash = key.hashCode();  //获取哈希值
        int i = hash % CAPACITY;    //通过取余操作得到数组下标
        //循环链表找到相对应的key值
        for (Entry<K, V> entry = table[i]; entry != null; entry = entry.next) {
            if (entry.k.equals(key)) {
                return entry.v;
            }
        }
        return null;
    }
//put方法
    public V put(K key, V value) {
        int hash = key.hashCode();//657765%8
        int i = hash % CAPACITY;
        //put方法返回值如果是覆盖添加元素，则会返回被覆盖元素的值，循环遍历链表查看该位置是否有已存在的值
        for (Entry<K, V> entry = table[i]; entry != null; entry = entry.next) {
            if (entry.k.equals(key)) {
                V oldValue = entry.v;
                entry.v = value;
                return oldValue;
            }
        }
        //将put的元素添加进来
        addEntry(key, value, i);
        //如果是最新添加的值则会返回null
        return null;
    }
    //增加新的节点
    private void addEntry(K key, V value, int i) {
        Entry entry = new Entry(key, value, table[i]); //new一个新的entry对象，并指向该地方最初的位置（在链表头部新加节点）
        table[i] = entry;                              //将该节点移动到最初的位置
        size++;                                        //元素个数+1
    }

    //节点类（链表）
    class Entry<K, V> {
        private K k;         //key
        private V v;         //value
        private Entry next;  //下一个节点

        public Entry(K k, V v, Entry next) {
            this.v = v;
            this.k = k;
            this.next = next;
        }

        public V getV() {
            return v;
        }

        public void setV(V v) {
            this.v = v;
        }

        public K getK() {
            return k;
        }

        public void setK(K k) {
            this.k = k;
        }

        public Entry getNext() {
            return next;
        }

        public void setNext(Entry next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        MyHashMap<String, String> myHashMap = new MyHashMap<>();
        for (int i = 0; i < 10; i++) {
            myHashMap.put("a"+i,"b"+i);
        }
        System.out.println(myHashMap.get("a1"));
    }
}

jdk7中HashMap源码解析

jdk7中hashmap结构

源码解析（主要方法）

hashmap结构

//存放链表的数组
transient Entry[] table;  
//键值对，持有指向下一个Entry的引用，由此构成单向链表
static class Entry<K,V> implements Map.Entry<K,V> {  
    final K key;  
    V value;  
    //指向下一节点
    Entry<K,V> next;  
    final int hash;  
    ……  
}

？？transient的用意：

解释：java语言的关键字，变量修饰符，如果用transient声明一个实例变量，当对象存储时，它的值不需要维持。换句话来说就是，用transient关键字标记的成员变量不参与序列化过程。
transient 是表明该数据不参与序列化。因为 HashMap 中的存储数据的数组数据成员中，数组还有很多的空间没有被使用，没有被使用到的空间被序列化没有意义。所以没有使用默认的序列化的方法，自己手动重写了 readObject/writeObject() 方法，只序列化实际存储元素的数组，增加效率。
由于不同的虚拟机对于相同 hashCode 产生的 Code 值可能是不一样的，如果你使用默认的序列化，那么反序列化后，元素的位置和之前的是保持一致的，可是由于 hashCode 的值不一样了，那么定位函数 indexOf（）返回的元素下标就会不同，这样不是我们所想要的结果 .

属性常量

/**
 * 默认的初始化数组长度，HashMap中数组的值必须是2的N次幂？？
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
 * HashMap中散列数组长度的最大值，1073741824
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认的负载因子，当HashMap中元素的数量达到容量的75%时，进行扩容。????什么时候会进行扩容
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * HashMap的存储结构
 */
transient Entry<K,V>[] table;

/**
 * HashMap中元素（即键-值对）的数量
 */
transient int size;

/**
 * HashMap的重构阈值，它的值为容量和负载因子的乘积。在HashMap中所有桶中元素的总数量达到了这个重构阈值之后，HashMap将进行resize操作以自动扩容。
 */
int threshold;

/**
 * 负载因子，它和容量一样都是HashMap扩容的决定性因素。    
 */
final float loadFactor;

/**
 * 表示HashMap被结构化更新的次数，比如插入、删除等会更新HashMap结构的操作次数，用于实现迭代器快速失败行为。
 */
transient int modCount;

/**
 * 默认的阀值 
 */
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

/**
 * 表示是否要对字符串键使用备选哈希函数      
 */   
 transient boolean useAltHashing;

/**
 * 一个与当前实例关联并且可以减少哈希碰撞概率，应用于键的哈希码计算的随机种子。     
 */
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);

构造器

public HashMap(int initialCapacity, float loadFactor) {
        //校验初始化容量大小
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);
        //初始化容量是否大于容量的最大值
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //校验加载因子
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        //使容量为2的N次方
        while (capacity < initialCapacity)
            capacity <<= 1;

        //加载因子
        this.loadFactor = loadFactor;
        //重构阈值
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        //跟hash值的计算相关
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

put方法

public V put(K key, V value) {
        //如果键是NULL，调用putForNullKey方法。
        if (key == null)
            return putForNullKey(value);
        //计算hash值
        int hash = hash(key);
        //根据hash值计算下标值
        int i = indexFor(hash, table.length);
        //遍历该数组中的链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果其hash值相等且键相等，将新值替换旧值，并返回旧值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //只要涉及到元素个数变化就会++(用于Fail-Fast机制)
        modCount++;
        //该桶中没有存放元素，或者没有元素的键与要PUT元素的键匹配，插入新节点
        addEntry(hash, key, value, i);
        return null;
    }

putForNullKey方法：

private V putForNullKey(V value) {
       //遍历第一个桶中的链表
       for (Entry<K,V> e = table[0]; e != null; e = e.next) {
           //如果链表中有元素的键为NULL，将新值替换旧值，并返回旧值
           if (e.key == null) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }
       modCount++;
       //第一个桶中没有存放元素或没有节点的键为null的，插入新节点
       addEntry(0, null, value, 0);
       return null;
   }

hash方法

final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                //对字符串键使用备选哈希函数
                return sun.misc.Hashing.stringHash32((String) k);
            }
            //随机种子,用来降低冲突发生的几率
            h = hashSeed;
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        //混合高低位
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

>>：带符号右移。正数右移高位补0，负数右移高位补1。比如：

4 >> 1，结果是2；-4 >> 1，结果是-2。-2 >> 1，结果是-1。

>>>：无符号右移。无论是正数还是负数，高位通通补0。

对于正数而言，>>和>>>没区别。

对于负数而言，-2 >>> 1，结果是2147483647（Integer.MAX_VALUE），-1 >>> 1，结果是2147483647（Integer.MAX_VALUE）。

所以，要判断两个数符号是否相同时，可以这么干：

1	return ((a >> 31) ^ (b >> 31)) == 0;

indexFor方法：

static int indexFor(int h, int length) {
    //把hash值和数组的长度进行“与”操作等价于对长度取余，但是效率比较高
    return h & (length-1);
}

？？为什么容量是2的次方

resize扩容方法：

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //扩容前的容量已经达到最大容量，将阈值设置为整型的最大值
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //创建新容量的数组
        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        //计算是否需要对键重新进行哈希码的计算
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        /**
         * 将原有所有的entry迁移至新的entry数组中
         * 在迁移时，entry在entry数组中的绝对位置可能会发生变化
         * 这就是为什么HashMap不能保证存储条目的顺序不能恒久不变的原因
         */
        transfer(newTable, rehash);
        table = newTable;
        //重新计算重构阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

addEntry方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
        //如果尺寸已将超过了阈值并且桶中索引处不为null
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //扩容2倍
            resize(2 * table.length);
            //重新计算哈希值
            hash = (null != key) ? hash(key) : 0;
            //重新计算下标
            bucketIndex = indexFor(hash, table.length);
        }
        //创建节点
        createEntry(hash, key, value, bucketIndex);
    }

？？什么时候会扩容

jdk7中resize，只有当 size>=threshold并且 table中的那个槽中已经有Entry时，才会发生resize。即有可能虽然size>=threshold，但是必须等到每个槽都至少有一个Entry时，才会扩容。（误区超过阀值就会扩容）

transfer方法：

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍历当前的table，将里面的元素添加到新的newTable中
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    //重新计算hash值
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //计算下标
                int i = indexFor(e.hash, newCapacity);
                //插入到链表头部
                e.next = newTable[i];
                //存放在数组下标i中,所以扩容后链表的顺序与原来相反
                newTable[i] = e;
                e = next;
            }
        }
    }

？？jdk7中死循环问题

createEntry方法：

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        //把该节点插到链表头部
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

get方法

public V get(Object key) {
        //如果键为null，调用getForNullKey方法
        if (key == null)
            return getForNullKey();
        //键不为null，调用getEntry方法
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

getForNullKey方法：

private V getForNullKey() {
        //遍历第一个数组中的链表，因为putForNullKey是把NULL键存放到第一个数组中。
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

getEntry方法：

final Entry<K,V> getEntry(Object key) {

        //计算键的hash值
        int hash = (key == null) ? 0 : hash(key);
        //遍历对应桶数组中的链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

romove方法

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

removeEntryForKey方法：

final Entry<K,V> removeEntryForKey(Object key) {
        //计算键的hash值
        int hash = (key == null) ? 0 : hash(key);
        //计算下标号
        int i = indexFor(hash, table.length);
        //记录待删除节点的上一个节点
        Entry<K,V> prev = table[i];
        //待删除节点
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            //是否是将要删除的节点
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                //将要删除的节点是否为链表的头部
                if (prev == e)
                    //链表的头部指向下一节点
                    table[i] = next;
                else
                    //上一节点的NEXT为将要删除节点的下一节点
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

jdk8中HashMap源码解析

jdk8中hashmap的结构

jdk8中hashmap

jdk8和jdk7中hashmap的区别

1.最大区别就是底层实现不同

jdk7中是数组+链表实现，jdk8中是数组+链表+红黑树

2.新节点插入到链表的时插入顺序不同

jdk7中插入头结点，jdk8中插入尾节点(因为jdk8中添加新元素时，会遍历整个链表判断是否要树化)

3.HASH算法有所简化

4.扩容机制有所优化

源码解析（主要方法）

属性常量

// 序列号
    private static final long serialVersionUID = 362498820763181265L;    
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树??
    static final int TREEIFY_THRESHOLD = 8; 
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table; 
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;   
    // 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
    int threshold;
    // 填充因子
    final float loadFactor;

类构造函数

public HashMap() {
  // 初始化填充因子  
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0，否则报错
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    // 初始容量不能大于最大值，否则为最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 填充因子不能小于或等于0，不能为非数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    // 初始化填充因子                                        
    this.loadFactor = loadFactor;
    // 初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);    
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

tableSizeFor

//tableSizeFor(initialCapacity)返回大于initialCapacity的最小的二次幂数值。
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;
}
//说明：>>> 操作符表示无符号右移，高位取0

Node类

//Node是单向链表，它实现了Map.Entry接口
static class Node<k,v> implements Map.Entry<k,v> {
    final int hash;
    final K key;
    V value;
    Node<k,v> next;
    //构造函数Hash值 键 值 下一个节点
    Node(int hash, K key, V value, Node<k,v> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + = + value; }
 
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
 
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

put方法

1
2
3

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<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤①：tab为空则创建 
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤②：计算index，并对null做处理  
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 步骤③：节点key存在，直接覆盖value 
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // 步骤④：判断该链为红黑树 
        // hash值不相等，即key不相等；为红黑树结点
        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
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 步骤⑥：超过最大容量 就扩容 
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

// 如果传入key对应的value已经存在，就返回存在的value，不进行替换。如果不存在，就添加key和value，返回null
public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, true);
    }

hash函数

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//首先获取对象的hashCode()值，然后将hashCode值右移16位，然后将右移后的值与原来的hashCode做异或运算，返回结果。（其中h>>>16，在JDK1.8中，优化了高位运算的算法，使用了零扩展，无论正数还是负数，都在高位插入0）。

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table已经初始化，长度大于0，根据hash寻找table中的项也不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 桶中第一项(数组元素)相等
        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<K,V>)first).getTreeNode(hash, key);
            // 否则，在链表中查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

//当Map集合中有这个key时，就使用这个key值，如果没有就使用默认值defaultValue
public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

KeySet系列方法：

//keySet()返回所有键
public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
  
  //Map.foreach本质仍然是entrySet,,配合lambda表达式一起使用，操作起来更加方便。
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

//entrySet()返回所有键值对
public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> 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<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }

???keyset()和entryset效率问题

//举例
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
        while (entryIterator.hasNext()) {
            Map.Entry<String, Integer> next = entryIterator.next();
            System.out.println("key=" + next.getKey() + " value=" + next.getValue());
        }
        
Iterator<String> iterator = map.keySet().iterator();
        while (iterator.hasNext()){
            String key = iterator.next();
            System.out.println("key=" + key + " value=" + map.get(key));
        }

keySet其实是遍历了2次，一次是转为Iterator对象，另一次是从hashMap中取出key所对应的value。

entrySet只是遍历了一次就把key和value都放到了entry中，效率更高。

如果是JDK8，使用Map.foreach方法

keySet:

final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

entrySet:

final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

其实这里已经很明显了，当要得到某个value时，keySet还需要从HashMap中get，entrySet相比keySet少了遍历table的过程，这也是两者性能上的主要差别

/**
 * 键迭代器
 */
final class KeyIterator extends HashIterator 
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] 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<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> 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;
    }
    //省略部分代码
}

？？输入输出顺序问题

HashIterator 在初始化时，会先遍历桶数组，找到包含链表节点引用的桶,随后由 nextNode 方法遍历该桶所指向的链表。遍历完下一个桶后，nextNode 方法继续寻找下一个不为空的桶。之后流程和上面类似，直至遍历完最后一个桶。

HashMapSpliterator系列方法;

static class HashMapSpliterator<K,V> {
       final HashMap<K,V> map;
       Node<K,V> current;          // current node
       int index;                  // current index, modified on advance/split
       int fence;                  // one past last index
       int est;                    // size estimate
       int expectedModCount;       // for comodification checks

       HashMapSpliterator(HashMap<K,V> m, int origin,
                          int fence, int est,
                          int expectedModCount) {
           this.map = m;
           this.index = origin;
           this.fence = fence;
           this.est = est;
           this.expectedModCount = expectedModCount;
       }

       final int getFence() { // initialize fence and size on first use
           int hi;
           if ((hi = fence) < 0) {
               HashMap<K,V> m = map;
               est = m.size;
               expectedModCount = m.modCount;
               Node<K,V>[] tab = m.table;
               hi = fence = (tab == null) ? 0 : tab.length;
           }
           return hi;
       }

       public final long estimateSize() {
           getFence(); // force init
           return (long) est;
       }
   }

static final class KeySpliterator<K,V>
       extends HashMapSpliterator<K,V>
       implements Spliterator<K> {
       KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                      int expectedModCount) {
           super(m, origin, fence, est, expectedModCount);
       }

       public KeySpliterator<K,V> trySplit() {
           int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
           return (lo >= mid || current != null) ? null :
               new KeySpliterator<>(map, lo, index = mid, est >>>= 1,
                                       expectedModCount);
       }

       public void forEachRemaining(Consumer<? super K> action) {
           int i, hi, mc;
           if (action == null)
               throw new NullPointerException();
           HashMap<K,V> m = map;
           Node<K,V>[] tab = m.table;
           if ((hi = fence) < 0) {
               mc = expectedModCount = m.modCount;
               hi = fence = (tab == null) ? 0 : tab.length;
           }
           else
               mc = expectedModCount;
           if (tab != null && tab.length >= hi &&
               (i = index) >= 0 && (i < (index = hi) || current != null)) {
               Node<K,V> p = current;
               current = null;
               do {
                   if (p == null)
                       p = tab[i++];
                   else {
                       action.accept(p.key);
                       p = p.next;
                   }
               } while (p != null || i < hi);
               if (m.modCount != mc)
                   throw new ConcurrentModificationException();
           }
       }

       public boolean tryAdvance(Consumer<? super K> action) {
           int hi;
           if (action == null)
               throw new NullPointerException();
           Node<K,V>[] tab = map.table;
           if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
               while (current != null || index < hi) {
                   if (current == null)
                       current = tab[index++];
                   else {
                       K k = current.key;
                       current = current.next;
                       action.accept(k);
                       if (map.modCount != expectedModCount)
                           throw new ConcurrentModificationException();
                       return true;
                   }
               }
           }
           return false;
       }

       public int characteristics() {
           return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
               Spliterator.DISTINCT;
       }
   }

static final class ValueSpliterator<K,V>
       extends HashMapSpliterator<K,V>
       implements Spliterator<V> {
       ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
                        int expectedModCount) {
           super(m, origin, fence, est, expectedModCount);
       }

       public ValueSpliterator<K,V> trySplit() {
           int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
           return (lo >= mid || current != null) ? null :
               new ValueSpliterator<>(map, lo, index = mid, est >>>= 1,
                                         expectedModCount);
       }

       public void forEachRemaining(Consumer<? super V> action) {
           int i, hi, mc;
           if (action == null)
               throw new NullPointerException();
           HashMap<K,V> m = map;
           Node<K,V>[] tab = m.table;
           if ((hi = fence) < 0) {
               mc = expectedModCount = m.modCount;
               hi = fence = (tab == null) ? 0 : tab.length;
           }
           else
               mc = expectedModCount;
           if (tab != null && tab.length >= hi &&
               (i = index) >= 0 && (i < (index = hi) || current != null)) {
               Node<K,V> p = current;
               current = null;
               do {
                   if (p == null)
                       p = tab[i++];
                   else {
                       action.accept(p.value);
                       p = p.next;
                   }
               } while (p != null || i < hi);
               if (m.modCount != mc)
                   throw new ConcurrentModificationException();
           }
       }

       public boolean tryAdvance(Consumer<? super V> action) {
           int hi;
           if (action == null)
               throw new NullPointerException();
           Node<K,V>[] tab = map.table;
           if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
               while (current != null || index < hi) {
                   if (current == null)
                       current = tab[index++];
                   else {
                       V v = current.value;
                       current = current.next;
                       action.accept(v);
                       if (map.modCount != expectedModCount)
                           throw new ConcurrentModificationException();
                       return true;
                   }
               }
           }
           return false;
       }

       public int characteristics() {
           return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
       }
   }

static final class EntrySpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<Map.Entry<K,V>> {
        EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        public EntrySpliterator<K,V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedModCount);
        }

        public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K,V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        Node<K,V> e = current;
                        current = current.next;
                        action.accept(e);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                Spliterator.DISTINCT;
        }

？？Spliterator:

是一个可分割迭代器(splitable iterator)，可以和iterator顺序遍历迭代器一起看。jdk1.8发布后，对于并行处理的能力大大增强，Spliterator就是为了并行遍历元素而设计的一个迭代器，jdk1.8中的集合框架中的数据结构都默认实现了spliterator

这个就是用来多线程并行迭代的迭代器，这个迭代器的主要作用就是把集合分成了好几段，每个线程执行一段，因此是线程安全的。基于这个原理，以及modCount的快速失败机制，如果迭代过程中集合元素被修改，会抛出异常。

resize方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空
        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值
            threshold = Integer.MAX_VALUE;
            return oldTab;//返回
        }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 双倍扩容阀值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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
    table = newTab;//将新数组的值复制给旧的hash桶数组
    if (oldTab != null) {//进行扩容操作，复制Node对象值到新的hash桶数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j结点处不为空，复制给e
                oldTab[j] = null;//将旧的hash桶数组在j结点处设置为空，方便gc
                if (e.next == null)//如果e后面没有Node结点
                    newTab[e.hash & (newCap - 1)] = e;//直接对e的hash值对新的数组长度求模获得存储位置
                else if (e instanceof TreeNode)//如果e是红黑树的类型，那么添加到红黑树中
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null; // 按命名来翻译的话，应该叫低位首尾节点
                    Node<K,V> hiHead = null, hiTail = null; // 按命名来翻译的话，应该叫高位首尾节点
                    Node<K,V> next;
                    do {
                        next = e.next;//将Node结点的next赋值给next
                        if ((e.hash & oldCap) == 0) {//如果结点e的hash值与原hash桶数组的长度作与运算为0
                            if (loTail == null)//如果loTail为null
                                loHead = e;//将e结点赋值给loHead
                            else
                                loTail.next = e;//否则将e赋值给loTail.next
                            loTail = e;//然后将e复制给loTail
                        }
                        else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0
                            if (hiTail == null)//如果hiTail为null
                                hiHead = e;//将e赋值给hiHead
                            else
                                hiTail.next = e;//如果hiTail不为空，将e复制给hiTail.next
                            hiTail = e;//将e复制个hiTail
                        }
                    } while ((e = next) != null);//直到e为空
                    if (loTail != null) {//如果loTail不为空
                        loTail.next = null;//将loTail.next设置为空
                        newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处
                    }
                    if (hiTail != null) {//如果hiTail不为空
                        hiTail.next = null;//将hiTail.next赋值为空
                        newTab[j + oldCap] = hiHead;//将hiHead赋值给新的hash桶数组[j+旧hash桶数组长度]
                    }
                }
            }
        }
    }
    return newTab;
}

？？jdk8新扩容机制

不会造成倒序，不会产生死循环问题

TreeNode()相关方法

static final int TREEIFY_THRESHOLD = 8;

/**
 * 当桶数组容量小于该值时，优先进行扩容，而不是树化
 */
static final int MIN_TREEIFY_CAPACITY = 64;

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

/**
 *  树化函数
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd 为头节点（head），tl 为尾节点（tail）
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将普通节点替换成树形节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);  // 将普通链表转成由树形节点链表
        if ((tab[index] = hd) != null)
            // 将树形链表转换成红黑树
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

？？什么时候会被树化

链表长度大于等于 TREEIFY_THRESHOLD
桶数组容量大于等于 MIN_TREEIFY_CAPACITY

第一点容易理解，第二点，当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。当桶数组比较小的时候会放生频繁的扩容操作，扩容时需要拆分红黑树并重新映射，所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。

comparableClassFor()系列方法

当put一个新元素时，如果该元素键的hash值小于当前节点的hash值的时候，就会作为当前节点的左节点；hash值大于当前节点hash值得时候作为当前节点的右节点。那么hash值相同的时候呢？这时还是会先尝试看是否能够通过Comparable进行比较一下两个对象（当前节点的键对象和新元素的键对象），要想看看是否能基于Comparable进行比较的话，首先要看该元素键是否实现了Comparable接口，此时就需要用到comparableClassFor方法来获取该元素键的Class，然后再通过compareComparables方法来比较两个对象的大小。


/**
* 如果对象x的类是C，如果C实现了Comparable<C>接口，那么返回C，否则返回null
*/
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // 如果x是个字符串对象
            return c; // 返回String.class
        /*
         * 为什么如果x是个字符串就直接返回c了呢 ? 因为String  实现了 Comparable 接口，可参考如下String类的定义
         * public final class String implements java.io.Serializable, Comparable<String>, CharSequence
         */ 
 
        // 如果 c 不是字符串类，获取c直接实现的接口（如果是泛型接口则附带泛型信息）    
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) { // 遍历接口数组
                // 如果当前接口t是个泛型接口 
                // 如果该泛型接口t的原始类型p 是 Comparable 接口
                // 如果该Comparable接口p只定义了一个泛型参数
                // 如果这一个泛型参数的类型就是c，那么返回c
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                        Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
            // 上面for循环的目的就是为了看看x的class是否 implements  Comparable<x的class>
        }
    }
    return null; // 如果c并没有实现 Comparable<c> 那么返回空
}


/**
* 如果x所属的类是kc，返回k.compareTo(x)的比较结果
* 如果x为空，或者其所属的类不是kc，返回0
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

/**
* 如果两者不具有compare的资格，或者compare之后仍然没有比较出大小。那么就要通过一个决胜局再比一次，这个决胜局就是* * tieBreakOrder方法。
* 用这个方法来比较两个对象，返回值要么大于0，要么小于0，不会为0
* 也就是说这一步一定能确定要插入的节点要么是树的左节点，要么是右节点，不然就无法继续满足二叉树结构了
* 
* 先比较两个对象的类名，类名是字符串对象，就按字符串的比较规则
* 如果两个对象是同一个类型，那么调用本地方法为两个对象生成hashCode值，再进行比较，hashCode相等的话返回-1
*/
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
            compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                -1 : 1);
    return d;
}

compute系列方法

computeIfAbsent

@Override
    public V computeIfAbsent(K key,
                             Function<? super K, ? extends V> mappingFunction) {
        if (mappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key); //计算hash
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        // 如果为初始化则先进行初始化，
        // resize（）方法在table为空时执行初始化逻辑
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 下面的逻辑就是通过key找到节点node
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
            V oldValue;
            // 如果key存在且其value！=null，则返回该value
            if (old != null && (oldValue = old.value) != null) {
                afterNodeAccess(old);
                return oldValue;
            }
        }
        // 下面的逻辑是：如果没找到则新建节点，
        // 节点value为Function返回值；如果找到但value为null，
        // 则将Function返回值作为其value
        V v = mappingFunction.apply(key);
        if (v == null) {
            return null;
        } else if (old != null) {
            old.value = v;
            afterNodeAccess(old);
            return v;
        }
        else if (t != null)
            t.putTreeVal(this, tab, hash, key, v);
        else {
            tab[i] = newNode(hash, key, v, first);
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        ++modCount;
        ++size;
        afterNodeInsertion(true);
        return v;
    }

总结：

存在且value不为null，则返回value
不满足上述条件下，先检查Function返回值，若为null，返回null
存在但value为null，则将Function返回值作为value，返回value
不存在，新建节点，将Function返回值作为value，返回value
使用场景：从map中获取所需要的value，若其为null，就用准备好的值即Function的返回值，就像上面那题的用法那样

computeIfPresent

public V computeIfPresent(K key,
                              BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null)
            throw new NullPointerException();
        Node<K,V> e; V oldValue;
        int hash = hash(key);
        if ((e = getNode(hash, key)) != null &&
            (oldValue = e.value) != null) {
            V v = remappingFunction.apply(key, oldValue);
            if (v != null) {
                e.value = v;
                afterNodeAccess(e);
                return v;
            }
            else
                removeNode(hash, key, null, false, true);
        }
        return null;
    }

总结：

存在且value不为null：1，BiFunction返回值为null，删除该节点；2，BiFunction返回值不为null，作为新value，返回其值
不存在或其value为null，返回null
使用场景：更新map中存在的且其value值不为null的键值对的值

compute

根据key做匹配，根据BiFunction的apply返回做存储的value。匹配到Node做value替换，匹配不到新增node。apply的返回值如果为null则删除该节点，否则即为要存储的value。

@Override
    public V compute(K key,
                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        Node<K,V>[] tab; Node<K,V> first; int n, i;
        int binCount = 0;
        TreeNode<K,V> t = null;
        Node<K,V> old = null;
        if (size > threshold || (tab = table) == null ||
            (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((first = tab[i = (n - 1) & hash]) != null) {
            if (first instanceof TreeNode)
                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
            else {
                Node<K,V> e = first; K k;
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        old = e;
                        break;
                    }
                    ++binCount;
                } while ((e = e.next) != null);
            }
        }
        V oldValue = (old == null) ? null : old.value;
        V v = remappingFunction.apply(key, oldValue);
        if (old != null) {
            if (v != null) {
                old.value = v;
                afterNodeAccess(old);
            }
            else
                removeNode(hash, key, null, false, true);
        }
        else if (v != null) {
            if (t != null)
                t.putTreeVal(this, tab, hash, key, v);
            else {
                tab[i] = newNode(hash, key, v, first);
                if (binCount >= TREEIFY_THRESHOLD - 1)
                    treeifyBin(tab, hash);
            }
            ++modCount;
            ++size;
            afterNodeInsertion(true);
        }
        return v;
    }

???三者比较

computeIfAbsent：如果key已存在，返回oldVlaue；不存在创建，返回新创建value
computeIfPresent：如果key不存在，返回null；如果已存在，value为null则删除此节点，不为null替换节点value并返回此value。
compute：如果key不存在，新建key进行存储；如果key存在，value为null则删除此节点，不为null替换节点value并返回此value。

merge

功能大部分与compute相同，不同之处在于BiFunction中apply的参数，入参为oldValue、value，调用merge时根据两个value进行逻辑处理并返回value。

public V merge(K key, V value,
                BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
     if (value == null)
         throw new NullPointerException();
     if (remappingFunction == null)
         throw new NullPointerException();
     int hash = hash(key);
     Node<K,V>[] tab; Node<K,V> first; int n, i;
     int binCount = 0;
     TreeNode<K,V> t = null;
     Node<K,V> old = null;
     if (size > threshold || (tab = table) == null ||
         (n = tab.length) == 0)
         n = (tab = resize()).length;
     if ((first = tab[i = (n - 1) & hash]) != null) {
         if (first instanceof TreeNode)
             old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
         else {
             Node<K,V> e = first; K k;
             do {
                 if (e.hash == hash &&
                     ((k = e.key) == key || (key != null && key.equals(k)))) {
                     old = e;
                     break;
                 }
                 ++binCount;
             } while ((e = e.next) != null);
         }
     }
     if (old != null) {
         V v;
         if (old.value != null)
         	//根据oldValue和value参数计算value值
             v = remappingFunction.apply(old.value, value);
         else
         	//oldValue为null，直接取value参数
             v = value;
         if (v != null) {
             old.value = v;
             afterNodeAccess(old);
         }
         else
         	//计算出来的value值为null，删除节点
             removeNode(hash, key, null, false, true);
         return v;
     }
     if (value != null) {
         if (t != null)
             t.putTreeVal(this, tab, hash, key, value);
         else {
             tab[i] = newNode(hash, key, value, first);
             if (binCount >= TREEIFY_THRESHOLD - 1)
                 treeifyBin(tab, hash);
         }
         ++modCount;
         ++size;
         afterNodeInsertion(true);
     }
     return value;
 }

forEach

调用此方法时实现BiConsumer接口重写void accept(Object o, Object o2)方法，其中o为key，o2为value，可根据自己的实现对map中所有数据进行处理。

@Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key, e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

ConcurrentModificationException异常

错误实例

public static void main(String[] args) {
       HashMap<String, String> hashMap = new HashMap<>();
       hashMap.put("1", "Hello");
       hashMap.put("2", "World");
       Iterator<String> it = hashMap.keySet().iterator();
       while (it.hasNext()) {
           String key = it.next();
           if (key.equals("1")) {
               it.remove();
           }
       }
   }

报错

//报错
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1437)
	at java.util.HashMap$KeyIterator.next(HashMap.java:1461)
	at com.yufh.Exception.main(Exception.java:21)

HashMap.java:1437:

1
2
3

if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
//如果HashMap中modCount和expectedModCount不相等，则会抛出异常

错误解析(并发异常)

modCount：

具体用途是记录该HashMap修改次数，比如在对一个HashMap put操作时，会对modCount进行++modCount操作

而在remove操作的时候，也会对modCount进行同样的操作：

expectedModCount：

它是HashIterator中的一个变量，在对HashMap迭代的时候，将modCount赋给expectedModCount

HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] 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);
            }
        }

什么时候调用

//HashMap entrySet()：
public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

//此处新建一个EntrySet对象，而在对EntrySet进行迭代的时候，会调用：
public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }

//新建一个EntryIterator对象，查看该类描述：
final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

总结：HashMap迭代遍历的时候，会初始化expectedModCount=modCount，这时候对HashMap进行修改操作，modCount会+1，继续遍历的时候expectedModCount!=modCount，继而抛出java.util.ConcurrentModificationException异常。

产生错误原因

Fail-Fast 机制
我们知道 java.util.HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经可能有其他线程修改了 Map：注意到 modCount 声明为 volatile，保证线程之间修改的可见性。

解决办法

在单线程环境下的解决方法

Itr类中也给出了一个remove()方法：keyset()->new set()->KeyIterator();->nextNode()

public final void remove() {
            Node<K,V> 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;  //这里重新把modCount赋值给expectedModCount
        }

多线程环境下的解决方法
- 多线程环境使用it.remove();可以嘛？
  
  iterator()方法每次都new一个Itr()，Itr是一个私有内部类，
  
  虽然一开始值相同，但是modCount是同一个，所以当有一个线程改变了modCount时，另一个线程在调用checkForComodification()时，就会发生异常。
1. 在使用iterator迭代的时候使用synchronized或者Lock进行同步；
2. 使用线程安全的ConcurrentHashMap
  - 为什么不使用hashtable
    
    效率太低： HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。
  - ConcurrentHashMap 原理：底层采用分段的数组+链表实现，线程安全，通过把整个Map分为N个Segment（Segment 是一种可重入锁继承ReentrantLock），使用了锁分离技术，可以提供相同的线程安全，但是效率提升N倍（默认分为16段，最理想情况并发量为16的话效率提升16倍）。

Next Post

负载均衡常用算法
Previous Post

Synchronized

CATALOG

1. HashMap原理浅析

