HashMap结构和原理

1.HashMap的底层结构？

HashMap是我们⾮常常⽤的数据结构，由数组和链表组合构成的数据结构。 ⼤概如下，数组⾥⾯每个地⽅都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node。 因为他本身所有的位置都为null，在put插⼊的时候会根据key的hash去计算⼀个index值。 就⽐如我put（”帅丙“，520），我插⼊了为”帅丙“的元素，这个时候我们会通过哈希函数计算出插⼊的位置，计算出来index是2那结果如下。 hash（“帅丙”）= 2

2.为啥需要链表，链表⼜是怎么样⼦的呢？

    我们都知道数组⻓度是有限的，在有限的⻓度⾥⾯我们使⽤哈希，哈希本身就存在概率性，就是”帅丙“和”丙帅“我们都去hash有⼀定的概率会⼀样，就像上⾯的情况我再次哈希”丙帅“极端情况也会hash到⼀个值上，那就形成了链表。 每⼀个节点都会保存⾃身的hash、key、value、以及下个节点，我看看Node的源码。

3.新的Entry节点在插⼊链表的时候，是怎么插⼊的么？

    java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上⾯的例⼦⼀样，因为写这个代码的作者认为后来的值被查找的可能性更⼤⼀点，提升查找的效率。     在java8之后，都是所⽤尾部插⼊了。

4.头插法为啥要改尾插？

首先，了解一下HashMap扩容机制：

数组容量是有限的，数据多次插⼊的，到达⼀定的数量就会进⾏扩容，也就是resize。

4.1 什么时候resize呢？ 有两个因素： Capacity： HashMap当前⻓度。 LoadFactor： 负载因⼦，默认值0.75f     怎么理解呢，就⽐如当前的容量⼤⼩为100，当你存进第76个的时候，判断发现需要进⾏resize了，那就进⾏扩容，但是HashMap的扩容也不是简单的扩⼤点容量这么简单的 4.2 扩容？它是怎么扩容的呢？ 分为两步 扩容：创建⼀个新的Entry空数组，⻓度是原数组的2倍。 ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。 4.3为什么要重新Hash呢，直接复制过去不行么？ 是因为⻓度扩⼤以后，Hash的规则也随之改变。 Hash的公式—> index = HashCode（Key） & （Length - 1） 原来⻓度（Length）是8你位运算出来的值是2 ，新的⻓度是16你位运算出来的值明显不⼀样了。 扩容前： 扩容后：         我先举个例⼦吧，我们现在往⼀个容量⼤⼩为2的put两个值，负载因⼦是0.75是不是我们在put第⼆个的时候就会进⾏resize？ 2*0.75 = 1 所以插⼊第⼆个就要resize了 现在我们要在容量为2的容器⾥⾯⽤不同线程插⼊A，B，C，假如我们在resize之前打个短点，那意味着数据都插⼊了但是还没resize那扩容前可能是这样的。 我们可以看到链表的指向A->B->C Tip：A的下⼀个指针是指向B的 因为resize的赋值⽅式，也就是使⽤了单链表的头插⼊⽅式，同⼀位置上新元素总会被放在链表的头部位置，在旧数组中同⼀条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。 就可能出现下⾯的情况，⼤家发现问题没有？ B的下⼀个指针指向了A ⼀旦⼏个线程都调整完成，就可能出现环形链表 如果这个时候去取值，悲剧就出现了——Infinite Loop。 尾插法     因为java8之后链表有红⿊树的部分，⼤家可以看到代码已经多了很多if else的逻辑判断了，红⿊树的引⼊巧妙的将原本O(n)的时间复杂度降低到O(logn) 使⽤头插会改变链表的上的顺序，但是如果使⽤尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了 总结：

     Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引⽤关系。      Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引⽤关系。

5.java8就可以把HashMap⽤在多线程中呢？

    我认为即使不会出现死循环，但是通过源码看到put/get⽅法都没有加同步锁，多线程情况最容易出现的就是：⽆法保证上⼀秒put的值，下⼀秒get的时候还是原值，所以线程安全还是⽆法保证。

6.HashMap的默认初始化⻓度是多少？

初始化⼤⼩是16 6.1为啥是16？     位与运算⽐算数计算的效率⾼了很多，之所以选择16，是为了服务将Key映射到index的算法。 6.2为啥我们重写equals⽅法的时候需要重写hashCode⽅法呢？ 因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个⽅法equals、hashCode，这两个⽅法都是⽤来⽐较两个对象是否相等的。 在未重写equals⽅法我们是继承了object的equals⽅法，那⾥的 equals是⽐较两个对象的内存地址，显然我们new了2个对象内存地址肯定不⼀样

对于值对象，==⽐较的是两个对象的值 对于引⽤对象，⽐较的是两个对象的地址

⼤家是否还记得我说的HashMap是通过key的hashCode去寻找index的，那index⼀样就形成链表了，也就是说”帅丙“和”丙帅“的index都可能是2，在⼀个链表上的。 我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”帅丙“还 是”丙帅“呢？ equals！是的，所以如果我们对equals⽅法进⾏了重写，建议⼀定要对hashCode⽅法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

7.HashMap常⻅⾯试题：

1.HashMap的底层数据结构？

1.7的时候底层entry数组加链表，1.8的时候改成Node节点、链表和红黑树， 链表长度超过8，自动转成红黑树，当红黑树的节点的个数小于等于6时， 会将红黑树结构转为链表结构 红黑树主要为了解决查询效率问题，但是需要设计左右节点的移动， 增删会比较慢，不采用二叉树的原因，是因为树高，树越高查询效率越慢

2.HashMap的存取原理？

存的时候： 根据key采用hash算法计算得到数组的索引位置上，1.7采用头插法并发可能会导致扩容时，改变链表的顺序，造成死循环，1.8采用尾插法，会保证链表的顺序。 取的的时候： 根据key得到数组的索引，然后用equals去比较

3.Java7和Java8的区别？

差别：底层结构不一样 1.7头插，1.8尾插

4.为啥会线程不安全？

并发存取时，⽆法保证上⼀秒put的值，下⼀秒get的时候还是原值

5.有什么线程安全的类代替么?

HashTable,ConcurrentHashMap

6.默认初始化⼤⼩是多少？为啥是这么多？为啥⼤⼩都是2的幂？

初始化大小是16，采用位运算，位运算比算术效率高， 只要是2的幂就可以，就是为了哈希的时候分布更加均匀，减少哈希冲突

7.HashMap的扩容⽅式？负载因⼦是多少？为什是这么多？

扩容的时候，主要和当前hash表的长度和负载因子有关， `当长度超过（当前hash表长度* 负载因子）`，会触发扩容， 扩容的时候会创建一个空的entry数组，长度是当前长度的2倍，遍历原来的entry数组， 重新hash到新的数组，不采用直接复制主要是因为hash表的长度发生改变， hash规则也发生了改变，负载因子是0.75，如果是0.5，数组的长度只有一半会被利用， 就会导致哈希冲突变多，影响查询效率，如果是1的话，虽然能减少哈希冲突， 但是占用的空间大了，所以采用0.75是基于空间和时间的综合考虑

8.HashMap的主要参数都有哪些？

默认初始化容量：默认初始化容量，必须是2的次方

/** * The default initial capacity - MUST be a power of two. * 默认初始化容量，必须是2的次方 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

     默认初始化容量。这个是在采用无参构造方法实例化HashMap的时候，默认使用16作为初始化容量。在第一次put的时候使用16来创建数组。

最大容量：

/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. * 最大容量。即HashMap的数组容量必须小于等于 1 << 30 */ static final int MAXIMUM_CAPACITY = 1 << 30;

最大容量。但必须是2的次方数，我们来看下面这段代码：

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) //如果初始化容量大于最大容量，则仅初始化为最大容量。 initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }

可以看到，在指定容量的进行初始化时，会先判断这个初始化容量是否大于最大容量，超过则使用最大容量来进行初始化。 默认负载因子

/** * The load factor used when none specified in constructor. * 默认的负载因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认负载因子值为0.75，但是可以通过构造方法来指定。一般是不建议修改的。 树形化阈值

/** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8;

即当链表的长度大于8的时候，会将链表转为红黑树，优化查询效率。链表查询的时间复杂度为o(n) , 红黑树查询的时间复杂度为 o(log n ) 解树形化阈值

/** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6;

当红黑树的节点的个数小于等于6时，会将红黑树结构转为链表结构。 树形化的最小容量

/** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64;

前面我们看到有一个树形化阈值，就是当链表的长度大于8的时候，会从链表转为红黑树。其实不一定是这样的。转为红黑树有两个条件：

① 链表的长度大于8 ② HashMap数组的容量大于等于64

需要当上述两个条件都成立的情况下，链表结构才会转为红黑树

9.HashMap是怎么处理hash碰撞的？

HashMap使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。 hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时， 他们会存储在同一个bucket位置的链表中。键对象的equals()来找到键值对。

10.hash的计算规则？