济南做网站比较好的公司,做网站要的图片斗鱼,南通网站定制企业,电子书网站建设系列博客目录 文章目录 系列博客目录4. HashMap相关面试题4.4 面试题-HashMap的put方法的具体流程 频54.4.1 hashMap常见属性4.4.2 源码分析 HashMap的构造函数面试文稿#xff1a; 4.5 讲一讲HashMap的扩容机制 难3频4面试文稿#xff1a; 4.6 面试题-hashMap的寻址算法 难4…系列博客目录 文章目录 系列博客目录4. HashMap相关面试题4.4 面试题-HashMap的put方法的具体流程 频54.4.1 hashMap常见属性4.4.2 源码分析 HashMap的构造函数面试文稿 4.5 讲一讲HashMap的扩容机制 难3频4面试文稿 4.6 面试题-hashMap的寻址算法 难4频4面试文稿 4.7 面试题-hashmap在1.7情况下的多线程死循环问题 难4频3面试文稿 4. HashMap相关面试题
4.4 面试题-HashMap的put方法的具体流程 频5
4.4.1 hashMap常见属性 size是存储元素的个数。
注意这个table他是由hashMap的内部类Node组成的数组Node里面有哈希值(用来记录存储的位置、key和value还有next因为发生冲突的时候会用到链表以及红黑树。
4.4.2 源码分析 HashMap的构造函数
MapString, String map new HashMap();
map.put(name,itheima);按住Ctrl左键点进HashMap中
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted 默认加载因子 0.75
}上方代码说明了以下两点
HashMap是懒惰加载在创建对象时并没有初始化数组在无参的构造函数中设置了默认的加载因子是0.75
为了更好理解源码先看一下添加数据的流程图
第一次添加数据流程图(涉及到了初始化添加数据以及如果大于阈值调用resize())如下 以下是非第一次发现key存在时候的流程图 以下是发现key不存在的时候的流程图。 以下是针对上面流程图的JDK1.8的带注释的源码。
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//判断数组是否未初始化if ((tab table) null || (n tab.length) 0)//如果未初始化调用resize方法 进行初始化n (tab resize()).length;//通过 运算求出该数据key的数组下标并判断该下标位置是否有数据if ((p tab[i (n - 1) hash]) null)//如果没有直接将数据放在该下标位置tab[i] newNode(hash, key, value, null);//该数组下标有数据的情况else {NodeK,V e; K k;//判断该位置数据的key和新来的数据是否一样if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))//如果一样证明为修改操作该节点的数据赋值给e,后边会用到e p;//判断是不是红黑树else if (p instanceof TreeNode)//如果是红黑树的话进行红黑树的操作e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);//新数据和当前数组既不相同也不是红黑树节点证明是链表else {//遍历链表for (int binCount 0; ; binCount) {//判断next节点如果为空的话证明遍历到链表尾部了if ((e p.next) null) {//把新值放入链表尾部p.next newNode(hash, key, value, null);//因为新插入了一条数据所以判断链表长度是不是大于等于8if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是进行转换红黑树操作treeifyBin(tab, hash);break;}//判断链表当中有数据相同的值如果一样证明为修改操作if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;//把下一个节点赋值为当前节点p e;}}//判断e是否为空e值为修改操作存放原数据的变量if (e ! null) { // existing mapping for key//不为空的话证明是修改操作取出老值V oldValue e.value;//一定会执行 onlyIfAbsent传进来的是falseif (!onlyIfAbsent || oldValue null)//将新值赋值当前节点e.value value;afterNodeAccess(e);//返回老值return oldValue;}}//计数器计算当前节点的修改次数modCount;//当前数组中的数据数量如果大于扩容阈值 16* 0.75 12if (size threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//添加操作时 返回空值return null;
}面试文稿
判断键值对数组table是否为空或为null否则执行resize()进行扩容初始化根据键值key计算hash值得到数组索引判断table[i]null条件成立直接新建节点添加如果table[i]null ,不成立 4.1 判断table[i]的首个元素是否和key一样如果相同直接覆盖value 4.2 判断table[i] 是否为treeNode即table[i] 是否是红黑树如果是红黑树则直接在树中插入键值对 4.3 遍历table[i]链表的尾部插入数据然后判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操 作遍历过程中若发现key已经存在直接覆盖value插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold数组长度*0.75如果超过进行扩容。
4.5 讲一讲HashMap的扩容机制 难3频4
扩容的流程
第一次初始化数组的流程如下 第一次存储数量大于12时流程如下
//扩容、初始化数组
final NodeK,V[] resize() {NodeK,V[] oldTab table;//如果当前数组为null的时候把oldCap老数组容量设置为0int oldCap (oldTab null) ? 0 : oldTab.length;//老的扩容阈值int oldThr threshold;int newCap, newThr 0;//判断数组容量是否大于0大于0说明数组已经初始化if (oldCap 0) {//判断当前数组长度是否大于最大数组长度if (oldCap MAXIMUM_CAPACITY) {//如果是将扩容阈值直接设置为int类型的最大数值并直接返回threshold Integer.MAX_VALUE;return oldTab;}//如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap2//运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)
* newThr oldThr 1; // double threshold 等价于oldThr*2}//如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;//数组未初始化的情况将阈值和扩容因子都设置为默认值else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的时候扩容阈值是没有赋值的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})//根据上边计算得出的容量 创建新的数组 NodeK,V[] newTab (NodeK,V[])new Node[newCap];//赋值table newTab;//扩容操作判断不为空证明不是初始化数组if (oldTab ! null) {//遍历数组for (int j 0; j oldCap; j) {NodeK,V e;//判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作if ((e oldTab[j]) ! null) {//将数组位置置空oldTab[j] null;//判断是否有下个节点if (e.next null)//如果没有就重新计算在新数组中的下标并放进去newTab[e.hash (newCap - 1)] e;//有下个节点的情况并且判断是否已经树化else if (e instanceof TreeNode)//进行红黑树的操作((TreeNodeK,V)e).split(this, newTab, j, oldCap);//有下个节点的情况并且没有树化链表形式else {//比如老数组容量是16那下标就为0-15//扩容操作*2容量就变为32下标为0-31//低位0-15高位16-31//定义了四个变量// 低位头 低位尾NodeK,V loHead null, loTail null;// 高位头 高位尾NodeK,V hiHead null, hiTail null;//下个节点NodeK,V next;//循环遍历do {//取出next节点next e.next;//通过 与操作 计算得出结果为0if ((e.hash oldCap) 0) {//如果低位尾为null证明当前数组位置为空没有任何数据if (loTail null)//将e值放入低位头loHead e;//低位尾不为null证明已经有数据了else//将数据放入next节点loTail.next e;//记录低位尾数据loTail e;}//通过 与操作 计算得出结果不为0else {//如果高位尾为null证明当前数组位置为空没有任何数据if (hiTail null)//将e值放入高位头hiHead e;//高位尾不为null证明已经有数据了else//将数据放入next节点hiTail.next e;//记录高位尾数据hiTail e;}}//如果e不为空证明没有到链表尾部继续执行循环while ((e next) ! null);//低位尾如果记录的有数据是链表if (loTail ! null) {//将下一个元素置空loTail.next null;//将低位头放入新数组的原下标位置newTab[j] loHead;}//高位尾如果记录的有数据是链表if (hiTail ! null) {//将下一个元素置空hiTail.next null;//将高位头放入新数组的(原下标原数组容量)位置newTab[j oldCap] hiHead;}}}}}//返回新的数组对象return newTab;}面试文稿
在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次每次扩容都是达到了扩容阈值数组长度 * 0.75每次扩容的时候都是扩容之前容量的2倍扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中 没有hash冲突的节点则直接使用 e.hash (newCap - 1) 计算新数组的索引位置如果是红黑树走红黑树的添加如果是链表则需要遍历链表可能需要拆分链表判断(e.hash oldCap)是否为0该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上
4.6 面试题-hashMap的寻址算法 难4频4
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}在putVal方法中有一个hash(key)方法这个方法就是来去计算key的hash值的看下面的代码
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}首先获取key的hashCode值然后右移16位 异或运算 原来的hashCode值主要作用就是使原来的hash值更加均匀减少hash冲突。
GPT:通常情况下hashCode 的低位信息可能有某些模式或偏向而高位的信息可能没有充分地分布到低位。为了避免这些模式导致哈希值不均匀HashMap 会对哈希值进行调整使得低位和高位信息更加混合从而避免过多元素落在哈希表的同一桶中。右移操作 (h 16) 将原始 hashCode 的高 16 位移到低 16 位。 然后使用 异或 (^) 操作将这两部分合并在一起。这是为了将 hashCode 的低位和高位信息都引入到哈希计算中。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
{。。。。。if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);。。。。(n-1)hash : 得到数组中的索引代替取模性能更好数组长度必须是2的n次幂
面试文稿
关于hash值的其他面试题为何HashMap的数组长度一定是2的次幂
计算索引时效率更高如果是 2 的 n 次幂可以使用位与运算代替取模扩容时重新计算索引效率更高 hash oldCap 0 的元素留在原来位置 否则新位置 旧位置 oldCap
4.7 面试题-hashmap在1.7情况下的多线程死循环问题 难4频3
jdk7的的数据结构是数组链表 在数组进行扩容的时候因为链表是头插法在进行数据迁移的过程中有可能导致死循环
变量e指向的是需要迁移的对象变量next指向的是下一个需要迁移的对象 (e迁移完毕后next把自己赋值给eJdk1.7中的链表采用的头插法在数据迁移的过程中并没有新的对象产生只是改变了对象的引用
产生死循环的过程 线程1和线程2的变量e和next都引用了这个两个节点。 线程2扩容后由于头插法链表顺序颠倒但是线程1的临时变量e和next还引用了这两个节点
第一次循环 由于线程2迁移的时候已经把B的next执行了A 第二次循环 第三次循环
面试文稿
参考回答 在jdk1.7的hashmap中在数组进行扩容的时候因为链表是头插法在进行数据迁移的过程中有可能导致死循环 比如说现在有两个线程 线程一读取到当前的hashmap数据数据中一个链表在准备扩容时线程二介入 线程二也读取hashmap直接进行扩容。因为是头插法链表的顺序会进行颠倒过来。比如原来的顺序是AB扩容后的顺序是BA线程二执行结束。 线程一继续执行的时候就会出现死循环的问题。 线程一先将A移入新的链表再将B插入到链头由于另外一个线程的原因B的next指向了A 所以B-A-B,形成循环。 当然JDK 8 将扩容算法做了调整不再将元素加入链表头而是保持与扩容前一样的顺序使用尾插法就避免了jdk7中死循环的问题。
