# HashMap 介绍
- #### HashMap 是怎样实现的？
- hashmap 是由 数组 + 链表 + 红黑树实现的
- #### hashmap 为什么采用这种方式实现？
- 我们都知道hashmap是根据算得哈希值来确定数据存放的位置，但是我们也知道哈希值会一样，也就是哈希碰撞这种情况。
为了让哈希值一样的数据能有地方存储，于是采用了当发生哈希碰撞时，在原数据位置继续存放的方式，而链表这种数据结构就刚好满足要求
- java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高
- #### HashMap在jdk1.8之后引入了红黑树的概念，为什么采用6和8进行红黑树和链表转化？
- **6和8是指：表示若桶中链表元素超过8时，会自动转化成红黑树；若桶中元素小于等于6时，树结构还原成链表形式。**
- 原因：
- 1）红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
- 2）选择6和8的原因1：
如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
- 3）选择6和8的原因2：
中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
- #### hashmap 是如何提高散列程度的？
- ```java
// 数组容量2的倍数【resize()方法扩容体现出 】，目的是提高运算速度；增加散列度，降低冲突；减少内存碎片。
//左移一位。故数组容量2的倍数
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
```
- ```java
// hashcode的高16位与低16位进行异或，目的是增加散列度，降低冲突。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
- #### hashmap 提高散列程度为何这样实现？
- [https://blog.csdn.net/liuxingrong666/article/details/103640412](https://blog.csdn.net/liuxingrong666/article/details/103640412 "文章链接")
- #### HashMap 如何扩容？
- 当散列表中元素的个数，如果大于扩容阈值，会触发扩容
- 判断元素个数是不是超过最大值，若超过则置为最大值
- 扩容的容量为原来的2倍
- 若原来有元素，则把原来的元素拷贝到新数组中
-