山东规划 建设部门的网站,wordpress文章专题插件,用万网做网站,cn域名知名网站由经典面试题引入#xff0c;讲解一下HashMap的底层数据结构#xff1f;这个面试题你当然可以只答#xff0c;HashMap底层的数据结构是由#xff08;数组链表红黑树#xff09;实现的#xff0c;但是显然面试官不太满意这个答案#xff0c;毕竟这里有一个坑需要你去填讲解一下HashMap的底层数据结构这个面试题你当然可以只答HashMap底层的数据结构是由数组链表红黑树实现的但是显然面试官不太满意这个答案毕竟这里有一个坑需要你去填那就是在回答HashMap的底层数据结构时需要考虑JDK的版本因为在JDK8中相较于之前的版本做了一些改进不仅仅是增加了红黑树的数据结构、还包括了链表结点的插入由头插法改成了尾插法这些都是底层数据结构的优化问题。 JDK8中HashMap的数据结构 从上面数据结构原理图中我们能看出数组和链表是如何组合使用的数组不是实际保存数据的结构数组保存的是NodeK,V的对象引用地址实际保存数据的是NodeK,V结点类。数组中的每个位置只能保存一个NodeK,V对象通过链表可以在同一位置保存多个数据还有链表会在一定条件下转化为红黑树。
table数组
// 用于保存 NodeK,V 类型的数组
transient NodeK,V[] table; HashMap的默认初始化容量指的是table数组大小// HashMap的默认初始化容量为161位运算左移4位static final int DEFAULT_INITIAL_CAPACITY 1 4; HashMap的默认负载因子用于计算阈值
// HashMap的负载因子用于计算阈值超过阈值即负载过大需要数组扩容
static final float DEFAULT_LOAD_FACTOR 0.75f; HashMap的阈值当HashMap中的元素个数超过阈值时数组会扩容为原大小的2倍// 扩容的阈值(默认阈值 默认数组容量 * 负载因子)默认为12 16 * 0.75int threshold; HashMap的链表转换为红黑树的阈值
// 树化的阈值不是唯一条件而是必须条件
static final int TREEIFY_THRESHOLD 8;
NodeK,V结点类// HashMap源码的静态内部类
static class NodeK,V implements Map.EntryK,V {final int hash; // 保存key计算出的hash码final K key; // 保存key的值V value; // 保存value的值NodeK,V next; // 保存下一个结点的引用地址Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;} HashMap的构造方法 HashMap的无参构造
// 此时只设置了默认的负载因子即数组未初始化
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; }
HashMap的带负载因子和数组容量的构造方法// 可设置自定义负载因子和数组容量
public HashMap(int initialCapacity, float loadFactor) {// 数组容量不能小于0if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);// 数组容量不能大于MAXIMUM_CAPACITYif (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;// 负载因子不能小于等于0if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;// 用于计算table数组的最终大小因为数组大小必需为2的n次方数this.threshold tableSizeFor(initialCapacity);
}
HashMap的可传入Map集合数据的构造方法
public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;// 遍历Map取出集合的数据依次放入HashMap中putMapEntries(m, false);
} HashMap的put方法 HashMap的put方法实际调用了putVal方法
public V put(K key, V value) {// 计算key的哈希值创建NodeK,V结点放入数组中return putVal(hash(key), key, value, false, true);
} HashMap的hash方法返回的哈希值并不是直接调用Object对象的hashCode()方法返回的那个哈希值而是经过了异或运算后的哈希值。
// 计算key的哈希值的方法
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
} 异或运算就是两个二进制数值按位比较同位的值相同则为0同位的值不同则为1。我们分析一下先计算出key的哈希值用作第一个数再把key的哈希值右移16位作为第二个数然后再把两个数值进行异或运算^。这样计算出的哈希值会变得更随机因为增加了高16位参与能降低哈希冲突的概率。
// 425918570 对应的32位的二进制哈希值 // 高16位 低16位
0001 1001 0110 0011 --- 0000 0000 0110 1010 // 原始哈希值
0000 0000 0000 0000 --- 0001 1001 0110 0011 // 原始哈希值右移16位的值
0001 1001 0110 0011 --- 0001 1001 0000 1001 // 异或运算得到的哈希值
putVal方法是添加数据的核心方法table数组会在第一次添加元素时进行初始化默认初始化容量为16在添加数据时需要通过哈希值计算出数据放入的table数组所在的索引下标位置。添加完元素后需要判断数组是否需要扩容扩容大小是原数组的两倍。// HashMap添加数据的核心方法// onlyIfAbsent false表示key相等时会覆盖旧valuefinal V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;// table数组是第一次使用时才进行初始化懒惰使用if ((tab table) null || (n tab.length) 0)// resize()包括了数组的初始化和扩容n (tab resize()).length;// table数组当前计算出的下标位置还未保存过元素if ((p tab[i (n - 1) hash]) null)// 创建新结点直接放入计算出的数组下标位置中tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;// 出现哈希冲突需要判断是否是相同key,因为不同key也可能有相同的哈希值if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;// 当前计算的数组下标保存的是树结点即红黑树结构else if (p instanceof TreeNode)// 采用红黑树的插入方法e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {// 从数组下标所在的头结点开始遍历链表for (int binCount 0; ; binCount) {// 找到尾结点在尾结点后插入新结点即尾插法if ((e p.next) null) {// 先插入结点再判断阈值故链表长度大于8时才是树化必须条件p.next newNode(hash, key, value, null);// 链表的长度大于8时走树化方法if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);break;}// 如果当前遍历到的链表结点和需要添加的数据key相同则无需插入直接退出if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}// 添加结点数据时发现key已经存在此时不是插入而是更新if (e ! null) { V oldValue e.value;// put相同key的数据时会覆盖旧值if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);// 返回当前key的旧值return oldValue;}}modCount;// HashMap中元素个数大于阈值进行扩容if (size threshold)resize();afterNodeInsertion(evict); return null;
}
putVal方法中添加NodeK,V的结点元素时如何计算元素所在的table数组下标位置呢这里就需要用到我们的哈希值了我们可以利用哈希值对数组的最大索引下标值进行取模运算这样就可以把取模运算的结果当做数组的下标位置。但是实际源码中并不是这样做的而是采用了与运算利用哈希值和数组的最大索引下标进行按位与运算。
// 32位的二进制哈希值// 高16位 低16位
0001 1001 0110 0011 --- 0001 1001 0000 1001 // 最终计算出的哈希值
0000 0000 0000 0000 --- 0000 0000 0000 1111 // table数组的最大索引下标使用默认大小就是15
0000 0000 0000 0000 --- 0000 0000 0000 1001 // 与运算的结果 9即下标位置 HashMap的数组长度为2的n次方数的原因 面试经常会问HashMap的数组长度为什么强制使用2的幂次方数要回答这个问题那么我们就需要知道数组长度在哪个地方用到了通过源码我们发现数组的长度被用于添加元素时计算数组的下标位置。数组下标是通过与运算计算出来的与运算的特点是全1为1有0为0而2的幂次方数减一正好保证后面全为1这样就可以使与运算计算的结果降低相同值的概率本质就是减少哈希冲突的概率。
// 数组下标计算公式
int i (n - 1) hash// 当hash值为10数组长度n为9时
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 影响运算的有效位为1位容易产生哈希冲突
0000 0000 0000 0000 --- 0000 0000 0000 1000 // (n - 1)的值为8
0000 0000 0000 0000 --- 0000 0000 0000 1000 // 计算出的数组下标为8// 当hash值为10数组长度n为16时
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 影响运算结果的有效位为4位不易产生哈希冲突
0000 0000 0000 0000 --- 0000 0000 0000 1111 // (n - 1)的值为15
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 计算出的数组下标为10
数组扩容后NodeK,V元素的存放的数组下标位置变化不大只有两种可能不是在新数组的原索引值位置就是在原索引值原数组长度的位置。我们知道数组扩容是在原数组容量的基础上乘以2根据原理可推断在重新计算元素保存的数组下标位置时(n - 1)带来的影响很小只会增加一个有效位的计算。即扩容前(n - 1) 15是4个1扩容后(n - 1) 31是5个1。
// 数组下标计算公式
int i (n - 1) hash// 当hash值为10扩容前数组长度n为16
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 运算结果的有效位为4位
0000 0000 0000 0000 --- 0000 0000 0000 1111 // (n - 1)的值为15
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 计算出的数组下标为10// 当hash值为10扩容后数组长度n为32
// 高16位 低16位
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 运算结果的有效位为5位增加一位有效位计算
0000 0000 0000 0000 --- 0000 0000 0001 1111 // (n - 1)的值为31
0000 0000 0000 0000 --- 0000 0000 0000 1010 // 计算出的数组下标还是10 HashMap的链表树化的条件 链表什么时候树化我们可以查看在添加结点时判断是否需要树化的源码逻辑。
// 树化的阈值不是唯一条件而是必须条件
static final int TREEIFY_THRESHOLD 8;// 当遍历的结点数大于等于8时
if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st// 进入是否需要树化的方法treeifyBin(tab, hash); 从源码中我们可以了解到链表转换为红黑树需要满足两个条件一是数组的容量需要大于64二是链表的长度要大于阈值8。当必要条件链表的长度要大于8时才会选择优化缩短链表长度此时不一定就需要直接转换为红黑树还可以通过扩容数组的方式来使链表长度变短所以当数组的容量小于64时是采取数组扩容来优化链表的。
// 将链表结点转换为红黑树如果数组容量太小则先扩容数组
final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;// 数组为空或容量小于64扩容数组if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();// 找到当前链表的头结点else if ((e tab[index (n - 1) hash]) ! null) {TreeNodeK,V hd null, tl null;// 遍历普通结点链表转换为树结点的双向链表do {// 链表结点替换成树结点返回TreeNodeK,V p replacementTreeNode(e, null);// 第一次保存树的头结点if (tl null)hd p;else {// 树结点间建立双向链表关系p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);// 将数组中的普通结点链表替换成树结点的双向链表if ((tab[index] hd) ! null)// 构造生成红黑树hd.treeify(tab);}} JDK8的HashMap为什么在链表中使用尾插法代替了头插法 链表结点的头插法就是在链表的头部插入数据就是每次插入的新结点数据都会成为链表的头结点。JDK7的HashMap中是否真的使用了头插法我们可以从源码中求证。// 用于添加EntryK,V结点的方法jdk1.7叫Entry
void createEntry(int hash, K key, V value, int bucketIndex) {// table数组保存的头结点Entry保存到e变量EntryK,V e table[bucketIndex];// 1. 把e元素作为新结点的next结点即原头结点作为新结点的下一个结点// 2. 新结点作为头结点保存到table[bucketIndex]即头插法table[bucketIndex] new Entry(hash, key, value, e);// HashMap中保存的元素总数1size;}
链表结点的尾插法就是在链表的尾部插入数据这样就需要遍历链表找到尾结点使尾结点的NodeK,V next结点指向新结点。JDK8的HashMap添加结点使用尾插法的源码实现就是如此前面在源码中已经看到过。// 从数组下标所在的头结点开始遍历链表
for (int binCount 0; ; binCount) {// 找到尾结点在尾结点后插入新结点即尾插法if ((e p.next) null) {// 新结点作为尾结点的next结点并成为新尾结点p.next newNode(hash, key, value, null);// 链表的长度大于8时走树化方法if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);break;}// 如果当前遍历到的链表结点和需要添加的数据key相同则无需插入直接退出if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;
} 了解了头插法和尾插法的区别那么JDK8中的HashMap为什么抛弃了头插法而使用尾插法呢这是因为头插法在数组扩容时链表重新在新数组中生成时会导致链表元素倒序这里比较难理解。因为链表的遍历是从头结点开始的而链表插入是头插法会一直更新头结点所以就是最早插入的结点成为尾结点最后插入的结点成为头结点这是头插法的特点。这里的链表元素倒序表面上看起来问题不大但是在多线程同时操作一个HashMap的情况下容易产生死链问题这才是根本的。JDK7中的HashMap在数组扩容时为什么会死链当然这是并发问题是可能出现不是说一定就会死链。我们要结合扩容的源码进行分析不一定要非常深入理解能找到问题所在就行。
// jdk1.7的扩容过程
void transfer(Entry[] newTable, boolean rehash) {// 获取新数组的容量int newCapacity newTable.length;// 遍历旧数组获取头结点单节点也是链表for (EntryK,V e : table) {// 遍历链表while(null ! e) {// 取出当前结点的next结点EntryK,V next e.next;// 判断是否需要重新计算hash值if (rehash) {e.hash null e.key ? 0 : hash(e.key);}// 因为数组扩容了重新计算元素存放的数组位置int i indexFor(e.hash, newCapacity);// 当前添加的结点e作为头结点所以它的e.next指向旧的头结点e.next newTable[i];// 最新添加的结点成为新数组保存的头结点每次更新头结点即头插法newTable[i] e;// 遍历的写法取下一个节点e next; }}
} 分析Entry[ ] newTable作为外部传入的引用变量存在线程安全问题Entry[ ] table不是方法的局部变量也存在线程安全问题。我们通过分析知道头插法会导致链表结点元素倒序即从A B C变为C B A这就出现了大问题。在多线程环境下如果一个线程完成了扩容Entry[ ] table会引用新数组Entry[ ] newTable由于链表结点引用指向发生了倒序那么另一个线程就会产生死链在遍历中产生死链会陷入死循环。
// 假设扩容前当前遍历的链表为 A B C
// 分析t1线程发生死链的情况有两个线程 t1 和 t2都在执行扩容操作while(null ! e) {// t2线程未扩容成功时t1线程执行当 e Be.next一定为 CEntryK,V next e.next;// t1线程发生上下文切换此时t2线程先完成了扩容// 由于链表倒序为C B A当 e B时e.next的引用变为了 A next还是引用 Cif (rehash) {e.hash null e.key ? 0 : hash(e.key);}int i indexFor(e.hash, newCapacity);// B结点指向头结点C,即 B c B发生死链e.next newTable[i];// B结点变为头结点newTable[i] e;// 继续遍历下一个节点变为C,由于死链会变为死循环e next;
} JDK8的HashMap为什么引入了红黑树的数据结构 红黑树是一种自平衡二叉搜索树并不是完全平衡的二叉树。完全平衡二叉树需要自旋多次才能达到平衡而红黑树不需要多次自旋同样有很好的查询性能缺点是引入了结点颜色维护变得更加复杂。《算法导论》中对于红黑树的定义①每个结点不是红结点就是黑结点 ②根结点是黑色的 ③每个叶子节点NIL都是黑的④如果一个节点是红的那么它的两个儿子都是黑的⑤对于任意一个结点其到叶子节点NIL的所有路径上的黑结点数都是相等的。HashMap中使用红黑树的目的是为了提升查询效率因为链表过长会导致查询效率变低。HashMap中的链表会在数组容量大于64和链表长度大于8时转换为红黑树同时红黑树也会在结点数小于等于6时退化为链表。
