HashMap说明
参考ForeverNoBug的博客，网址：https://blog.****.net/xianlvfan2224/article/details/102722298?utm_source=app#114HashMapgetput_571
对于产生冲突的链表：如果长度超过8，就转为为红黑树。链表长度低于6，则就把红黑树转回链表
ArrayList线程不安全，Vector线程安全。
HashMap线程不安全，HashTable线程安全。其中HashMap可以包含Null。
StringBuilder线程不安全，StringBuffer线程安全。
HashMap使用了数组、链表和红黑树来实现。其中的put和get方法。简单说HashMap是由数组+链表实现。
数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）
,那么查找、添加很快，仅需一次寻址既可。如果定位到的数组包含链表，对于添加（O(n)），首先遍历链表，存在即覆盖，否则新增。
对于查找，仅需遍历链表，然后通过key对象的equals方法逐一比对，查找链表越小，性能才会越好。
HashMap的put和get方法。
HashMap的put方法：如果key不存在，则直接插入，返回值为null；如果存在的话，则覆盖，且返回值为老的value值。
Map<String,String> map=new HashMap<String,String>();
String hh=map.put("1", "22");
String hh2=map.put("1", "33");
String hh3=map.put("1", "44");
String hh4=map.put("2", "44");
System.out.println(hh+" "+hh2+" "+hh3+" "+hh4); //null 22 33 null
以下是HashMap初始化 ，简单模拟数据结构
Node[] table=new Node[16] 散列桶初始化，table
class Node {
hash;//hash值
key;//键
value;//值
node next;//用于指向链表的下一层（产生冲突，用拉链法）
}
对于产生冲突的链表：如果长度超过8，就转为为红黑树。链表长度低于6，则就把红黑树转回链表。具体流程入戏：
1、对Key求Hash值，然后再计算下标
2、如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到同一个bucket中）
3、如果碰撞了，以链表的方式链接到后面
4、如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
5、如果节点已经存在就替换旧值
6、如果桶满了(容量16*加载因子0.75)，就需要 resize（扩容2倍后重排）
扰动函数可以减少碰撞。
扰动函数可以减少碰撞，原理是如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这就意味着存链表结构减小，这样取值的话就不会频繁调用equal方法，这样就能提高HashMap的性能。（扰动即Hash方法内部的算法实现，目的是让不同对象返回不同hashcode。）
使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生。
为什么String, Interger这样的wrapper类适合作为键？因为String是final的，而且已经重写了equals()和hashCode()方法了。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。
5、拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。
7、解决hash 碰撞还有那些办法？
开放定址法。
当冲突发生时，使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的地址。
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
下面给一个线性探查法的例子
问题：已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
解答：为了减少冲突，通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。
前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。
当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。
当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。
当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。
类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
8、如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置
9 get方法
先前HashMap通过hash code来存放数据，那么get方法一样要通过hash code来获取数据。可以看到如果当前table没有数据的话直接返回null，反之通过传进来的hash值找到对应节点（Node）first，如果first的hash值以及Key跟传入的参数匹配就返回对应的value，反之判断是否是红黑树，如果是红黑树则从根节点开始进行匹配如果有对应的数据则结果，否则返回Null，如果是链表的话就会循环查询链表，如果当前的节点不匹配的话，就会从当前节点获取下一个节点来进行循环匹配，如果有对应的数据则返回结果，否则返回Null。