高空利剑-数据结构-HashMap

1.HashMap的工作原理是什么?

HashMap在JDK1.7是通过数组+单向链表来实现的,在JDK1.8中是通过数组+单向链表+红黑树来实现的.这里拿JDK1.8版本来说把,一开始在数组中的每一个元素都是一个链表结构,而链表中的每一个节点都是一个Entry对象,这个Entry对象是用来存储真正的key-Value,也就是键值对的这个值,在HashMap中有两个比较重要的方法,一个是get()方法,一个是put()方法

1.先说一下put()方法,在存储K-V键值对的时候,HashMap通过key的hashCode经过扰动函数处理后得到hash值,然后将这个Hash值和数组的长度-1进行&运算,得到的结果也就是数组的下标,然后我们就根据这个下标去找到数组中存储的这个单向链表Node节点,然后把链表中的每一个key和要插入的key进行一个equals()比较,如果是相等的话,我们就直接更新这个Value值,如果不相等的话,就把新的K-V值 put()到链表中去,那么在put()过程中的话,当哈希表中存储的键值对超过了数组长度乘以负载因子的时候,就会将这个数组扩容为两倍,还有就是在插入链表的时候,如果链表长度超过了我们默认设置的阈值为8的时候,节点的数据结构就会自动转化为一个红黑树的结构

2.在说一下get()方法,在get()方法调用的时候和put()方法也比较类似,同样的HashMap通过key的hashCode经过扰动函数处理后得到hash值,然后将这个Hash值和数组的长度-1进行&运算,得到的结果也就是数组的下标,然后我们在遍历这个下标对应的链表元素,在进行equals()比较,如果key相同的话,就把这个元素取出并且返回给用户

总结一下,HashMap最核心的原理是利用Hash值来计算出下标的位置,然后再用equals()方法比较,equals()比较主要是解决Hash冲突的问题

2.HashMap如何解决哈希碰撞的?

1.Java中的HashMap主要是利⽤链地址法处理HashCode的碰撞问题。所谓 链地址法 就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
2.在调⽤HashMap的put⽅法或get⽅法时，都会⾸先调⽤hashcode⽅法，去查找相关的key，当有冲突时，再调⽤equals⽅法。例如当我们将键值对传递给put⽅法时，他会调⽤键对象的hashCode()⽅法来计算hashCode，然后找到哈希桶位置来存储对象。当两个不同的键却有相同的hashCode时，他们就会存储在同⼀个哈希桶位置的链表中。

3.为什么哈希表习惯将⻓度（capacity）设置为 2 的 n 次⽅？

减少哈希冲突，均匀分布元素。2的幂次⽅减1后除了最⾼位每⼀位都是1，让数组每⼀个位置都能添加到元素。例如⼗进制8，对应⼆进制1000，减1是0111，这样在&hash值使数组每个位置都是可以添加到元素，如果有⼀个位置为0，那么⽆论hash值是多少那⼀位总是0，例如0101，&hash后第⼆位总是0，也就是说数组中下标为2的位置总是空的。如果初始化⼤⼩设置的不是2的幂次⽅，hashmap也会调整到⽐初始化值⼤且最近的⼀个2的幂作为capacity。

4.Hash表超长以后转化成红包树,为什么使用红黑树?

红黑树是二叉查找树的一种,那么它的查找算法就相当于是二分查找,红黑树的时间复杂度O(log n )在数据比较多的时候会比链表的查询的时间复杂度O(n)要好很多

5.为什么JDK1.8之前，链表元素增加采⽤的是头插法，1.8之后改成尾插法了。1.8之前采⽤头插法是基于什么设计思路呢？

JDK1.7是考虑新增数据⼤多是热点数据，所以考虑放在链表头位置，也就是数组中，这样可以提⾼查询效率，但这种⽅式会出现插⼊数据是逆序的。在JDK1.8，hashmap链表在节点⻓度达到8之后会变成红⿊树，这样⼀来在数组后节点⻓度不断增加时，遍历⼀次的次数就会少很多，相⽐头插法⽽⾔，尾插法操作额外的遍历消耗已经⼩很多了。

6.HashMap 1.8扩容优化

1.在JDK中装填因子是0.75,装填因子 = 节点总数量 / 哈希表桶数组的长度 ,当put元素的时候,装填因子大于0.75就要扩容
2.在 JDK1.7 中，HashMap 整个扩容过程就是分别取出数组元素，⼀般该元素是最后⼀个放⼊链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的hash 值计算其在新数组中的下标，然后进⾏交换。这样的扩容⽅式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。
3.⽽在 JDK 1.8 中，HashMap 对扩容操作做了优化。由于扩容数组的⻓度是 2 倍关系，所以对于假设初始tableSize = 4 要扩容到 8 来说就是0100 到 1000 的变化（左移⼀位就是 2 倍），在扩容中只⽤判断原来的 hash 值和新数组⻓度-1做与运算，0 的话索引不变，1 的话索引变成原索引加上原数组⻓度。
4.之所以能通过这种与运算来重新分配索引，是因为 hash 值本来就是随机的，⽽ hash 按位与上newTable的长度-1 得到的二进制位 0（扩容前的索引位置）和 二进制位1（扩容前索引位置加上扩容前数组⻓度的数值索引处）就是随机的，所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。

一开始容量是2^2 ,我们计算key的索引是:数组长度- 1 (4-1=3二进制就是 11) 和 key的哈希值(1010)做&运算
  1010
&   11
-------
    10

现在扩容为2^3 我们计算key的索引是:数组长度- 1(8-1=7二进制就是 111) 和 key的哈希值(1010)做&运算
  1010
&  111
-------
    10

如果现在key的哈希值是1110,做&运算
  1110
&  111
-------
   110

当扩容为原来容量的两倍时候,节点的索引有两种情况
1.保持不变
2.二进制角度就是 原索引 前面 加1,十进制角度就是 原索引加上旧容量

7.为什么插⼊HashMap的数据需要实现hashcode和equals⽅法？对这两个⽅法有什么要求？

1.通过hashcode来确定插⼊下标，通过equals⽐较来寻找数据；两个相等的key的hashcode必须相等，但拥有相同的hashcode的对象不⼀定相等。
2.HashMap中需要使⽤hashcode来获取key的下标，如果两个相同对象的hashcode不同，那么会造成HashMap中存在相同的key；所以equals返回相同的key他们的hashcode⼀定要相同。

8.HashMap可不可以不使用链表,直接使用红黑树或者AVL树或者二叉搜索树?

我认为HashMap之所以没有选择一开始就使用红黑树,可能是因为时间和空间的折中考虑吧,在hash冲突比较小的时候,即使转化为红黑树之后,在时间复杂度上所产生的效果其实也并不是特别的大,而且呢,在put的时候效率可能会降低,毕竟每次put都要进行非常复杂的红黑树的这种旋转算法旋转操作,另外在空间上的话,每个节点都需要维护更多的一个指针,这就有点显的有点得不偿失了,最后就是HashMap之所以选择红黑树而不是二叉搜索树,我认为最主要的原因是二叉树在一些极端情况下它会变成一个倾斜的结构,查找效率就会退化成跟链表这个差不多了,而红黑树是一种平衡树,它可以防止这种退化,可以保持平衡,因为红黑树又不像其他的完全的平衡二叉树那样有严格的平衡条件,所以呢,红黑树插入效率要比完全的平衡二叉树要高,所以得话HashMap在选择红黑树既可以避免极端情况下的退化,也可以兼顾查询和插入的这种效率

9.HashMap是线程安全的么?

HashMap在设计的时候是针对单线程环境来设计的,所以在多线程环境下,它不是线程安全的

10.多线程并发环境下,如果需要一个Hash结构,如何实现?

如果在多线程并发环境下,我们可以使用ConcurrentHashMap来实现

11.ConcurrentHashMap的底层原理的理解

ConcurrentHashMap要分为两种情况来分析,一个是JDK1.7,另一个是JDK1.8之后,他们之间的差别是比较大得
1.在JDK1.7的时候,它的底层是使用数组加链表来实现的,使用了一种分段锁来保证线程安全,它是将数组分成了16段,也就是给每个Segment来配一把锁,然后再读每个Segment的时候就要先获取对应的锁,所以呢,它是最多能有16个线程并发去操作
2.在JDK1.8之后,它跟HashMap一样,也引入了这种红黑树的数据结构,同时在并发处理方面,不在使用分段锁的方式,而是采用CAS + Synchronized关键字的这种方式来实现一种更加细粒度的锁,相当于是把这个锁的控制,控制在了这种更加细粒度的哈希桶的这个级别,然后再写入键值对的时候,这个可以锁住哈希桶的这种链表的这个头结点,这样就不会影响到其他的哈希桶的写入,从而去提高对并发的处理能力

12.ConcurrentHashMap可以使用ReentrantLock作为锁么?

理论上来讲是可以的,但是我认为Synchronized关键字会更好一些吧,因为在JDK1.6之后对Synchronized关键字进行了一些优化,它里面引入了偏向锁,轻量级锁,和重量级锁,这些个锁在ReentrantLock中是没有的,并且随着JDK版本得不断升级,这个Synchronized也在进一步的优化,因为ReentrantLock是用java代码来实现的,所以在之后的话也很难有特别大的提升空间,所以得话让我选,我会优先选择Synchronized,然后次之才会选择ReentrantLock

13.Synchronized关键字对于锁的优化介绍

Synchronized默认采用的是偏向锁,在程序运行中始终是只有一个线程去获取这个Synchronized的这么一个锁,java对象中会记录一个线程的ID,我们在下次再获取这个Synchronized的锁时候,只需要去比较这个线程的ID就行了,在运行过程中如果出现第2个线程去请求Synchronized锁的时候,这里就分两种情况,
1.在没有发生并发竞争锁的情况下,这个Synchronized就会自动升级为轻量级锁,这个时候第2个线程就会尝试自旋锁的方式来获取锁,因为很快就能拿到锁,所以第2个线程也不会阻塞,
2.但是如果出现这种两个线程竞争锁的情况的话,这个Synchronized会自动升级为重量级锁,这个时候就是只会有1个线程能够获取到锁,那么另外一个线程它会阻塞,然后要等待第1个线程释放锁之后才能去拿到锁