HashMap底层原理分析

开篇先整几个问题：
1、JDK8中的HashMap有哪些改动？
2、JDK8为什么要使用红黑树？
3、HashMap扩容机制是怎么样的，JDK7和JDK8有什么区别？
4、为什么重写对象的Equals时，要重写HashCode方法，跟HashMap有什么关系吗？为什么？
5、HashMap是线程安全的吗？遇到过ConcurrentModificationException吗？为什么会出现？如何解决？
6、在使用HashMap的过程中我们应该注意些什么？

HashMap简单实现：

package test;

import org.junit.Test;

/**
 * HashMap数组+链表简单实现
 */
public class MyHashMap<K, V> {

    private Entry<K, V>[] table; //数组
    private int size = 0; //map大小
    private static int CAPACITY = 8; //数组容量

    public V put(K k, V v){
        if(table == null){
            table = new Entry[CAPACITY]; //初始化数组大小
        }
        int hash = k.hashCode();
        int index = Math.abs(hash % CAPACITY); //取余获取数组下标

        if(table[index] != null){
            for(Entry<K, V> e = table[index]; e != null; e = e.next){
                if(e.getK().equals(k)){
                    V oldV = e.getV();
                    e.setV(v);
                    return oldV; //返回旧值
                }
            }
        }

        Entry<K, V> entry = new Entry<>(k, v, table[index]);
        table[index] = entry;
        size ++;
        return null; //如果不是替换，就没有旧值返回
    }

    public V get(K k){
        int hash = k.hashCode();
        int index = hash/CAPACITY; //取余获取数组下标
        if(table[index] == null){
            return null;
        }
        for(Entry<K, V> e = table[index]; e != null; e = e.next){
            if(e.getK().equals(k)){
                return e.getV();
            }
        }
        return null;
    }

    public int size(){
        return size;
    }

    class Entry<K, V>{
        private K k;
        private V v;
        private Entry<K, V> next;

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

        public K getK() {
            return k;
        }

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

        public V getV() {
            return v;
        }

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

        public Entry<K, V> getNext() {
            return next;
        }

        public void setNext(Entry<K, V> next) {
            this.next = next;
        }
    }

    @Test
    public void testMap(){
        MyHashMap<String, Object> myMap = new MyHashMap<>();
        for(int i=0;i<10;i++){
            myMap.put("index" + i, "value" + i);
        }
        System.out.println(myMap.size());
    }
}

HashMap原理：
jdk7：通过hash算法以及一系列的位运算，得到数组下标；如果数组下标没有值，直接放入，如果有值，放入链表头部插入；可以参考上述代码。
1）数组默认大小 16，加载因子：0.75，也就是说阈值是12；
2）扩容条件：当数组使用的大小 >= 数组初始大小*0.75 且 当前数组节点不为空
3）之前的2倍扩容
4）将oldTable中的数据复制到newTable中
5）数组大小需要是2的倍数，比如数组大小为16，计算数组下标的大致方式为：hashcode & (16-1)，因为2的倍数-1的数据进行与运算的特性，保证不会有数组下标越界。
6）JDK7扩容的时候可能会发生死锁的情况

jdk8与jdk7的区别：
1）当链表长度大于8的时候，会转换成红黑树，红黑树的查询效率优于链表
2）当链表长度小于等于6的时候，红黑树会转换成链表
3）数据是从尾结点加入
4）Hash算法有所优化；jdk8hash算法提升了一些性能，因为有了红黑树，散列程度不需要像7那样。
5）扩容有所优化。jdk7会重新组装链表，最终结果会和老数组中的链表顺序相反；链表直接搬到新数组中，也不会产生死锁了
6）1.7扩容的时候，除了超过阈值之外，还会判断taible[i]是否为空，不为空的话才会进行扩容，而1.8不会

ps.16扩容到32长度的新数组时候，如果hashcode 的二进制第5位位数是0，那么在新数组中位置不变；如果第5位是1，则在新数组中下标 +16。