先介绍HashMap

要了解hashmap首先需要了解哈希表。

关于哈希表，可以简单理解成是一个主干数组，每传入一个参数的时候，可以通过一个Key去获得想要的位置，从而获取对应的数组值。而通过key去获取数组的位置，就成了哈希表的关键。
一般我们都会通过hashCode方法将一个key转化成哈希值，再通过哈希值去获取数组下标。
我用一张图解释一下

1024555-20161113180447499-1953916974.png

介绍完哈希表，那么我们继续介绍一下hashmap的一些关键参数

    /**
     * 阈值，代表当前哈希表的主干数组最大有多少个，默认是16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The load factor used when none specified in constructor.
     * 负载因子，代表当前最多可以存储多少个value值
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

     /**
     * 哈希表的主干数组
     */
    transient Entry<K,V>[] table;

再介绍一下HashMap的一个重要内部类

static class Entry<K,V> implements Map.Entry<K,V> { final K key;
        V value;
        Entry<K,V> next;  //存储指向下一个Entry的引用，单链表结构 int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算 

       /** * Creates new entry. */ 
       Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        } 

}

可以看出，其实这是一个
除了自身带有key 和value的对象外，还有下一个节点值。是不是很像链表的一个节点？

接着直接看put方法

    public V put(K key, V value) {
        //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
       //如果key为null，存储位置为table[0]或table[0]的冲突链上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
        int i = indexFor(hash, table.length);//获取在table中的实际位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
        addEntry(hash, key, value, i);//新增一个entry
        return null;
    }    

简单总结一下就是
1.如果table为空，那么初始化table
2.将当前的key转化为hash值
3.通过哈希值获取在数组中的index
4.如果当前Key已存在，就进行覆盖。

再看一下get

public V get(Object key) {
　　　　 //如果key为null,则直接去table[0]处去检索即可。
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
 }

final Entry<K,V> getEntry(Object key) {
            
        if (size == 0) {
            return null;
        }
        //通过key的hashcode值计算hash值
        int hash = (key == null) ? 0 : hash(key);
        //indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
        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;
    }

1.通过key获取哈希值
2.通过哈希值获取当前数组下表index
3.获取数组下表以后就等于获取了当前链表的第一个节点
4.依次遍历链表找出最终对应Key的节点

哈希冲突

刚才我们看到，获取数组table的节点以后，会再获取当前节点的下一个节点，这是为什么呢？
因为这里就涉及到了一个节点冲突的问题。简单点将就是，不同的Key通过哈希转化以后，可能得到同一个index。如果出现了这种现象，当前的hash值通过拉链法去解决。
何为拉链法呢，就是其实table的每一个值都是一个节点，对应一条链表。当我们发现当前的Key所对应数组下标的value中，已经有值，我们就把新的节点挂在当前节点的后方，形成链表。
所以我们上面的get方法就可以看出，获取到tab的一个值之后，还需要循环当前链表。
用一张图来简单描述一下hashMap的数据结构

1024555-20161113235348670-746615111.png

从这里开始我们可以发现，hashMap的操作请求都没有做同步处理，所以HashMap也就不是线程安全。基于这种情况，jdk又推出了ConcurrentHashMap。也就是在HashMap的基础上增加了线程安全的逻辑。

ConcurrentHashMap

相比HashMap，ConcurrentHashMap是由Segment 的数组组成，这个数组的个数一共是16个，每一个Segment则是继承了RenteenLock。这样等于每一个Segment都是一个分段锁，可以实现同时16个线程的操作。而Segment里面的每一个值，就可以理解成是一个HashMap，只是增加了线程同步的HashMap。
先用一张图介绍一下：

3.png

然后我们再来看一下Segment的源码

接着就来分析一下put的操作

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    // 1. 计算 key 的 hash 值
    int hash = hash(key);
    // 2. 根据 hash 值找到 Segment 数组中的位置 j
    //    hash 是 32 位，无符号右移 segmentShift(28) 位，剩下低 4 位，
    //    然后和 segmentMask(15) 做一次与操作，也就是说 j 是 hash 值的最后 4 位，也就是槽的数组下标
    int j = (hash >>> segmentShift) & segmentMask;
    // 刚刚说了，初始化的时候初始化了 segment[0]，但是其他位置还是 null，
    // ensureSegment(j) 对 segment[j] 进行初始化
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        s = ensureSegment(j);
    // 3. 插入新值到 槽 s 中
    return s.put(key, hash, value, false);
}

1.首先根据Key获取哈希值
2.获取哈希值之后通过特定的算法获取Segments数组对应的下标
3.通过下标获取当前key的节点所在的Segment
4.获取到Segment之后，其实就是Segment内部的操作了

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 在往该 segment 写入前，需要先获取该 segment 的独占锁
    //    先看主流程，后面还会具体介绍这部分内容
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        // 这个是 segment 内部的数组
        HashEntry<K,V>[] tab = table;
        // 再利用 hash 值，求应该放置的数组下标
        int index = (tab.length - 1) & hash;
        // first 是数组该位置处的链表的表头
        HashEntry<K,V> first = entryAt(tab, index);
 
        // 下面这串 for 循环虽然很长，不过也很好理解，想想该位置没有任何元素和已经存在一个链表这两种情况
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        // 覆盖旧值
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                // 继续顺着链表走
                e = e.next;
            }
            else {
                // node 到底是不是 null，这个要看获取锁的过程，不过和这里都没有关系。
                // 如果不为 null，那就直接将它设置为链表表头；如果是null，初始化并设置为链表表头。
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
 
                int c = count + 1;
                // 如果超过了该 segment 的阈值，这个 segment 需要扩容
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node); // 扩容后面也会具体分析
                else
                    // 没有达到阈值，将 node 放到数组 tab 的 index 位置，
                    // 其实就是将新的节点设置成原链表的表头
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        // 解锁
        unlock();
    }
    return oldValue;
}

1.获取同步锁加锁
2.逻辑基本和HashMap的一致就不再详细说明了，上面注释已经很详细了
3.要注意在finally中会释放锁。

java 1.7和1.8的区别

由于会出现链表冲突导致一个数组的链表特别长的情况，1.8将通过链表去解决节点冲突的方式改成了红黑树。