前言八股按照重要程度来进行复习时间充裕可全部看一下不充裕的话就看重点部分第一优先级redis、mysql一定要背第二优先级JVM虚拟机、SSM框架一定要背第三优先级常见集合、计算机网络大部分要背第四优先级Java基础、数据结构、操作系统时间不充裕可不背可以实习的时候复习1.算法复杂度分析1.1为什么要进行复杂度分析编写性能更优的代码评价别人代码写的好坏1.2 时间复杂度分析2.List相关面试题2.1 数组概述数组Array是一种用连续的内存空间存储相同数据类型数据的线性数据结构int[] array {22,33,44,55}我们定义了这么一个数组之后在内存的表示是这样的现在假如我们通过arrar[1]想要获得下标为1这个元素但是现在栈内存中指向的堆内存数组的首地址它是如何获取下标为1这个数据的2.2 寻址公式我们把数组的内存地址稍微改了一下都改成了数字如下图在数组在内存中查找元素的时候是有一个寻址公式的如下​arr[i] baseAddress i * dataTypeSize​baseAddress数组的首地址目前是10​dataTypeSize代表数组中元素类型的大小目前数组重存储的是int型的数据dataTypeSize4个字节​arr指的是数组​i指的是数组的下标​​有了寻址公式以后我们再来获取一下下标为1的元素这个是原来的数组​int[] array {22,33,88,66,55,25};​套入公式​array[1] 10 i * 4 14​获取到14这个地址就能获取到下标为1的这个元素了。2.3 操作数组的时间复杂度2.3.1 随机查询根据索引来进行查询数组元素的访问是通过下标来访问的计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素public int test01(int[] a,int i){ return a[i]; // a[i] baseAddress i \* dataSize }代码的执行次数并不会随着数组的数据规模大小变化而变化是常数级的所以查询数据操作的时间复杂度是O(1)2.3.2 未知索引查询O(n)或O(log2n)情况一查找数组内的元素查找55号数据遍历数组时间复杂度为O(n)情况二查找排序后数组内的元素通过二分查找算法查找55号数据时间复杂度为O(logn)2.3.3 查询O(n)数组是一段连续的内存空间因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低。​假设数组的长度为 n现在如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来给新来的数据我们需要将第 kn 这部分的元素都顺序地往后挪一位。如下图所示新增之后的数据变化如下所以​插入操作最好情况下是O(1)的最坏情况下是O(n)的平均情况下的时间复杂度是O(n)。​2.3.4 删除O(n)​同理可得如果我们要删除第 k 个位置的数据为了内存的连续性也需要搬移数据不然中间就会出现空洞内存就不连续了时间复杂度仍然是O(n)。2.4 ArrayList源码分析分析ArrayList源码主要从三个方面去翻阅成员变量构造函数关键方法以下源码都来源于jdk1.82.4.1 成员变量DEFAULT_CAPACITY 10; 默认初始的容量**(CAPACITY)​EMPTY_ELEMENTDATA {}; 用于空实例的共享空数组实例​DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};用于默认大小的空实例的共享空数组实例​Object[] elementData; 存储元素的数组缓冲区​int size; ArrayList的大小它包含的元素数量2.4.2 构造方法第一个构造是带初始化容量的构造函数可以按照指定的容量初始化数组​第二个是无参构造函数默认创建一个空集合将collection对象转换成数组然后将数组的地址的赋给elementData2.4.3 源码分析添加数据的流程结论底层数据结构ArrayList底层使用动态的数组实现的初始容量ArrayList初始容量为0第一次添加数据的时候才会初始化容量为10扩容逻辑ArrayList在进行扩容的时候是原来容量的1.5倍每次扩容都需要拷贝数组添加逻辑确保数组已使用长度size加1之后足够存下下一个数据计算数组容量如果当前数组已使用长度1后的大于当前的数组长度则调用grow方法扩容原来的1.5倍确保新增的数据有地方存储之后则将新元素添加到位于size的位置上。返回添加成功布尔值2.4.4 面试题-ArrayList listnew ArrayList(10)中的list扩容几次参考回答​该语句只是声明和实例了一个 ArrayList指定了容量为 10未扩容2.4.5 面试题-如何实现数组和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.5 链表2.5.1单向链表链表中的每一个元素称之为结点Node​物理存储单元上非连续、非顺序的存储结构​单向链表每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next代码实现参考链表中的某个节点为BB的下一个节点为C 表示 B.nextC2.5.2 单向链表时间复杂度分析1查询操作只有在查询头节点的时候不需要遍历链表时间复杂度是O(1)​查询其他结点需要遍历链表时间复杂度是O(n)2插入和删除操作只有在添加和删除头节点的时候不需要遍历链表时间复杂度是O(1)​添加或删除其他结点需要遍历链表找到对应节点后才能完成新增或删除节点时间复杂度是O(n)2.5.3 双向链表双向链表顾名思义它支持两个方向每个结点不止有一个后继指针 next 指向后面的结点​有一个前驱指针 prev 指向前面的结点参考代码对比单链表​双向链表需要额外的两个空间来存储后继结点和前驱结点的地址​支持双向遍历这样也带来了双向链表操作的灵活性2.5.4 双向链表时间复杂度分析1查询操作​查询头尾结点的时间复杂度是O(1)​平均的查询时间复杂度是O(n)​给定节点找前驱节点的时间复杂度为O(1)2增删操作​头尾结点增删的时间复杂度为O(1)​其他部分结点增删的时间复杂度是 O(n)​给定节点增删的时间复杂度为O(1)2.5.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和LinkedList3.HashMap相关面试题3.1 二叉树3.1.1 二叉树概述二叉树顾名思义每个节点最多有两个“叉”也就是两个子节点分别是左子节点和右子节点。不过二叉树并不要求每个节点都有两个子节点有的节点只有左子节点有的节点只有右子节点。​二叉树每个节点的左子树和右子树也分别满足二叉树的定义。Java中有两个方式实现二叉树数组存储链式存储。​基于链式存储的树的节点可定义如下3.1.2 二叉搜索树在二叉树中比较常见的二叉树有​满二叉树​完全二叉树​二叉搜索树​红黑树1二叉搜索树概述二叉搜索树(Binary Search Tree,BST)又名二叉查找树有序二叉树或者排序二叉树是二叉树中比较常用的一种类型​二叉查找树要求在树中的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值2二叉搜索树-时间复杂度分析插入查找删除的时间复杂度O(logn)​​极端情况下二叉搜索的时间复杂度对于图中这种情况属于最坏的情况二叉查找树已经退化成了链表左右子树极度不平衡此时查找的时间复杂度肯定是O(n)。3.1.3 红黑树1概述​红黑树Red Black Tree也是一种自平衡的二叉搜索树(BST)之前叫做平衡二叉B树Symmetric Binary B-Tree2红黑树的特质​性质1节点要么是红色,要么是黑色性质2根节点是黑色​性质3叶子节点都是黑色的空节点​性质4红黑树中红色节点的子节点都是黑色​性质5从任一节点到叶子节点的所有路径都包含相同数目的黑色节点​在添加或删除节点的时候如果不符合这些性质会发生旋转以达到所有的性质保证红黑树的平衡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表是根据键Key直接访问在内存存储位置值Value的数据结构它是由数组演化而来的利用了数组支持按照下标进行随机访问数据的特性​举个例子假设有100个人参加马拉松编号是1-100如果要编程实现根据选手的编号迅速找到选手信息​可以把选手信息存入数组中选手编号就是数组的下标数组的元素就是选手的信息。​当我们查询选手信息的时候只需要根据选手的编号到数组中查询对应的元素就可以快速找到选手的信息如下图现在需求升级了​假设有100个人参加马拉松不采用1-100的自然数对选手进行编号编号有一定的规则比如2023ZHBJ001其中2023代表年份ZH代表中国BJ代表北京001代表原来的编号那此时的编号2023ZHBJ001不能直接作为数组的下标此时应该如何实现呢我们目前是把选手的信息存入到数组中不过选手的编号不能直接作为数组的下标不过可以把选手的选号进行转换转换为数值就可以继续作为数组的下标了​转换可以使用散列函数进行转换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的数据结构 底层使用hash表数据结构即数组和链表或红黑树当我们往HashMap中put元素时利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时如果出现hash值相同的key此时有两种情况。a. 如果key相同则覆盖原始值b. 如果key不同出现冲突则将当前的key-value放入链表或红黑树中获取时直接找到hash值对应的下标在进一步判断key是否相同从而找到对应值。面试官追问HashMap的jdk1.7和jdk1.8有什么区别​JDK1.8之前采用的是拉链法。拉链法将链表和数组相结合。也就是说创建一个链表数组数组中每一格就是一个链表。若遇到哈希冲突则将冲突的值加到链表中即可。​jdk1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为8 时并且数组长度达到64时将链表转化为红黑树以减少搜索时间。扩容 resize( ) 时红黑树拆分成的树的结点数小于等于临界值6个则退化成链表3.4 面试题-HashMap的put方法的具体流程3.4.1 hashMap常见属性3.4.2 源码分析HashMap是懒惰加载在创建对象时并没有初始化数组​在无参的构造函数中设置了默认的加载因子是0.75添加数据流程图具体的源码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); //因为新插入了一条数据所以判断链表长度是不是大于等于8 if (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传进来的是false if (!onlyIfAbsent || oldValue null) //将新值赋值当前节点 e.value value; afterNodeAccess(e); //返回老值 return oldValue; } } //计数器计算当前节点的修改次数 modCount; //当前数组中的数据数量如果大于扩容阈值 if (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如果超过进行扩容。3.5 面试题-讲一下HashMap的扩容机制扩容的流程源码//扩容、初始化数组 final NodeK,V[] resize() { NodeK,V[] oldTab table; //如果当前数组为null的时候把oldCap老数组容量设置为0 int 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需要大于16 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) * newThr oldThr 1; // double threshold 等价于oldThr*2 } //如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0 else if (oldThr 0) // initial capacity was placed in threshold newCap oldThr; //数组未初始化的情况将阈值和扩容因子都设置为默认值 else { // zero initial threshold signifies using defaults newCap 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; //通过 与操作 计算得出结果为0 if ((e.hash oldCap) 0) { //如果低位尾为null证明当前数组位置为空没有任何数据 if (loTail null) //将e值放入低位头 loHead e; //低位尾不为null证明已经有数据了 else //将数据放入next节点 loTail.next e; //记录低位尾数据 loTail e; } //通过 与操作 计算得出结果不为0 else { //如果高位尾为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的寻址算法在putVal方法中有一个hash(key)方法这个方法就是来去计算key的hash值的看下面的代码首先获取key的hashCode值然后右移16位 异或运算 原来的hashCode值主要作用就是使原来的hash值更加均匀减少hash冲突​有了hash值之后就很方便的去计算当前key的在数组中存储的下标看下面的代码(n-1)hash : 得到数组中的索引代替取模性能更好数组长度必须是2的n次幂​关于hash值的其他面试题为何HashMap的数组长度一定是2的次幂计算索引时效率更高如果是 2 的 n 次幂可以使用位与运算代替取模​扩容时重新计算索引效率更高 hash oldCap 0 的元素留在原来位置 否则新位置 旧位置 oldCap3.7 面试题-HashMap在1.7情况下的多线程死循环问题jdk7的的数据结构是数组链表​在数组进行扩容的时候因为链表是头插法在进行数据迁移的过程中有可能导致死循环变量e指向的是需要迁移的对象​变量next指向的是下一个需要迁移的对象​Jdk1.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中死循环的问题。3.8 面试题-HashSet与HashMap的区别(1)HashSet实现了Set接口, 仅存储对象; HashMap实现了 Map接口, 存储的是键值对.​(2)HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法. 依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象. 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true.3.9 面试题-HashTable与HashMap的区别主要区别在实际开中不建议使用HashTable在多线程环境下可以使用ConcurrentHashMap类4.真实面试题4.1 Java常见的集合类面试官说一说Java提供的常见集合画一下集合结构图​候选人​嗯~~好的。​在java中提供了两大类的集合框架主要分为两类​第一个是Collection 属于单列集合第二个是Map 属于双列集合​在Collection中有两个子接口List和Set。在我们平常开发的过程中用的比较多像list接口中的实现类ArrarList和LinkedList。 在Set接口中有实现类HashSet和TreeSet。​在map接口中有很多的实现类平时比较常见的是HashMap、TreeMap还有一个线程安全的map:ConcurrentHashMap4.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自动的一个工具类Arrays里面有一个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来使用4.3 HashMap面试官说一下HashMap的实现原理​候选人​嗯。它主要分为了以下几个部分​1底层使用hash表数据结构即数组链表 | 红黑树​2添加数据时计算key的值确定元素在数组中的下标​key相同则替换​不同则存入链表或红黑树中​3获取数据通过key的hash计算数组下标获取元素面试官HashMap的jdk1.7和jdk1.8有什么区别​候选人​JDK1.8之前采用的拉链法数组链表​JDK1.8之后采用数组链表红黑树链表长度大于8且数组长度大于64则会从链表转化为红黑树面试官好的你能说下HashMap的put方法的具体流程吗​候选人​嗯好的。​1.判断键值对数组table是否为空或为null否则执行resize()进行扩容初始化​2.根据键值key计算hash值得到数组索引​3.判断table[i]null条件成立直接新建节点添加​4.如果table[i]null ,不成立​判断table[i]的首个元素是否和key一样如果相同直接覆盖value​判断table[i] 是否为treeNode即table[i] 是否是红黑树如果是红黑树则直接在树中插入键值对​遍历table[i]链表的尾部插入数据然后判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操 作遍历过程中若发现key已经存在直接覆盖value​5.插入成功后判断实际存在的键值对数量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类