HashMap的底层数据结构？

HashMap 是咱们十分罕用的数据结构，由数组和链表组合形成的数据结构。数组里每个中央都存了Key-Value这样的实例，在Java7叫Entry，在Java8中叫Node。

初始化后所有的地位都为null，在put插入的时候会依据key的hash去计算一个index值。

链表？为啥须要链表？链表具体是什么样的？

数组的长度是无限的，在无限的长度外面应用哈希，哈希本事就存在肯定的概率性，当两个key的hash一样时就会hash到一个值上，造成链表。

每个节点都会有本身的hash、key、value、以及下个节点，Node的源码：

static class Node<K,V> implements Map.Entry<K,V>{    final int hash;    fianl K key;    V value;    Node<K,V> next;    ...}
链表，新的Entry节点在插入链表的时候，是怎么插入的？

Java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，因为过后设计这段代码的作者认为起初的值被查找的可能性更大一点，晋升查找的效率。

Java8之后，都是采纳尾部插入。

为什么改用尾插法？

改用尾插法是因为HashMap的扩容机制，数组容量是无限的，数据屡次插入，到肯定的数量就会进行扩容，也就是resize。

什么时候resize？

resize的两个条件：

  • Capacity：HashMap以后长度。
  • LoadFactor：负载因子，默认值0.75f
/** * The load factor used when none specfified in constructor */static final float FEFAULT_LOAD_FACTOR=0.75f;

简略的了解就是，如果以后容量是100，当存进第76个的时候，判断发现须要进行resize了，那就进行扩容。

HashMap是怎么扩容的？

分两步：

  • 扩容：创立一个新的Entry空数组，长度为原数组的2倍。
  • Rehash：遍历原Entry数组，把所有的Entry从新Hash到新数组。
为什么不间接复制，为什么须要从新Hash？

因为长度扩充后，Hash的规定也随之扭转。

Hash公式：index = HashCode(Key)  & (Length-1)

扩容后Length产生了扭转，从新计算的index与扩容前显著不一样。

Java8以前用头插法，Java8之后为什么改为尾插法了呢？

先举个例子吧，咱们当初往一个容量大小为2的put两个值，负载因子是0.75，咱们在put第二个的时候就会进行resize ，当初咱们要在容量为2的容器外面用不同线程插入A，B，C，如果咱们在resize之前打个断点，那意味着数据都插入了然而还没进行resize那扩容前可能是这样的，咱们能够看到链表的指向A->B->C

Tip：A的下一个指针是指向B的

因为resize的赋值形式，也就是应用了单链表的头插入方式，同一地位上新元素总会被放在链表的头部地位，在旧数组中同一条Entry链上的元素，通过从新计算索引地位后，有可能放到了新数组的不同地位上。

可能呈现如下状况，B的下个指针指向了A：

一旦几个线程同时都调整实现，就可能呈现环形链表。

如果这个时候去取值，就会呈现--Infinite Loop。

Java8之后的尾插法

应用头插法会扭转链表的程序，如果应用尾插，在扩容的时候放弃链表元素原来的程序，就不会呈现链表成环的问题了。

就是说本来是A->B，在扩容后那个链表还是A->B


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

那是不是意味着Java8就能够把HashMap用在多线程中？

Java8中HashMap即便不会呈现死循环，然而通过源码看到put/get办法都没有加同步锁，多线程状况下最容易呈现的就是：无奈保障上一秒put的值下一秒get的时候还是原值，所以线程平安还是无奈保障。

HashMap的默认初始化长度是多少？

源码显示初始化大小是16

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

这样是为了位运算的不便，位与运算比算数计算的效率高了很多，之所以抉择16，是为了服务将Key映射到index的算法。咱们是通过key的HashCode值去做位运算，

比方说：key为“你好”的二进制是123456那二进制就是11110001001000000

index 的计算公式;index = hashCode(key) & (Length-1)

15的二进制是1111，那 11110001001000000 & 1111十进制就是4

用位与运算成果和取模一样，性能也进步了不少！

为什么用16不必别的呢？

因为应用2的幂的数字的时候，Length-1的值所有二进制位全为1，这种状况下，index的后果等同于HashCode后几位的值。只有输出的HashCode自身散布平均，Hash算法的后果就是均匀分布的。

这是为了实现均匀分布。

为啥我没重写equals办法的时候须要重写HashCode办法呢？用HashMap举例

因为在Java中，所有的对象都继承于Object类。Object类中有两个办法，equals、hashCode，这两个办法都是用来比拟两个对象是否相等的。在未重写equals办法时候咱们是继承object的equals办法，那个equals是比拟两个对象的内存地址，显然咱们new了两个对象内存地址必定不一样，在HashMap中通过key的hashCode去寻找index的，如果index一样就造成了链表了，当咱们依据key去hash而后计算出index，找到了2两个或多个，具体找哪个值就不晓得了

equals！所以咱们对equals办法进行了重写，倡议肯定要对hashCode办法重写，以保障雷同的对象返回雷同的hash值，不同的对象返回不同的hash值。

HashMap的线程是不平安的，怎么解决HashMap在线程平安的场景

在须要线程平安的场景应用个别应用HashTable或者ConcurrentHashMap，然而HashTable的并发度的起因基本上很少应用，存在线程不平安的场景的时候咱们都是应用ConcurrentHashMap。

HashTable的源码很简略粗犷，间接在办法上加锁，并发度很低，最多同时容许一个线程拜访，ConcurrentHashMap 就好很多，1.7和1.8有较大的不同，不过并发度都比前者好太多了。

学习技术，问题探讨，举荐退出我的Java学习园地。