Hashmap学习笔记
参考了很多博客自己手动整理学习一下hashmap。
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
从图中可以看出：
① HashMap继承于AbstractMap类，实现了Map接口。Map是"key-value键值对"接口，AbstractMap实现了"键值对"的通用函数接口。
② HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。
table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。
size是HashMap的大小，它是HashMap保存的键值对的数量。
threshold是HashMap的阈值，最多容纳Entry的个数，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量*2扩增。
loadFactor就是加载因子。
modCount是用来实现fail-fast机制的。
※补充：
1）拉链法：
拉链法解决冲突：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，加载因子α可以大于1，但一般均取α≤1。
在拉链（单链表）的哈希表中搜索一个记录是容易的，首先计算哈希地址，然后搜索该地址的单链表。
拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度
2）加载因子：
①什么是加载因子？加载因子（n/m:n为输入域的关键字个数，m为位桶的数目）。比如定义 16的散列空间，存放了12个关键字 那么此时加载因子α=0.75 即，加载因子表示hash表中存放元素的填满程度。
②为何加载因子越小越好？打个比方，房间大小一定，住的人越少越舒坦。参考原因在下边。看一下，无论哪一个处理加载因子越小成功查找的次数越少，不成功查找次数越多。所以尽量保证小一点的加载因子。
clear()
clear() 的作用是清空HashMap。它是通过将所有的元素设为null来实现的。
containsKey()
containsKey() 的作用是判断HashMap是否包含key。
containsKey() 首先通过getEntry(key)获取key对应的Entry，然后判断该Entry是否为null。
getEntry() 的作用就是返回“键为key”的键值对，它的实现源码中已经进行了说明。
这里需要强调的是：HashMap将“key为null”的元素都放在table的位置0处，即table[0]中；“key不为null”的放在table的其余位置！
containsValue()
containsValue() 的作用是判断HashMap是否包含“值为value”的元素。
containsNullValue() 的作用判断HashMap中是否包含“值为null”的元素。
entrySet()、values()、keySet()
entrySet()的作用是返回“HashMap中所有Entry的集合”，它是一个集合。
get()
get() 的作用是获取key对应的value
put()
put() 的作用是对外提供接口，让HashMap对象可以通过put()将“key-value”添加到HashMap中。
若要添加到HashMap中的键值对对应的key已经存在HashMap中，则找到该键值对；然后新的value取代旧的value，并退出！
若要添加到HashMap中的键值对对应的key不在HashMap中，则将其添加到该哈希值对应的链表中，并调用addEntry()。
addEntry() 的作用是新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
说到addEntry()，就不得不说另一个函数createEntry()。
它们的作用都是将key、value添加到HashMap中。而且，比较addEntry()和createEntry()的代码，我们发现addEntry()多了两句：
(01) addEntry()一般用在 新增Entry可能导致“HashMap的实际容量”超过“阈值”的情况下。
例如，我们新建一个HashMap，然后不断通过put()向HashMap中添加元素；put()是通过addEntry()新增Entry的。
在这种情况下，我们不知道何时“HashMap的实际容量”会超过“阈值”；
因此，需要调用addEntry()
(02) createEntry() 一般用在 新增Entry不会导致“HashMap的实际容量”超过“阈值”的情况下。
例如，我们调用HashMap“带有Map”的构造函数，它绘将Map的全部元素添加到HashMap中；
但在添加之前，我们已经计算好“HashMap的容量和阈值”。也就是，可以确定“即使将Map中的全部元素添加到HashMap中，都不会超过HashMap的阈值”。
此时，调用createEntry()即可。
putAll()
putAll() 的作用是将"m"的全部元素都添加到HashMap中
remove()
remove() 的作用是删除“键为key”元素
本人主要参考如下博客，尤其第一个链接博客写的特别好，如下
https://www.cnblogs.com/skywang12345/p/3310835.html#b2
https://blog.****.net/a544879146/article/details/71122725