[数据结构与算法]HashMap的个人理解V21.12.31

一、版本区别

HashMap的实现方式是分版本而定的

1.在jdk1.7的版本中HasnMap的底层是由数组+链表实现的；

在jdk1.8的版本中采用了红黑树，也就是1.8之后HashMap的底层是由数组+链表+红黑树实现的。

2.在jdk1.7的版本中HasnMap采用的是头插法存储；

在jdk1.8的版本中采用的是尾插法。

二、为什么HashMap会由头插法变成尾插法？【面试点】

因为jdk1.7的版本中采用的头插法，在存储过程中对链表的存储过程中是由头部插入。这样在多线程的情况下很容易发生死锁问题。

即：因为在HahMap的存储过程中发生哈希碰撞时链表的查询方式是从头部开始进行查询，查询效率也就是O(n)。而恰恰在存储的时候他也是从头部开始进行插入。试想在多线程的情况下，一个在进行put存储，一个在进行查询操作。这样极为容易发生死锁问题。

所以在jdk1.8的版本中采用了尾插法，从链表底部开始存储，这样就避免了多线程情况下死锁问题。

由上而答，极为容易会继续问你什么是哈希碰撞？

三、什么是哈希碰撞？

众所周知，HashMap的底层是由数组+链表组成，所以HashMap的put方法在进行存储过程中会首先会根据键进行一个哈希运算。然后得出一个index进行一个对数组的存储。等等，因为在HashMap源码中，对数组的默认长度有一个设定，即为16。下面是源码：

//这个就是对hashMap源码中对数组的一个默认长度的设定 
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

因为在很多元素的情况下，在通过Hash运算出相同哈希值得情况下，往同一数组空间中存储的情况下就会发生哈希冲突。也就采用链表的形式就行存储。

在通过上面回答了什么是哈希冲突以后，也会继续问你什么是哈希运算。

四、什么是哈希运算？

哈希运算呢，这个先看源码：

//这个就是计算下标的hash源码   
static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

通过源码可以看到int类型h在得到键的hashcode值的情况下会进行%16算出一个数组的下标存储位置。

五、对红黑树又有多少理解？

红黑树的满足条件：

1.红黑树的是分为根节点和子节点组成，根节点是黑色，子节点是红色。

2.红色节点不能连续（红节点的孩子和父亲都必须是黑色）。

3.对于每个节点,从该节点至NIL树的尾端的任何路径,都含有相同的黑色节点数。

4.每个叶子节点都是黑色的空节点（NIL节点)。

六、还知道一些别的了解吗？

剩下基本上都是一些散列的了解。

例如

1.HashMap的加载因子是0.75；

2.HashMap进化成红黑树的条件？

(1).当链表长度大于8时，会自动转成红黑树进行存储；

(2).在HashMap中也有Remove方法，当链表长度等于6时，会从红黑树继续转成链表存储。

七、那你知道加载因子为什么是0.75而不是1或者是0.5么？

1.加载因子为1，空间利用率得到了很大的满足，很容易碰撞，产生链表，查询效率低。

2.加载因子为0.5，碰撞的概率低，产生的链表概率低，查询效率高，空间利用率低。

????所以0.5-1之间，取中间0.75。

剩下还有好多好多，未完……希望可以的话有大佬指点一下。