Java数据结构 之 HashMap 重温学习
个人能力有限，暂时不整理温习 红黑二叉树
该篇文章主要讲述 HashMap 、ConcurrentHashMap 部分区别（从扩容消耗内存方面 介绍下ArrayMap），在文章末尾会简单的提到 List 部分的面试知识点。
update time 2019年12月09日13:33:53
1. HashMap
这里的HashMap 主要针对 JDK 1.8 版本，JDK1.7 没有引入红黑树概念
HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。它是基于哈希表的 Map 接口的非同步实现。
数组：存储区间连续，占用内存严重，寻址容易，插入删除困难；
链表：存储区间离散，占用内存比较宽松，寻址困难，插入删除容易；
Hashmap 综合应用了这两种数据结构，实现了寻址容易，插入删除也容易。
效果图
在这里插入图片描述
主要参数说明
/**
* 主要参数 同 JDK 1.7
* 即：容量、加载因子、扩容阈值（要求、范围均相同）
*/
// 1. 容量（capacity）： 必须是2的幂 & <最大容量（2的30次方）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 = 2的30次方（若传入的容量过大，将被最大值替换）
// 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
final float loadFactor; // 实际加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子 = 0.75
// 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量）
// a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
// b. 扩容阈值 = 容量 x 加载因子
int threshold;
// 4. 其他
transient Node<K,V>[] table; // 存储数据的Node类型 数组，长度 = 2的幂；数组的每个元素 = 1个单链表
transient int size;// HashMap的大小，即 HashMap中存储的键值对的数量
/**
* 与红黑树相关的参数
*/
// 1. 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 3. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
// 否则，若桶内元素太多时，则直接扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
核心参数图解
image
2. hash() 方法
hash方法其实在java8中也做了优化：只向右移动一次使高位移动向低位，和hash值做 异或处理，使高位添加到运算 但是由于计算出来的值太大，hashmap初始大小只有16，所以要和（长度-1）做一次并运算，保留长度内的数据以此来达到降低key冲突的百分比
image
测试的运算过程
image
3. HashMap 的put方法
流程图如下
（唉 那里都有二叉树么）
在这里插入图片描述
- 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容，设置容量 阙值等初始化工作，（注意 若哈希表的数组tab为空，则 通过resize() 创建，所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建）
- 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向第六步，如果table[i]不为空，转向第三部；
- 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向第四步，这里的相同指的是hashCode以及equals；
- 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向第五步；
- 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
- 插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过，进行扩容，然后结束整个流程。
4. HashMap扩容
hashmap 添加的时候 如果长度没有大于8，保持链表插入 ，插入后判断是否转换为红黑树(前提Hash表的数量已经超过数组最小)，如果依然为链表，判断长度是否大于阙值，如果扩容则直接长度 *2 ，至于扩容后的位置则通过计算方式来计算
部分源码：
/**
* resize（）
* 该函数有2种使用情况：1.初始化哈希表 2.当前数组容量过小，需扩容
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 扩容前的数组（当前数组）
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的数组的容量 = 长度
int oldThr = threshold;// 扩容前的数组的阈值
int newCap, newThr = 0;
// 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 针对情况2：若无超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 通过右移扩充2倍
}
// 针对情况1：初始化哈希表（采用指定 or 默认值）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表优化重hash的代码块
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
通过图表说明：
image
扩容位置算法示意图
image
相对与 JDK 1.7在计算新元素的存储位置有很大区别：JDK 1.7在扩容后，都需按照原来方法重新计算，即
hashCode（）->> 扰动处理 ->>（h & length-1）），JDK 1.8 做了部分的优化，提高了扩容效率。
读完以上内容 我们知道HashMap中默认的存储大小就是一个容量为16的数组，所以当我们创建出一个HashMap对象时，即使里面没有任何元素，也要分别一块内存空间给它，而且，我们再不断的向HashMap里put数据时，当达到一定的容量限制时（这个容量满足这样的一个关系时候将会扩容：HashMap中的数据量>容量加载因子，而HashMap中默认的加载因子是0.75），HashMap的空间将会扩大，而且扩大后新的空间一定是原来的2倍，所以我们建议在知道数据大小的时候,初始化HashMap时就设置好数据容量,以免在扩容过程中 不断地Hash计算来消耗内存*
上段文字其实也算一个引子，推荐 使用 parseArray 和 ArrayMap 来代替HashMap
简单介绍：ArrayMap是一个<key,value>映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作，所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。
更加详细的 源码级介绍：
ArrayMap详解
2 HashMap其他 可能面试的问题
大体知识点总览
image
2.1 哈希表解决Hash 冲突
image
2.2 键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化
image
HashMap 线程不安全的其中一个重要原因：多线程下容易出现resize（）死循环
本质 : 并发 执行 put（）操作导致触发 扩容resize（），转移数据操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况,从而导致 环形链表，使得在获取数据遍历链表时形成死循环.
由于 JDK 1.8 转移数据操作 : 按旧链表的正序遍历链表、在新链表的尾部依次插入，所以不会出现链表 逆序、倒置的情况，故不容易出现环形链表的情况。(但是还是不建议 多线程高并发中使用Hashmap，官方推荐使用 ConcurrentHashMap)
2.3 为什么 key 多推荐使用 String、Integer
image
2.4 HashMap 中的 key若 Object类型， 则需实现哪些方法？
String Integer 中都默认实现了 hashcode() 和 equals() 方法
image
至于其
-
HashMap 和 ArrayMap 的区别（数组扩容方式 ）
ArrayMap ：通过 Hash/ （key/value）的存储方式优化数组空间，一种独特的方式，能够重复的利用因为数据扩容而遗留下来的数组空间HashMap ： 初始值16个长度，每次扩容的时候，直接申请双倍的数组空间，尾插法，添加到数组/链表/红黑树子节点.
ArrayMap ： 每次扩容的时候，如果size长度大于8时申请size*1.5个长度，大于4小于8时申请8个，小于4时申请4个。 -
HashMap 和 LinkedHashMap的区别
LinkedHashMap - 参考文章 -
深入LinkedHashMap 了解 LRU 缓存 （个人吃过很多亏）
LinkedHashMap 及 LRU 缓存 - 参考文章
HashMap 和 LinkedHashMap 简单区别：LinkedHashMap 是HashMap的子类，双向链表保存了记录的插入顺序，在遍历LinkedHashMap时，先得到的记录是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。
- ConcurrentHashMap 了解吗？（多并发）
ConcurrentHashMap 参考文章
个人对ConcurrentHashMap 多线程并发中做的工作：在添加元素时候，采用synchronized来保证线程安全，然后计算size的时候采用CAS操作进行计算。在扩容期间通过给不同的线程设置不同的下表索引进行扩容操作，就是不同的线程，操作的数组分段不一样，同时利用synchronized同步锁锁住操作的节点，保证了线程安全。
ArrayList、LinkedList、Vector 的区别
ArrayList、LinkedList、Vector 数据结构区别
ArrayList和Vector是按照顺序将元素存储（从为0开始），删除元素时，删除操作完成后，需要使部分元素移位，默认的初始容量都是10.
ArrayList和Vector是基于数组实现的，LinkedList是基于双向链表实现的（含有头结点）。所以 ArrayList和Vector 更加适合于随机访问数据，LinkedList 由于基于链表实现，在插入和删除的时候只需要修改指针指向地址就可以了，所以更适合插入和删除操作。（不过由于LinkedList双向链表，支持双向查找。查找前会根据指定位置index判断是在链表的前半段还是后半段，从而决定是从前往后找或是从后往前找，提升查找效率。）
ArrayList、LinkedList、Vector 多线程
ArrayList、LinkedList不具有线程安全性（并且LinkedList在单线程的中，也是线程不安全的），如果在并发环境下使用它们，可以用Collections类中的静态方法synchronizedList(）对ArrayList和LinkedList进行调用即可。
List list = Collections.synchronizedList(new LinkedList(...));
Vector实现线程安全的，即它大部分的方法都包含关键字synchronized,但是Vector的效率没有ArraykList和LinkedList高。
ArrayList、LinkedList、Vector 扩容
ArrayList和Vector都是使用Object的数组形式来存储的，当向这两种类型中增加元素的时候，若容量不够，需要进行扩容。ArrayList扩容后的容量是之前的1.5倍，然后把之前的数据拷贝到新建的数组中去。而Vector默认情况下扩容后的容量是之前的2倍（扩容都通过新建数组，将老数组数据copy到新数组中）。
由于LinkedList 为双向链表，不存在容量，所以不需要扩容。
Vector可以设置容量增量，而ArrayList不可以。在Vector中，有capacityIncrement：当大小大于其容量时，容量自动增加的量。如果在创建Vector时，指定了capacityIncrement的大小，则Vector中动态数组容量需要增加时，如果容量的增量大于0，则增加的是大小是capacityIncrement，如果增量小于0，则增大为之前的2倍。
网友评论