HashMap看这一篇就够了

• 一、HashMap 数据结构
• 二、数据插入原理
• 三、HashMap的容量
• 四、HashMap的hash()算法
• 五、JDK1.8 主要的优化
• 六、HashMap是线程安全的吗？

一、HashMap 数据结构

HashMap是Java中最常用的集合类框架，也是Java语言中非常典型的数据结构

二、数据插入原理

1. 判断数组是否为空，为空进行初始化;
2. 不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
3. 查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
4. 存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
5. 如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)
6. 如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8并且数组长度大于64， 大于的话链表转换为红黑树；
7. 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

三、HashMap的容量

HashMap不传值，默认大小是16，负载因子是0.75，如果传入初始大小m，初始化大小为大于m的 2的整数次方，例如如果传10，大小为16；如果传20，则大小为32。

/**
         * The default initial capacity - MUST be a power of two.
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

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

HashMap的容量为什么是2的n次方？
HashMap容量取2的n次方，与hash寻址有关，HashMap是通过%运算来获得key的散列地址的，但是，%运算的速度并没有&的操作速度快。而&操作能代替%运算所必须的条件就是为2的n次方（公式：a%b=a&(b-1)，当b为2的n次方时）

四、HashMap的hash()算法

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

int hashCode = key.hashCode() ^ (key.hashCode() >>> 16);
其逻辑就是先获得key的hashCode的值 h，然后 h 和 h右移16位 做异或运算。实质上就是把一个数的低16位与他的高16位做异或运算。
如果不这样的话，那么就只有hash()返回值的末x位参与到运算，这样就会造成hash冲突的概率高一些。如果先把key的hashCode()返回值的高16位和低16位进行异或运算，这样高16位也参与到hash()的运算逻辑了，这样就能减少冲突。

五、JDK1.8 主要的优化

1. 数组+链表改成了数组+链表或红黑树
2. 链表的插入方式从头插法改成了尾插法
3. 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小
4. 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；

六、HashMap是线程安全的吗？

不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题。

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。
1、HashTable：直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大
2、Collections.synchronizedMap：使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现
3、ConcurrentHashMap：使用分段锁，降低了锁粒度，让并发度大大提高；成员变量使用volatile修饰，免除了指令重排序并且保证内存可见性，同时使用CAS操作和synchronized结合实现赋值操作。