本文转载自微信公众号《Java时光屋》，作者JackJia。转载本文请联系爪哇时光之家公众号。1.HashMap的数据结构：2.HashMap的哈希函数设计：3.Java1.8和Java1.7的比较：3.1干扰次数减少：3.2结构变化：3.3插入变化：3.4扩容变化：3.5扩容时间变化：4.HashTable与Collections.synchronizedMap，ConcurrentHashMap可以实现线程安全Map原理：5.Map集合顺序：前言HashMap是java面试中问的最多的一个问题，涉及的知识点很多，其中很适合调查面试这个问题真的是我反正面试很多公司的必考题，没有准备真的很难回答。1、HashMap的数据结构：JDK1.8：数组+链表/红黑树数据结构原理：链表长度>8&数组大小>=64=》转换为红黑树存储；红黑树节点数<6转为链表。tips：为什么不小于8是为了防止频繁的结构转换增加开销。那为什么是8呢？8次哈希冲突的概率是百万分之六，足够了。HashMap中数据插入的原理：要点：上面计算数组位置的方法是：通过(n-1)&hash计算数组中应该存放的下标索引；为什么叫位运算(n-1)更接近取模，为什么用位运算是因为效率高，没有二进制和十进制的转换。这里补充一下HashMap初始化数组大小的问题。HashMap数组的初始化大小是16，为什么？理论上2的整数次方就可以了，但是如果是2、4、8就有点小了，加不了多少数据。它会膨胀并影响性能。如果是32或更大，就会浪费空间。所以16是保留的经验值。2、HashMap的哈希函数设计：在HashMap中，首先使用key的hashcode（32位int值），然后对hashcode的高16位和低16位进行异或运算。为什么要这样设计：1、上面的哈希函数也叫扰动函数。主要考虑是尽量减少哈希冲突，越分散越好。2、算法要尽可能的高效，因为这是一个高频运算，所以使用了位运算。3、因为hashcode的范围是int类型，大约40亿映射空间，如果只是hashcode，碰撞很少，但是数组和内存不能分布，数组初始大小只有16个而已。模运算/位运算来达到目的。HashMap的数组长度应该是2的整数次方，这样数组长度-1正好是“低位掩码”，加上散列函数（扰动函数）来减少碰撞。3、Java1.7与Java1.8的比较：3.1干扰次数减少：这里java1.8与java1.7的区别在于java8在hash函数中只干扰一次，为了效率。java7在这里被扰动了四次。3.2结构变化：1.7中数组+链表===”数组+链表或者红黑树。为什么要这样，前者的查询效率是n，后者的查询效率是log2(n)，所以当链表数据量大时，会出现效率问题。3.3插入变化：链表的插入方式由头插入法改为尾插入法，简单来说，在1.7中，插入forward,1.8是backward插入，这样做的目的是防止扩容时死循环3.4扩容变化：1.7是扩容时重新hash新数组的位置，而1.8采用更简单的逻辑判断，位置不变还是索引+旧容量大小。为什么1.8可以这样？计算数组位置的掩码只是在高位多了一个1。3.5扩容的时间变化：插入时,1.7首先判断是否需要扩容插入前ired，1.8判断插入后是否需要扩容4.HashTable和Collections.synchronizedMap，ConcurrentHashMap可以实现线程安全的Map原理：我们都知道HashMap不是线程安全的。1.7版本会出现死循环、数据丢失、数据覆盖等问题。1.8解决的问题其中两个问题还是数据覆盖的问题，即多线程并发下的值覆盖。如果业务场景需要线程安全，就必须使用线程安全的Map类。一般我们使用ConcurrentHashMap。ConcurrentHashMap：使用的分段锁，降低了锁的粒度，提高了并发和效率。与1.7相比，1.8也提高了效率。成员变量之间使用volatile修饰，避免指令重排，保持内存可见。用于实现赋值操作的CAS和synchronized结合，只会锁住当前操作的索引节点。HashTable：直接在操作方法上使用synchronized关键字锁住整个数组，效率会很低。SynchronizedMap：内部实现对象锁实现。效率高于HashTable。5.Map集合的顺序：HashMap是无序的，所以只能循环遍历。LinkedHashMap：有序映射，内部维护一个单向链表。单向链表的before和after使其具有有序的特性。TreeMap：排序是通过Comprator比较器在内部实现的。总结一下我上面的讨论也是参考了网上我觉得不错的HashMap的解释，然后加上自己的理解，让大家更好的理解原理和内容。如果还有其他问题，欢迎关注我的公众号：Java时光屋进行讨论。
