HashMap以及ConcurrentHashMap（volatile）

1.HashMap怎么实现hashcode和equals

HashMap的数据结构是链表+数组，HashMap的数据结构类似于：

元素0->[hashCode=0,key.value=x1的数据]
元素1->[hashCode=1,key.value=y1的数据]
...
元素n->[hashCode=n,key.value=n1的数据]复制代码

hashMap的put和get方法都会调用hashCode方法，如果两个hashCode有冲突，再调用equals方法:

put() ：会调用对象的hashCode()方法来计算hashcode，然后找到buchet（桶）位置来储存对象，当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。hashMap通过链表来解决冲突问题，如果发生碰撞，对象就会储存在链表的下一节点。

get() ：buchet（桶）里的第一个节点，直接命中；如果有冲突，则通过key.equals(k)去找对应的可以。

为什么要重写hashCode()和equals()：

首先先来看一下equals:

public boolean equals(Object obj){
    return (this==obj);
}复制代码

是通过==来比较两个对象的引用地址，Object的equals只是简单的判断是不是同一个实例，但如果我们需要比较逻辑上的相等，就需要重写equals()方法，而涉及到HashMap的时候，重写了equals()就需要重写hashCode()方法。

2.concurrentHashMap怎么实现

采用了“分段锁”的方式来确保线性安全，相比于HashTable，不会存在锁竞争，可以有效的提高并发效率。

concurrentHashMap的主干是Segment数组

final Segment<K,V>[] segment;复制代码

Segment继承了ReentrantLock，所以它就是一种“可重入锁”。在concurrentHashMap中一个Segment就相当于一个子哈希表，Segment里维护了一个HashEntry数组，在并发情况下，不需要考虑锁的竞争。

#Segment:
transient volatile HashEntry<K,V>[] table;复制代码

一个ConcurrentHashMap维护一个Segment，一个Segment维护一个HashEntry，对于同一个Segment才考虑线程同步，不同Segment不需要考虑。

jdk7 中：

put() ：1.定位segment并确保定位的Segment已初始化 2.调用Segment的put方法

get() ：get无需加锁，由于其涉及的共享变量都使用volatile修饰，volatile可以保证内存可见性，所以不会读取过期数据。

jdk8 中：

put() ：沿用了hashMap中的put，根据hash值计算这个新插入的点在table中的位置i，如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾，但是不允许key或value为null。

调用的是putVal方法

public V put(K key, V value) {    return putVal(key, value, false);}复制代码

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());// 计算key的hash值
    int binCount = 0;// 表示table中索引下标代表的链表或红黑树中的节点数量
    // 采用自旋方式，等待table第一次put初始化完成，或等待锁或等待扩容成功然后再插入
    for (Node<K,V>[] tab = table;;) {
        // f节点标识table中的索引节点，可能是链表的head，也可能是红黑树的head
        // n:table的长度，i:插入元素在table的索引下标，fh : head节点的hash值
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)// 第一次插入元素，先执行初始化
            tab = initTable();
        // 定位到的索引下标节点(head)为null，表示第一次在此索引插入，
        // 不加锁直接插入在head之后，在casTabAt中采用Unsafe的CAS操作，保证线程安全
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // head节点为ForwadingNode类型节点，表示table正在扩容，链表或红黑树也加入到帮助扩容操作中
        else if ((fh = f.hash) == MOVED) 
            tab = helpTransfer(tab, f);
        else {// 索引下标存在元素，且为普通Node节点，给head加锁后执行插入或更新
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {// 为普通链表节点，还记得之前定义的几种常量Hash值吗？
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            // 插入新元素，每次插在单向链表的末尾，这点与 Java 7中不同（插在首部）
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {// head为树节点，按树的方式插入节点
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 链表节点树超过阈值8，将链表转换为红黑树结构
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 如果是插入新元素，则将链表或红黑树最新的节点数量加入到CounterCells中
    addCount(1L, binCount);
    return null;
}复制代码

get()：

1、计算key的hash值，并定位table索引

2、若table索引下元素(head节点)为普通链表，则按链表的形式迭代遍历。

3、若table索引下元素为红黑树TreeBin节点，则按红黑树的方式查找(find方法)。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {// 普通链表
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // hash值小于-1,即为红黑树，还记得之前定义的TreeBin节点的hash值吗
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {// 匹配下一个链表元素
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}复制代码

3.volatile

volatile实现的是可见性，即一个线程的修改对另一个线程是可见的。也就是一个线程修改结果，另一个线程马上能看到。

当把变量声明为volatile类型后，编译器与运行时都会注意到这个变量是共享的，因此不会将该变量上的操作与其他内存操作一起重排序， 在访问volatile变量时不会执行加锁操作，因此也就不会使执行线程阻塞，因此volatile变量是一种比sychronized关键字更轻量级的同步机制。