企业服务工作站,网页搜索优化,创办一个网站的费用,服装设计图片23Java面试专题 八股文面试全套真题#xff08;含大厂高频面试真题#xff09;多线程_软工菜鸡的博客-CSDN博客
常见集合篇-01-集合面试题-课程介绍 02-算法复杂度分析 2 List相关面试题
2.1 数组
2.1.1 数组概述
数组#xff08;Array#xff09;是一种用连续的内存空…23Java面试专题 八股文面试全套真题含大厂高频面试真题多线程_软工菜鸡的博客-CSDN博客
常见集合篇-01-集合面试题-课程介绍 02-算法复杂度分析 2 List相关面试题
2.1 数组
2.1.1 数组概述
数组Array是一种用连续的内存空间存储相同数据类型数据的线性数据结构。 int[] array {22,33,88,66,55,25};
我们定义了这么一个数组之后在内存的表示是这样的 现在假如我们通过arrar[1]想要获得下标为1这个元素但是现在栈内存中指向的堆内存数组的首地址它是如何获取下标为1这个数据的 2.1.2 寻址公式
为了方便大家理解我们把数组的内存地址稍微改了一下都改成了数字如下图
在数组在内存中查找元素的时候是有一个寻址公式的如下 arr指的是数组 i指的是数组的下标 有了寻址公式以后我们再来获取一下下标为1的元素这个是原来的数组 套入公式 array[1] 10 i * 4 14
获取到14这个地址就能获取到下标为1的这个元素了。 2.1.3 操作数组的时间复杂度
1.随机查询(根据索引查询)
数组元素的访问是通过下标来访问的计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素 public int test01(int[] a,int i){return a[i];// a[i] baseAddress i \* dataSize
}
代码的执行次数并不会随着数组的数据规模大小变化而变化是常数级的所以查询数据操作的时间复杂度是O(1) 2. 未知索引查询O(n)或O(log2n)
情况一查找数组内的元素查找55号数据遍历数组时间复杂度为O(n) 情况二查找排序后数组内的元素通过二分查找算法查找55号数据时间复杂度为O(logn) 3.插入O(n)
数组是一段连续的内存空间因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低。
假设数组的长度为 n现在如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来给新来的数据我们需要将第 kn 这部分的元素都顺序地往后挪一位。如下图所示 新增之后的数据变化如下 所以
插入操作最好情况下是O(1)的最坏情况下是O(n)的平均情况下的时间复杂度是O(n)。
4.删除O(n)
同理可得如果我们要删除第 k 个位置的数据为了内存的连续性也需要搬移数据不然中间就会出现空洞内存就不连续了时间复杂度仍然是O(n)。
2.2 ArrayList源码分析
分析ArrayList源码主要从三个方面去翻阅成员变量构造函数关键方法
以下 源码都来源于jdk1.8 2.2.1 成员变量 DEFAULT_CAPACITY 10; 默认初始的容量**(CAPACITY) EMPTY_ELEMENTDATA {}; 用于空实例的共享空数组实例 DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};用于默认大小的空实例的共享空数组实例 Object[] elementData; 存储元素的数组缓冲区 int size; ArrayList的大小它包含的元素数量 2.2.2 三个构造方法 第一个构造是带初始化容量的构造函数可以按照指定的容量初始化数组 第二个是无参构造函数默认创建一个空集合 将 collection对象转换成数组然后将数组的地址的赋给elementData 2.2.3 ArrayList源码分析
添加数据的流程 结论 底层数据结构
ArrayList底层是用动态的数组实现的 初始容量
ArrayList初始容量为0当第一次添加数据的时候才会初始化容量为10 扩容逻辑
ArrayList在进行扩容的时候是原来容量的1.5倍每次扩容都需要拷贝数组 添加逻辑 确保数组已使用长度size加1之后足够存下下一个数据 计算数组的容量如果当前数组已使用长度1后的大于当前的数组长度则调用grow方法扩容原来的1.5倍 确保新增的数据有地方存储之后则将新元素添加到位于size的位置上。 返回添加成功布尔值。
2.2.4 ArrayList底层的实现原理是什么-面试题
难易程度☆☆☆☆ 出现频率☆☆☆ 2.2.5 ArrayList listnew ArrayList(10)中的list扩容几次-面试题
难易程度☆☆☆ 出现频率☆☆ 参考回答
该语句只是声明和实例了一个 ArrayList指定了容量为 10未扩容
2.2.6 面试题-如何实现数组和List之间的转换
难易程度☆☆☆ 出现频率☆☆ 如下代码 参考回答 数组转List 使用JDK中java.util.Arrays工具类的asList方法 List转数组使用List的toArray方法。
无参toArray方法返回 Object数组传入初始化长度的数组对象返回该对象数组
面试官再问
1用Arrays.asList转List后如果修改了数组内容list受影响吗
2List用toArray转数组后如果修改了List内容数组受影响吗 数组转List受影响 List转数组不受影响 再答
1用Arrays.asList转List后如果修改了数组内容list受影响吗
Arrays.asList转换list之后如果修改了数组的内容list会受影响因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合在这个集合的构造器中把我们传入的这个集合进行了包装而已最终指向的都是同一个内存地址
2List用toArray转数组后如果修改了List内容数组受影响吗
list用了toArray转数组后如果修改了list内容数组不会影响当调用了toArray以后在底层是它是进行了数组的拷贝跟原来的元素就没啥关系了所以即使list修改了以后数组也不受影响
2.3 链表
2.3.1 单向链表 代码实现参考 2.3.2 单向链表时间复杂度分析
1查询操作 只有在查询头节点的时候不需要遍历链表时间复杂度是O(1) 查询其他结点需要遍历链表时间复杂度是O(n)
2插入和删除操作 只有在添加和删除头节点的时候不需要遍历链表时间复杂度是O(1) 添加或删除其他结点需要遍历链表找到对应节点后才能完成新增或删除节点时间复杂度是O(n)
2.3.3 双向链表
而双向链表顾名思义它支持两个方向 每个结点不止有一个后继指针 next 指向后面的结点 有一个前驱指针 prev 指向前面的结点
参考代码 对比单链表 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址 支持双向遍历这样也带来了双向链表操作的灵活性
2.3.4 双向链表时间复杂度分析 1查询操作 查询头尾结点的时间复杂度是O(1) 平均的查询时间复杂度是O(n) 给定节点找前驱节点的时间复杂度为O(1)
2增删操作 头尾结点增删的时间复杂度为O(1) 其他部分结点增删的时间复杂度是 O(n) 给定节点增删的时间复杂度为O(1)
2.3.5 面试题-ArrayList和LinkedList的区别是什么 底层数据结构 ArrayList 是动态数组的数据结构实现 LinkedList 是双向链表的数据结构实现 操作数据效率 ArrayList按照下标查询的时间复杂度O(1)【内存是连续的根据寻址公式】 LinkedList不支持下标查询 查找未知索引 ArrayList需要遍历链表也需要链表时间复杂度都是O(n) 新增和删除 ArrayList尾部插入和删除时间复杂度是O(1)其他部分增删需要挪动数组时间复杂度是O(n) LinkedList头尾节点增删时间复杂度是O(1)其他都需要遍历链表时间复杂度是O(n) 内存空间占用 ArrayList底层是数组内存连续节省内存 LinkedList 是双向链表需要存储数据和两个指针更占用内存 线程安全 ArrayList和LinkedList都不是线程安全的 如果需要保证线程安全有两种方案 在方法内使用局部变量每个线程都有一份局部变量则是线程安全的 使用线程安全的ArrayList和LinkedList 加锁性能下降 3 HashMap相关面试题 3.1 二叉树
3.1.1 二叉树概述
二叉树顾名思义每个节点最多有两个“叉”两个子节点分别是左/右子节点。不过二叉树并不要求每个节点都有两个子节点有的节点只有左/右子节点。
二叉树每个节点的左子树和右子树也分别满足二叉树的定义。 Java中有两个方式实现二叉树数组存储链式存储。
基于链式存储的树的节点可定义如下 3.1.2 二叉搜索树BST
在二叉树中比较常见的二叉树有 满二叉树 完全二叉树 二叉搜索树 红黑树
我们重点讲解二叉搜索树和红黑树
1二叉搜索树概述 2二叉搜索树-时间复杂度分析
实际上由于二叉查找树的形态各异时间复杂度也不尽相同我画了几棵树我们来看一下插入查找删除的时间复杂度 查找的时间复杂度O(logn)插入删除需要用到查找 所以也是O(logn)
极端情况下二叉搜索的时间复杂度 3.1.3 红黑树
1概述
红黑树Red Black Tree也是一种自平衡的二叉搜索树(BST)之前叫做平衡二叉B树Symmetric Binary B-Tree 2红黑树的特质 在添加或删除节点的时候如果不符合这些性质会发生旋转以达到所有的性质保证红黑树的平衡 3红黑树的复杂度 查找 红黑树也是一棵BST二叉搜索树树查找操作的时间复杂度为O(log n) 添加 添加先要从根节点开始找到元素添加的位置时间复杂度O(log n) 添加完成后涉及到复杂度为O(1)的旋转调整操作 故整体复杂度为O(log n) 删除 首先从根节点开始找到被删除元素的位置时间复杂度O(log n) 删除完成后涉及到复杂度为O(1)的旋转调整操作 故整体复杂度为O(log n)
3.2 散列表
在HashMap中的最重要的一个数据结构就是散列表在散列表中又使用到了红黑树和链表
3.2.1 散列表Hash Table概述
散列表(Hash Table)又名哈希表/Hash表是根据键Key直接访问在内存存储位置值Value的数据结构它是由数组演化而来的利用了数组支持按照下标进行随机访问数据的特性
举个例子
假设有100个人参加马拉松编号是1-100如果要编程实现根据选手的编号迅速找到选手信息
可以把选手信息存入数组中选手编号就是数组的下标数组的元素就是选手的信息。
当我们查询选手信息的时候只需要根据选手的编号到数组中查询对应的元素就可以快速找到选手的信息如下图 现在需求升级了 我们目前是把选手的信息存入到数组中不过选手的编号不能直接作为数组的下标不过可以把选手的选号进行转换转换为数值就可以继续作为数组的下标了
转换可以使用散列函数进行转换
3.2.2 散列函数和散列冲突
将键(key)映射为数组下标的函数叫做散列函数。可以表示为hashValue hash(key)
散列函数的基本要求 散列函数计算得到的散列值必须是≥0的正整数因为hashValue需要作为数组的下标。 如果key1key2那么经过hash后得到的哈希值也必相同即hash(key1) hash(key2 如果key1 ! key2那么经过hash后得到的哈希值也必不相同即hash(key1) ! hash(key2)
实际的情况下想找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的即便像著名的MD5,SHA等哈希算法也无法避免这一情况这就是散列冲突(或者哈希冲突哈希碰撞就是指多个key映射到同一个数组下标位置) 3.2.3 散列冲突-链表法拉链
在散列表中数组的每个下标位置我们可以称之为桶bucket或者槽slot每个桶(槽)会对应一条链表所有散列值相同的元素我们都放到相同槽位对应的链表中。 简单就是如果有多个key最终的hash值是一样的就会存入数组的同一个下标中下标中挂一个链表存入多个数据
3.2.4 时间复杂度-散列表
1插入操作通过散列函数计算出对应的散列槽位将其插入到对应链表中即可插入的时间复杂度是 O(1) 通过计算就可以找到元素 2当查找、删除一个元素时我们同样通过散列函数计算出对应的槽然后遍历链表查找或者删除 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1) 散列表可能会退化为链表,查询的时间复杂度就从 O(1) 退化为 O(n) 将链表法中的链表改造为其他高效的动态数据结构比如红黑树查询的时间复杂度是 O(logn) 将链表法中的链表改造红黑树还有一个非常重要的原因可以防止DDos攻击
DDos 攻击: 分布式拒绝服务攻击(英文意思是Distributed Denial of Service简称DDoS 指处于 不同位置的多个攻击者同时向一个或数个目标发动攻击或者 一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的这类攻击称为分布式拒绝服务攻击其中的攻击者可以有多个 3.3 面试题-说一下HashMap的实现原理 面试官追问HashMap的jdk1.7和jdk1.8有什么区别 3.4 面试题-HashMap的put方法的具体流程
3.4.1 hashMap常见属性 3.4.2 源码分析 HashMap是懒惰加载在创建对象时并没有初始化数组 在无参的构造函数中设置了默认的加载因子DEFA..是0.75
添加数据流程图
具体的jdk8源码 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;//当前数组中的数据数量如果大于扩容阈值if (size threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//添加操作时 返回空值return null;
} HashMap的put方法的具体流程 判断键值对数组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如果超过进行扩容。
3.5 面试题-讲一讲HashMap的扩容机制 扩容的流程 源码 //扩容、初始化数组
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等价于oldCap*2//运算过后判断是不是最大值并且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该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上
3.6 面试题-hashMap的寻址算法 3.9 面试题-HashTable与HashMap的区别
难易程度☆☆ 出现频率☆☆ 主要区别 区别 HashTable HashMap 数据结构 数组链表 数组链表红黑树 是否可以为null Key和value都不能为null 可以为null hash算法 key的hashCode() 二次hash 扩容方式 当前容量翻倍 1 当前容量翻倍 线程安全 同步(synchronized)的线程安全 非线程安全
在实际开中不建议使用HashTable在多线程环境下可以使用ConcurrentHashMap类
3 真实面试还原
3.1 Java常见的集合类 面试官说一说Java提供的常见集合画一下集合结构图 候选人 嗯~~好的。 在java中提供了量大类的集合框架主要分为两类 第一个是Collection 属于单列集合第二个是Map 属于双列集合 在Collection中有两个子接口List和Set。在我们平常开发的过程中用的比较多像list接口中的实现类ArrarList和LinkedList。 在Set接口中有实现类HashSet和TreeSet。 在map接口中有很多的实现类平时比较常见的是HashMap、TreeMap还有一个线程安全的map:ConcurrentHashMap 3.2 List 面试官ArrayList底层是如何实现的 候选人 嗯~我阅读过arraylist的源码我主要说一下add方法吧 第一确保数组已使用长度size加1之后足够存下下一个数据 第二计算数组的容量如果当前数组已使用长度1后的大于当前的数组长度则调用grow方法扩容原来的1.5倍 第三确保新增的数据有地方存储之后则将新元素添加到位于size的位置上。 第四返回添加成功布尔值。 面试官ArrayList listnew ArrayList(10)中的list扩容几次 候选人 是new了一个ArrarList并且给了一个构造参数10对吧(问题一定要问清楚再答) 面试官是的 候选人 好的在ArrayList的源码中提供了一个带参数的构造方法这个参数就是指定的集合初始长度所以给了一个10的参数就是指定了集合的初始长度是10这里面并没有扩容。 面试官如何实现数组和List之间的转换 候选人 嗯这个在我们平时开发很常见 数组转list可以使用jdk自动的一个工具类Arrars里面有一个asList方法可以转换为数组 List 转数组可以直接调用list中的toArray方法需要给一个参数指定数组的类型需要指定数组的长度。 面试官用Arrays.asList转List后如果修改了数组内容list受影响吗List用toArray转数组后如果修改了List内容数组受影响吗 候选人 Arrays.asList转换list之后如果修改了数组的内容list会受影响因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合在这个集合的构造器中把我们传入的这个集合进行了包装而已最终指向的都是同一个内存地址 list用了toArray转数组后如果修改了list内容数组不会影响当调用了toArray以后在底层是它是进行了数组的拷贝跟原来的元素就没啥关系了所以即使list修改了以后数组也不受影响 面试官ArrayList 和 LinkedList 的区别是什么 候选人 嗯它们两个主要是底层使用的数据结构不一样ArrayList 是动态数组LinkedList 是双向链表这也导致了它们很多不同的特点。 1从操作数据效率来说 ArrayList按照下标查询的时间复杂度O(1)【内存是连续的根据寻址公式】 LinkedList不支持下标查询 查找未知索引 ArrayList需要遍历链表也需要链表时间复杂度都是O(n) 新增和删除 ArrayList尾部插入和删除时间复杂度是O(1)其他部分增删需要挪动数组时间复杂度是O(n) LinkedList头尾节点增删时间复杂度是O(1)其他都需要遍历链表时间复杂度是O(n) 2从内存空间占用来说 ArrayList底层是数组内存连续节省内存 LinkedList 是双向链表需要存储数据和两个指针更占用内存 3从线程安全来说ArrayList和LinkedList都不是线程安全的 面试官嗯好的刚才你说了ArrayList 和 LinkedList 不是线程安全的你们在项目中是如何解决这个的线程安全问题的 候选人 嗯是这样的主要有两种解决方案 第一我们使用这个集合优先在方法内使用定义为局部变量这样的话就不会出现线程安全问题。 第二如果非要在成员变量中使用的话可以使用线程安全的集合来替代 ArrayList可以通过Collections 的 synchronizedList 方法将 ArrayList 转换成线程安全的容器后再使用。 LinkedList 换成ConcurrentLinkedQueue来使用 3.4 HashMap 面试官说一下HashMap的实现原理 候选人 嗯。它主要分为了一下几个部分 1底层使用hash表数据结构即数组链表 | 红黑树 2添加数据时计算key的值确定元素在数组中的下标 key相同则替换 不同则存入链表或红黑树中 3获取数据通过key的hash计算数组下标获取元素 面试官HashMap的jdk1.7和jdk1.8有什么区别 候选人 JDK1.8之前采用的拉链法数组链表 JDK1.8之后采用数组链表红黑树链表长度大于8且数组长度大于64则会从链表转化为红黑树 面试官好的你能说下HashMap的put方法的具体流程吗 候选人 嗯好的。 判断键值对数组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如果超过进行扩容。 面试官好的刚才你多次介绍了hsahmap的扩容能讲一讲HashMap的扩容机制吗 候选人 好的 在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次每次扩容都是达到了扩容阈值数组长度 * 0.75 每次扩容的时候都是扩容之前容量的2倍 扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中 没有hash冲突的节点则直接使用 e.hash (newCap - 1) 计算新数组的索引位置 如果是红黑树走红黑树的添加 如果是链表则需要遍历链表可能需要拆分链表判断(e.hash oldCap)是否为0该元素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上 面试官好的刚才你说的通过hash计算后找到数组的下标是如何找到的呢你了解hashMap的寻址算法吗 候选人 这个哈希方法首先计算出key的hashCode值然后通过这个hash值右移16位后的二进制进行按位 异或运算得到最后的hash值。 在putValue的方法中计算数组下标的时候使用hash值与数组长度取模得到存储数据下标的位置hashmap为了性能更好并没有直接采用取模的方式而是使用了数组长度-1 得到一个值用这个值按位与运算hash值最终得到数组的位置。 面试官为何HashMap的数组长度一定是2的次幂 候选人 嗯好的。hashmap这么设计主要有两个原因 第一 计算索引时效率更高如果是 2 的 n 次幂可以使用位与运算代替取模 第二 扩容时重新计算索引效率更高在进行扩容是会进行判断 hash值按位与运算旧数组长租是否 0 如果等于0则把元素留在原来位置 否则新位置是等于旧位置的下标旧数组长度 面试官好的我看你对hashmap了解的挺深入的你知道hashmap在1.7情况下的多线程死循环问题吗 候选人 嗯知道的。是这样 jdk7的的数据结构是数组链表 在数组进行扩容的时候因为链表是 头插法在进行数据迁移的过程中有可能导致死循环 比如说现在有两个线程 线程一 读取到当前的hashmap数据数据中一个链表在准备扩容时线程二介入 线程二也读取hashmap直接进行扩容。因为是头插法链表的顺序会进行颠倒过来。比如原来的顺序是AB扩容后的顺序是BA线程二执行结束。 当线程一再继续执行的时候就会出现死循环的问题。 线程一先将A移入新的链表再将B插入到链头由于另外一个线程的原因B的next指向了A所以B-A-B,形成循环。 当然JDK 8 将扩容算法做了调整不再将元素加入链表头而是保持与扩容前一样的顺序 尾插法就避免了jdk7中死循环的问题。 面试官好的hashmap是线程安全的吗 候选人不是线程安全的 面试官那我们想要使用线程安全的map该怎么做呢 候选人我们可以采用ConcurrentHashMap进行使用它是一个线程安全的HashMap 面试官那你能聊一下ConcurrentHashMap的原理吗 候选人好的请参考《多线程相关面试题》中的ConcurrentHashMap部分的讲解 面试官HashSet与HashMap的区别 候选人嗯是这样。 HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true. 面试官HashTable与HashMap的区别 候选人 嗯他们的主要区别是有几个吧 第一数据结构不一样hashtable是数组链表hashmap在1.8之后改为了数组链表红黑树 第二hashtable存储数据的时候都不能为null而hashmap是可以的 第三hash算法不同hashtable是用本地修饰的hashcode值而hashmap经常了二次hash 第四扩容方式不同hashtable是当前容量翻倍1hashmap是当前容量翻倍 第五hashtable是线程安全的操作数据的时候加了锁synchronizedhashmap不是线程安全的效率更高一些 在实际开中不建议使用HashTable在多线程环境下可以使用ConcurrentHashMap类
