Java岗大厂面试百日冲刺 - 日积月累,每日三题【Day12,zookeeper原理作用

Alibaba_开源 2021-11-25 17:49:34
java 面试 大厂 冲刺 百日

//LinkedHashMap的节点类

static class Entry<K,V> extends HashMap.Node<K,V> {

Entry<K,V> before, after;

Entry(int hash, K key, V value, Node<K,V> next) {

super(hash, key, value, next);

}

}

示例代码:

public static void main(String[] args) {

Map<String, String> linkedMap = new LinkedHashMap<String, String>();

linkedMap.put(“1”, “占便宜”);

linkedMap.put(“2”, “没够儿”);

linkedMap.put(“3”, “吃亏”);

linkedMap.put(“4”, “难受”);

for(linkedMap.Entry<String,String> item: linkedMap.entrySet()){

System.out.println(item.getKey() + “:” + item.getValue());

}

}

输出结果:

1:占便宜

2:没够儿

3:吃亏

4:难受

追问2:那TreeMap怎么实现有序的?

TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序,内部是通过红黑树来实现。

  1. TreeMap实现了SortedMap接口,它是一个key有序的Map类。

  2. 要么key所属的类实现Comparable接口,或者自定义一个实现了Comparator接口的比较器,传给TreeMap用于key的比较。

TreeMap<String, String> map = new TreeMap<String, String>(new Comparator() {

@Override

public int compare(String o1, String o2) {

return o2.compareTo(o1);

}

});


追问3:put方法原理是怎么实现的?

该条问答摘自 安琪拉的博客(https://blog.csdn.net/zhengwangzw/article/details/104889549)

在这里插入图片描述

  1. 判断数组是否为空,为空进行初始化;

  2. 不为空,计算 k 的 hash 值,通过(n - 1) & hash计算应当存放在数组中的下标 index;

  3. 查看 table[index] 是否存在数据,没有数据就构造一个Node节点存放在 table[index] 中;

  4. 存在数据,说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等,相等,用新的value替换原数据(onlyIfAbsent为false)

  5. 如果不相等,判断当前节点类型是不是树型节点,如果是树型节点,创造树型节点插入红黑树中;(如果当前节点是树型节点证明当前已经是红黑树了)

  6. 如果不是树型节点,创建普通Node加入链表中;判断链表长度是否大于 8并且数组长度大于64, 大于的话链表转换为红黑树;

  7. 插入完成之后判断当前节点数是否大于阈值,如果大于开始扩容为原数组的二倍。


下面我们看看源码中的内容:

/**

  • 将指定参数key和指定参数value插入map中,如果key已经存在,那就替换key对应的value

  • @param key 指定key

  • @param value 指定value

  • @return 如果value被替换,则返回旧的value,否则返回null。当然,可能key对应的value就是null。

*/

public V put(K key, V value) {

//putVal方法的实现就在下面

return putVal(hash(key), key, value, false, true);

}

从源码中可以看到,put(K key, V value)可以分为三个步骤:

  1. 通过hash(Object key)方法计算key的哈希值。

  2. 通过putVal(hash(key), key, value, false, true)方法实现功能。

  3. 返回putVal方法返回的结果。

那么看看putVal方法的源码是如何实现的?

/**

  • Map.put和其他相关方法的实现需要的方法

  • @param hash 指定参数key的哈希值

  • @param key 指定参数key

  • @param value 指定参数value

  • @param onlyIfAbsent 如果为true,即使指定参数key在map中已经存在,也不会替换value

  • @param evict 如果为false,数组table在创建模式中

  • @return 如果value被替换,则返回旧的value,否则返回null。当然,可能key对应的value就是null。

*/

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

//如果哈希表为空,调用resize()创建一个哈希表,并用变量n记录哈希表长度

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

//如果指定参数hash在表中没有对应的桶,即为没有碰撞

if ((p = tab[i = (n - 1) & hash]) == null)

//直接将键值对插入到map中即可

tab[i] = newNode(hash, key, value, null);

else {

Node<K,V> e; K k;

//如果碰撞了,且桶中的第一个节点就匹配了

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

//将桶中的第一个节点记录起来

e = p;

//如果桶中的第一个节点没有匹配上,且桶内为红黑树结构,则调用红黑树对应的方法插入键值对

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

//不是红黑树结构,那么就肯定是链式结构

else {

//遍历链式结构

for (int binCount = 0

《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

; ; ++binCount) {

//如果到了链表尾部

if ((e = p.next) == null) {

//在链表尾部插入键值对

p.next = newNode(hash, key, value, null);

//如果链的长度大于TREEIFY_THRESHOLD这个临界值,则把链变为红黑树

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

//跳出循环

break;

}

//如果找到了重复的key,判断链表中结点的key值与插入的元素的key值是否相等,如果相等,跳出循环

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

//用于遍历桶中的链表,与前面的e = p.next组合,可以遍历链表

p = e;

}

}

//如果key映射的节点不为null

if (e != null) { // existing mapping for key

//记录节点的vlaue

V oldValue = e.value;

//如果onlyIfAbsent为false,或者oldValue为null

if (!onlyIfAbsent || oldValue == null)

//替换value

e.value = value;

//访问后回调

afterNodeAccess(e);

//返回节点的旧值

return oldValue;

}

}

//结构型修改次数+1

++modCount;

//判断是否需要扩容

if (++size > threshold)

resize();

//插入后回调

afterNodeInsertion(evict);

return null;

}

追问4:HashMap扩容机制原理

  • capacity 即容量,默认16。
  • loadFactor 加载因子,默认是0.75
  • threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。
  • 一般情况下,当元素数量超过阈值时便会触发扩容(调用resize()方法)。

  • 每次扩容的容量都是之前容量的2倍。

  • 扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。

这里我们以JDK1.8的扩容为例:

HashMap的容量变化通常存在以下几种情况:

  1. 空参数的构造函数:实例化的HashMap默认内部数组是null,即没有实例化。第一次调用put方法时,则会开始第一次初始化扩容,长度为16

  2. 有参构造函数:用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数,将这个数设置赋值给阈值(threshold)。第一次调用put方法时,会将阈值赋值给容量,然后让 阈值 = 容量 x 加载因子 。(因此并不是我们手动指定了容量就一定不会触发扩容,超过阈值后一样会扩容!!)

  3. 如果不是第一次扩容,则容量变为原来的2倍,阈值也变为原来的2倍。(容量和阈值都变为原来的2倍时,加载因子0.75不变)

此外还有几个点需要注意:

  • 首次put时,先会触发扩容(算是初始化),然后存入数据,然后判断是否需要扩容;可见首次扩容可能会调用两次resize()方法

  • 不是首次put,则不再初始化,直接存入数据,然后判断是否需要扩容;

扩容时,要扩大空间,为了使hash散列均匀分布,原有部分元素的位置会发生移位。

JDK7的元素迁移

JDK7中,HashMap的内部数据保存的都是链表。因此逻辑相对简单:在准备好新的数组后,map会遍历数组的每个“桶”,然后遍历桶中的每个Entity,重新计算其hash值(也有可能不计算),找到新数组中的对应位置,以头插法插入新的链表。

  • 这里有几个注意点:

是否要重新计算hash值的条件这里不深入讨论,读者可自行查阅源码。

因为是头插法,因此新旧链表的元素位置会发生转置现象。

元素迁移的过程中在多线程情境下有可能会触发死循环(无限进行链表反转)。

JDK1.8的元素迁移

JDK1.8则因为巧妙的设计,性能有了大大的提升:由于数组的容量是以2的幂次方扩容的,那么一个Entity在扩容时,新的位置要么在原位置,要么在原长度+原位置的位置。原因如下图:

在这里插入图片描述

数组长度变为原来的2倍,表现在二进制上就是多了一个高位参与数组下标确定。此时,一个元素通过hash转换坐标的方法计算后,恰好出现一个现象:最高位是0则坐标不变,最高位是1则坐标变为“10000+原坐标”,即“原长度+原坐标”。如下图:

在这里插入图片描述

因此,在扩容时,不需要重新计算元素的hash了,只需要判断最高位是1还是0就好了。

JDK8的HashMap还有以下细节需要注意:

  • JDK8在迁移元素时是正序的,不会出现链表转置的发生。

  • 如果某个桶内的元素超过8个,则会将链表转化成红黑树,加快数据查询效率。

追问5:HashMap在JDK1.8都做了哪些优化?

| 不同点 | JDK 1.7 | JDK 1.8 |

| — | — | — |

| 存储结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |

| 初始化方式 | 单独函数:inflateTable() | 直接集成到了扩容函数resize()中 |

| hash值计算方式 | 扰动处理 = 9次扰动 = 4次位运算 + 5次异或运算 | 扰动处理 = 2次扰动 = 1次位运算 + 1次异或运算 |

| 存放数据的规则 | 无冲突时,存放数组;冲突时,存放链表 | 无冲突时,存放数组;冲突 & 链表长度 < 8:存放单链表;冲突 & 链表长度 > 8:树化并存放红黑树 |

| 插入数据方式 | 头插法(先讲原位置的数据移到后1位,再插入数据到该位置) | 尾插法(直接插入到链表尾部/红黑树) |

| 扩容后存储位置的计算方式 | 全部按照原来方法进行计算(即hashCode ->> 扰动函数 ->> (h&length-1)) | 按照扩容后的规律计算(即扩容后的位置=原位置 or 原位置 + 旧容量) |

  1. 数组+链表改成了数组+链表或红黑树

防止发生hash冲突,链表长度过长,将时间复杂度由O(n)降为O(logn);

  1. 链表的插入方式从头插法改成了尾插法,简单说就是插入时,如果数组位置上已经有元素,1.7将新元素放到数组中,新节点插入到链表头部,原始节点后移;而JDK1.8会遍历链表,将元素放置到链表的最后;

因为1.7头插法扩容时,头插法可能会导致链表发生反转,多线程环境下会产生环(死循环);

在这里插入图片描述

这个过程为,先将A复制到新的hash表中,然后接着复制B到链头(A的前边:B.next=A),本来B.next=null,到此也就结束了(跟线程二一样的过程),但是,由于线程二扩容的原因,将B.next=A,所以,这里继续复制A,让A.next=B,由此,环形链表出现:B.next=A; A.next=B

使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。

就是说原本是A->B,在扩容后那个链表还是A->B。

  1. 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置,1.8采用更简单的判断逻辑,位置不变或索引+旧容量大小;

  2. 在插入时,1.7先判断是否需要扩容,再插入,1.8先进行插入,插入完成再判断是否需要扩容;

追问6:链表红黑树如何互相转换?阈值多少?

  • **链表转红黑树的阈值为:8 **

  • **红黑树转链表的阈值为:6 **

经过计算,在hash函数设计合理的情况下,发生hash碰撞8次的几率为百万分之6,从概率上讲,阈值为8足够用;至于为什么红黑树转回来链表的条件阈值是6而不是7或9?因为如果hash碰撞次数在8附近徘徊,可能会频繁发生链表和红黑树的互相转化操作,为了预防这种情况的发生。


在这里插入图片描述

课间休息,又来秀一下来自咱们群里同学的搬砖工地,坐标:北京

作者:Qnlko

同是漂子,祝好~


面试题2:HashMap是线程安全的吗?

===================================================================================

正经回答:


不是线程安全的,在多线程环境下,

  • JDK1.7:会产生死循环、数据丢失、数据覆盖的问题;

  • JDK1.8:中会有数据覆盖的问题。

版权声明
本文为[Alibaba_开源]所创,转载请带上原文链接,感谢
https://blog.csdn.net/m0_63174811/article/details/121542477

  1. La distribution Linux d'Amazon est maintenant entièrement basée sur Fedora
  2. org.springframework.web.bind.MissingServletRequestParameterException
  3. Built in constraints and functions of MySQL Foundation (2)
  4. Basic operation of MySQL Foundation (I)
  5. Introduction to Java zero foundation 3: Java data types
  6. 从零开始搭建EasyDarwin环境——Linux系统开发环境搭建Golang
  7. Redis source Concise Analysis 02 - SDS String
  8. Construire l'environnement easydarwin à partir de zéro - - construire l'environnement de développement du système Linux golang
  9. javaweb代码是正确的,但是第一行代码就报错了
  10. **** | Java | 后端开挂:3行代码写出8个接口
  11. Java || 看了大二学长写的代码,我竟开始默默的模仿了。。。
  12. Java | 手把手教你实现一个抽奖系统(Java版)
  13. Java | Manuel pour vous apprendre à mettre en œuvre un système de loterie (version Java)
  14. Java | | après avoir lu le Code que j'ai écrit en deuxième année, j'ai commencé à imiter silencieusement...
  15. Java | back - end Pending: 3 - line Code write 8 Interfaces
  16. Le Code Web Java est correct, mais la première ligne de code est incorrecte
  17. Android网络编程之Http通信
  18. Android網絡編程之Http通信
  19. Http communication for Android Network Programming
  20. 数据结构实验八 领会图的两种主要储存结构和图的基本运算算法设计
  21. Hibernate数据校验简介
  22. The story of spring
  23. Il a dépensé 270 000 yuans pour soulever Xiaopeng p7 et a parcouru 3 627 km. Le propriétaire du véhicule a partagé 6 avantages et inconvénients.
  24. 阿里蚂蚁花呗团队面试题:spring+分布式+jvm+session+redis
  25. 【Java入门100例】14.字符串排序——compareTo()
  26. 【Java入门100例】13.修改文件扩展名——字符串替换
  27. Leetcode 79. Word Search [C + + / java detailed problem]
  28. Introduction à la vérification des données hibernantes
  29. Expérience de la structure des données
  30. Spring cloud gateway practice 2: more routing configuration methods
  31. Java network programming - summary overview
  32. 基于语法树的 Java 代码自动化插桩
  33. 云原生 Spring Boot 应用配置 Prometheus + Grafana 监控(保姆级)
  34. Spring cloud gateway practice 2: more routing configuration methods
  35. Jenkins file one line of code to deploy. Net program to k8s
  36. Java network programming - summary overview
  37. Cloud Native Spring Boot application configuration Prometheus + grafana Monitoring (baby - sitter)
  38. Insertion automatique de code Java basée sur l'Arbre syntaxique
  39. Le SUV phare de Xiaopeng, Xiaopeng G9, a fait ses débuts au salon de l'automobile et s'est tenu en position C dans la nouvelle force?
  40. Docker 从入门到实践系列四 - Docker 容器编排利器 Docker Compose
  41. 6年老猿带你掌握Spring Boot实现定时任务的动态增删启停
  42. disruptor笔记之六:常见场景,java教程从入门到精通pdf百度云
  43. Pourquoi InnoDB n'utilise - t - il pas un cache LRU naïf?
  44. Java Reflection (2): quelques opérations de base de reflection
  45. 6年老猿帶你掌握Spring Boot實現定時任務的動態增删啟停
  46. Les singes âgés vous permettent de maîtriser le démarrage et l'arrêt dynamiques des tâches programmées par Spring boot
  47. Docker From Beginning to Practice Series IV - docker Container chorégraphe Clean docker Composition
  48. 编写 java 程序,为家用电脑 ipv6 自动更新 goddy dns 记录(ddns)
  49. java jvm-old gc耗时几十s,导致系统告警
  50. Disruptor note 6: scénario commun, tutoriel Java de l'introduction à la maîtrise du PDF Baidu Cloud
  51. 编写Java程序启动脚本最佳实践
  52. How to get the correct Linux user's documents, music videos and other directories?
  53. Java JVM Old GC prend des dizaines de s, ce qui provoque une alarme système
  54. Écrivez un programme Java pour mettre à jour automatiquement les enregistrements DNS goddy (ddns) pour l'ordinateur domestique IPv6
  55. 編寫Java程序啟動脚本最佳實踐
  56. Meilleures pratiques pour écrire des scripts de démarrage de programmes Java
  57. Notes sur springcloud Eureka
  58. Ajout, suppression et modification simples de mybatis
  59. Java - carte mémoire de l'objet
  60. Why did docker lose to kubernetes? Docker employee readme!