注:源码系列文章主要是对某付费专栏的总结记录。如有侵权,请联系删除。
Map 在面试中,占据了很大一部分的面试题,其中以 HashMap 为主,这些面试题目有的可以说清楚,有的很难说清楚,如果是面对面面试的话,建议画一画。
答:HashMap 底层是 数组 + 链表 + 红黑树
的数据结构,数组的作用主要是方便快速查找,时间复杂度是 O(1),默认大小是 16,数组的下标索引是通过 Key 的 hash 计算出来的(index = (tab.length - 1) & hash
),数组元素叫做 Node,当多个 key 的 hashcode 一致,但 key 值不同时,就叫做(hash 碰撞冲突),单个 Node 就会转化成链表,链表的查询复杂度是 O(n),当链表的长度大于等于 8 并且数组大小(tab.length)超过 64 时,链表就会转化成红黑树,红黑树的查询复杂度是 O(log(n)),简单来说,最坏的查询次数相当于红黑树的最大深度。
答:
相同点:
ConcurrentModificationException
错误。不同点:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// index = (tab.length - 1) & hash
以上代码是 HashMap 的 hash 算法。
这其实是个数学问题,源码中就是通过以上代码来计算 hash 的,首先计算出 key 的 hashcode,因为 key 是 Object,所以会根据 key 的不同类型进行 hashcode 的计算,接着计算 h ^ (h >>> 16)
,这么做的好处是使大多数场景下,算出来的 hash 值比较分散。
一般来说,hash 值算出来之后,要计算当前 key 在数组中的索引下标位置,可以采用取模的方式,就是:索引下标位置 = hash 值 % 数组大小
,这样做的好处,就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上,但取模操作对于处理器的计算是比较慢的,数学上有个公式,当 b 是 2 的幂次方时
, a & b = a & (b - 1)
,所以此处索引位置的计算公式我们可以更改为:(n - 1) & hash
。
此问题可以延伸出三个小问题:
答:如果 key 是数字,直接用 key % 数组大小是没有问题的,但我们的 key 还有可能是字符串,是复杂对象,这时候用 字符串或复杂对象 % 数组大小是不行的,所以需要先计算出 key 的 hash 值。
答:hash 算法是 h ^ (h >>> 16)
,为了使计算出的 hash 值更分散,所以选择先将 h 无符号右移 16 位,然后再与 h 异或,就能达到 h 的高 16 位和低 16 位都能参与计算,减少了碰撞的可能性。
答:key.hashCode() 算出来的 hash 值还不是数组的索引下标,为了随机的计算出索引的下标位置,我们还会用 hash 值和数组大小进行取模,这样子计算出来的索引下标比较均匀分布。
取模操处理器计算比较慢,处理器对 & 操作就比较擅长,换成了 & 操作,是有数学证明的支撑,提高了处理器处理的速度。
答:因为只有大小是 2 的幂次方时,才能使 hash 值 % n(tab.length) == (n - 1) & hash 公式成立。
答:
网上列举的一些其它方法,尽量不要说,因为这些方法资料很少,实战用过的人更少,如果你没有深入研究的话,面试官让你深入描述一下很难说清楚,反而留下了不好的印象,说说 HashMap 现有的措施就足够了。
答:
扩容的时机:
resize() 中的 newCap = oldCap << 1
。(ArrayList 扩容为 1.5 倍(newCapacity = oldCapacity + (oldCapacity >> 1)
))扩容的门阀值是 threshold
,每次扩容时 threshold
都会被重新计算,门阀值等于 数组大小 * 影响因子(0.75)
。
新数组初始化之后,需要将老数组的值拷贝到新数组上,链表和红黑树都有自己的拷贝方法。
答:hash 冲突指定是 key 值的 hashcode 计算相同,但 key 值不同的情况。
如果桶中的元素原本只有一个或已经是链表了,新增元素直接追加到链表尾部;
如果桶中元素已经是链表,并且链表个数大于等于 8 时,此时有两种情况:
这里不仅仅判断了链表元素个数大于等于 8,还判断了数组大小,数组容量小于 64 没有立即转化的原因,猜测主要是因为红黑树占用的空间比链表大很多,转化也比较耗时,所以数组容量小的情况下冲突严重,我们可以先尝试扩容,看看能否通过扩容来解决冲突的问题。
答:当链表元素个数太多时,遍历可能比较耗时,转化成红黑树,可以使遍历的时间复杂度降低。但转化成红黑树,有空间和转化耗时的成本,我们通过 泊松分布公式
计算,正常情况下,链表个数出现 8 的几率不到千万分之一,所以说正常情况下,链表都不会转化成红黑树,这样设计的目的是为了防止非正常情况下,比如 hash 算法出问题时,导致链表元素个数轻易大于等于 8 时,仍然能够快速遍历。
延伸问题:红黑树什么时候转化成链表?
答:当节点的个数小于等于 6 时,红黑树会自动转化为链表,主要还是考虑红黑树的空间成本问题,当节点个数小于等于 6 时,遍历链表也很快,所以红黑树会重新变成链表。
答:如果数组有了 key,但不想覆盖 value,可以选择 putIfAbsent
方法,这个方法有给内置变量 onlyIfAbsent,内置是 true,就不会覆盖,我们平时使用的 put 方法,内置 onlyIfAbsent 为 false,是允许覆盖的。
取值时,如果为空,想返回默认值,可以使用 getOrDefault
方法,方法第一参数为 key,第二参数为你想返回的默认值,如 map.get(“10”, “3”),当 map 中没有 key 为 10 的值时,会返回默认值 3,而不是为空。
HashMap<String,String > map = Maps.newHashMap();
map.put("1","1");
map.put("2","2");
map.forEach((s, s2) -> map.remove("1"));
答:不行,会报 ConcurrentModificationException,如下:
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
发现 HashMap 重写了 Map 的 forEach 方法,会判断 modCount。建议使用迭代器的方式进行珊瑚,原理同 ArrayList 迭代器类似。
答:可以详细描述下源码的实现路径,说不清楚的话,可以画一画。
答:DTO 就是一个数据载体,可以看做拥有很多属性的 Java 类,我们可以对这些属性进行 get、set 操作。
看是什么类型的 Map。如果是 HashMap 的话,一定要覆写 equals 和 hashCode 方法,因为在 get、put 的时候,需要通过 equals 方法进行相等的判断;如果是 TreeMap 的话,DTO 需要实现 Comparable 接口,因为 TreeMap 会使用 Comparable 接口进行判断 key 的大小;如果是 LinkedHashMap 的话,和 HashMap 一样。
答:LRU,英文全称:Least recently used,中文叫做最近最少访问,在 LinkedHashMap 中,也叫做最少访问删除策略,我们可以通过 removeEldestEntry
方法设定一定的删除策略,使最少被访问的元素,在适当的时机被删除,原理是在 put 方法执行的最后,LinkedHashMap 会去检查这种策略,如果满足策略,就删除头节点。LinkedHashMap 覆写了 HashMap 的 afterNodeInsertion
方法。
保证头节点就是最少访问元素的原理是:LinkedHashMap 在 get 的时候,就会把当前访问的节点,移动到链表的尾部,慢慢的,就会使头部的节点成为最少被访问的元素。
答:因为 TreeMap 的底层就是通过排序来比较两个 key 的大小的,所以推荐 key 实现 Comparable 接口,是为了让 key 的排序往你希望的排序顺序上发展,而 String 本身已经实现了 Comparable 接口,所以使用 String 时,我们不需要额外的工作,不仅仅是 String,其它包装类型也都实现了 Comparable 接口,如 Long、Double、Float 等等。
Map 的面试题主要是 HashMap 为主,会问很多源码方面的问题,TreeMap 和 LinkedHashMap 主要以功能和场景为主,作为加分项。
Map 的面试题很多,但只要弄懂原理,题目再多变化,回答起来都会比较简单。
------------------------------------- END -------------------------------------
文章浏览阅读413次。编辑距离用于计算序列之间编辑距离和对齐的python模块。我需要一种方法来计算python中序列之间的编辑距离。我没有能够找到任何合适的库来实现这一点,所以我自己编写了一个。在那里似乎有许多可用于计算编辑的编辑距离库两个字符串之间的距离,但不是两个序列之间的距离。这完全是用python编写的。这种实现可能是在python中优化为更快。如果在C中实现。库API是根据difflib.sequencem..._edit distance python lib
文章浏览阅读3.8k次,点赞2次,收藏15次。antd 的upload组件是点开对话框后,按下确实就会上传,而且如果多选文件也会反复调用后端接口来完成上传。因为项目需要,所以要实现手动上传,和一次性上传多个文件(调用一次后端接口)在实现这个功能时,我翻阅了很多博客,可能是因为版本原因,很多代码都无用,最后还是通过翻阅官方文档,才最终实现。..._antd upload
文章浏览阅读246次。注意 第一步在一个文件下打开终端然后 sqlite3 student.db(创建一个数据库),然后再create stu。callback 回调函数 (只有sql为查询语句的时候,才会执行此语句)6--删除一列(sqlite3 不支持) 用下面方法。功能 :打开sqlite 数据库。功能 :关闭sqlite 数据库。基本sql命令,不以 . 夹头,db:指向sqlite句柄的指针。将新表的名字改为原来表的名字。sqlite3的基本命令。功能:执行一条sql语句。以 . 开头的命令。_sqlite 部署
文章浏览阅读1.4w次。前言canal-server同步到kafka本身是支持Kerberos方式的鉴权的,但是鉴于项目现在使用的kafka集群使用的是SASL/PLAIN的鉴权方式,所以需要对canal-server同步kafka做一下适配改造。准备kafka SASL/PLAIN鉴权的搭建我参考的这篇文章kafka SASL/PLAIN鉴权的搭建了解如何使用java向以SASL/PLAIN方式鉴权的kafk..._canal adapter kafka sasl
文章浏览阅读711次。adb(调试桥):debug工具。adb作用:借助adb工具,可以管理设备或手机模拟器状态。adb相关操作命令如下: 1. 显示系统中全部Android平台: android list targets2. 显示系统中全部AVD(模拟器): android list avd3. 创建AVD(模拟器): android create avd_android的shell命令工具:设备规范管理
文章浏览阅读769次,点赞10次,收藏7次。Centos 7.9 在线安装 VirtualBox 7.0_centos安装virtualbox
文章浏览阅读1.4w次,点赞9次,收藏10次。Autodesk卸载工具是一个专门用于Autodesk软件的卸载工具,可以自动识别电脑中的所有Autodesk软件,只需一键点击就能将Autodesk的软件完美卸载,并且不保留任何痕迹,这款卸载工具就可以帮助用户全面卸载Autodesk软件。_autodesk官方卸载工具
文章浏览阅读4.9k次。1.配置书写错误:配置文件value值引号内不能有空格,属性文件配置信息末尾不能有空格(1)打开属性文件中com.mysql.jdbc.Driver后发现多了一个空格(如下我标出了),所以写属性文件时一定别多输入多余的空格了。 jdbc.driverClassName=com.mysql.jdbc.Driver(此处有空格)(2)配置文件中的value值的" "号中前面或..._cannot find class: com.mysql.jdbc.driver
文章浏览阅读1.8k次。软件常用术语,免得你面对各种设计模式头发晕_软件术语
文章浏览阅读2.8k次。2017-08-02@erixhao 技术极客TechBoosterAI 机器学习第二篇 - 非线形回归分析。我们上文深入本质了解了机器学习基础线性回归算法后,本文继续研究非线性回归。非线性回归在机器学习中并非热点,并且较为小众,且其应用范畴也不如其他广。鉴于此,我们本文也将较为简单的介绍,并不会深入展开。非线性回归之后,我们会继续经典机器学习算法包括决策_非线性回归分析方法
文章浏览阅读164次。一、关系运算:1.等值比较: =语法:A=B操作类型:所有基本类型描述:如果表达式A与表达式B相等,则为TRUE;否则为FALSE举例:hive>select 1 from lxw_dual where 1=1;12.不等值比较: <>语法: A <> B操作类型:所有基本类型描述:如果表达式A为NULL,或者表..._josn mincol
文章浏览阅读767次。1 FI/SD 借口配置FI/SD通过tcode VKOA为billing设置过帐科目,用户可以创建自己的科目定义数据表。 科目是做到COA级的,通过KOFI/KOFK这两个condition type确定分别过帐到FI和CO凭证中。 由于PricingProc.是同Sale_sd 和fi 接口产生什么凭证?