你好，我是。这是一道关于收藏的面试题。这玩意被问到的概率很高。它是基础中的基础。几乎都会涉及到一两个问题，所以需要注意。我的文章几乎涵盖了收藏相关的所有核心面试点。可以说吃了这篇文章，这个水平就差不多稳定了。字数挺多的，建议先收藏起来。对了，过段时间这篇文章也会收录到我的面试仓库中。上面已经有很多面试题了。求一星！https://github.com/yessimida/interview-of-legends好了，不吹牛了，开始吧！让我们谈谈Java集合。这个问题一般在一开始就用来热身。您无需了解太多细节。一般来说，面试官会根据你回答的要点继续挖掘。从分类的角度来看，Java集合有collection和map两种。前者是存储对象的集合类，后者存储键值对（key-value）。CollectionSet的主要作用是保证存储的集合不会重复。至于集体是有序的还是无序的，要看具体的实现类。比如TreeSet是有序的，HashSet是无序的（所以网上有人说set是无序集合，这是胡说八道）。List很熟悉，具体的实现类是ArrayList和LinkedList的区别在于底层实现不同。前者是数组，后者是双向链表，所以扩展就是数组和链表的区别。数组VS链表数组的内存是连续的，存储元素的大小是固定的。该实现基于内存地址，并且由于元素的大小是固定的，因此它支持使用下标直接访问。具体来说就是通过下标*元素大小+内存基址计算出一个访问地址，然后直接访问，所以随机访问的效率很高，O(1)。但是由于需要保持连续内存特性，内存中间不能有空块，所以在删除中间元素时，需要重定位元素，需要进行内存拷贝，所以删除效率不高。链表的内存不需要是连续的，它们是通过指针连接起来的，所以对内存的要求没有那么高（数组的应用需要一块连续的内存），链表可以是bulkmemory，但是linkedlist需要另外存储指针，所以一般情况下链表占用的内存比较多。而且因为是指针连接，不可能直接随机访问一个元素，必须从头开始遍历（比如双向链表，但是尾），所以随机查找的效率不高，O(n).同样由于指针相通的特性，单边删除效率很高，因为只需要改变指针，不需要额外的内存复制动作（但是要找到这个元素还是很费力的，除非你遍历和依次删除）。两者的大致特点如前所述，再深入一点，再说说CPU亲和性的问题。你应该听说过空间局部性。空间局部性：如果一个内存位置被引用，它附近的位置将来也会被引用。根据这个原理，会有一个预读的功能，比如cpucache会读取连续的内存，所以如果你要遍历数组，那么你后面的数据就已经是上次读取的前一个数据了，一块加载，所以CPU亲和性高。另一方面，链表，因为内存不连续，所以无法进行预读，所以CPU亲和性低。顺带一提，链表（数组）如果加上一些约束，也可以用作栈、队列、双向队列。像LinkedList一样可以用作栈或队列。排队有序，严格遵守先进先出，跟平时排队一样，没什么好说的。常用的实现类是LinkedList。是的，这个东西也实现了Queue接口。另外值得一提的是优先级队列，也就是PriorityQueue，它内部是基于一个数组构建的。用法是你自定义一个比较器，自己定义比较规则。这个队列就是按照这个规则来安排队列的优先级。Map存储的是键值对，即给对象（值）设置一个键，通过键就可以找到值。最著名的，平日里用得最多的应该就是HashMap了，它是无序的。还有两个实现类，LinkedHashMap和TreeMap。前者是有链表的，这样插入顺序是保留的，后者是用红黑树实现的，所以是有序的。最后是IdentityHashMap，这个在网上好像比较少的文章提到过，不过还是看一下准备一下吧。HashMap是一个高频面试题，可以说几乎被问烂了。。。有些问题还是很难的，比如问默认初始容量是多少（16），hash函数是怎么设计的。..如果你没有准备，你肯定会上当，所以让我们抓住他们。能说说HashMap的实现原理吗？其实有一个Entry数组，Entry中存放的是key和value。当要插入一个键值对时，会根据一个哈希算法计算出key的哈希值，然后通过数组大小n-1&哈希值后得到一个数组下标，然后在插入Entry那个位置。那么我们知道hash算法可能会产生冲突，而数组的大小是有限的，所以通过不同的key计算得到相同的下标是有可能的。因此，为了解决Entry冲突的问题，采用了链表的方式，如下图所示：JDK1.7及之前链表的插入采用的是头部插入的方式，即新建一个Entry被插入链表的头部。在JDK1.8中改变了尾部插入方式，引入了红黑树。当链表长度大于8且数组??大小大于等于64时，将链表转为红黑树，当红黑树节点数小于6、会退化成链表。为什么JDK1.8把红黑树改成了HashMap？主要是为了避免哈希冲突导致链表长度过长，这样获取的时间复杂度并不是严格的O(1)，因为可能需要遍历链表才能找到HitEntry。为什么定义链表长度为8，数组大小大于等于64才转为红黑树？用红黑树代替链表不就行了吗？因为红黑树节点的大小是普通节点的两倍，为了节省内存空间不会直接使用红黑树，只有当节点数达到一定数量时才会转化为红黑树，这里定义为8，为什么是8？其实这个在HashMap的注释中也有提到，和泊松分布有关。这所大学应该已经学会了。简单翻译一下就是当默认阈值为0.75时，节点长度为8的冲突概率为0.00000006，也就是说概率比较小（毕竟红黑树很耗内存，遍历还是很快的链表的长度很短）。这是基于时间和空间的平衡。红黑树占用内存大，所以节点少的时候不使用红黑树。如果真的有很多冲突，就用红黑树，参数的大小为8。平衡时间和空间的问题。少于6个节点为什么要从红黑树转链表？也是为了平衡时间和空间。如果节点太少，链表的遍历也很快。小于等于8为什么不改而设置6呢？这是因为有一个缓冲空间，可以避免重复的水平跳跃。比如重复添加一个节点，从8到9，链表变成红黑树，然后删除，从9到8，再从红黑树变成链表，再添加，然后从链表变成红黑树？所以多了一点，毕竟树化和反树化都有开销。JDK1.8除了红黑树的变化之外，HashMap还有哪些变化？哈希函数的优化和扩容优化rehash的头插入和尾插入插入和扩容时机的改变哈希函数1.7的优化是这样实现的：staticinthash(inth){h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}1.8的实现方式如下：staticfinalinthash(Objectkey){inth;返回（键==空）？0:(h=key.hashCode())^(h>>>16);}具体来说就是对1.7的操作太多了，经过四次异或，所以1.8优化了一下，对key的哈希码高16位和低16位进行异或，得到的哈希值既有高位也有低位低的特性。这样得到的代码比较统一，不容易冲突。这也是JDK开发者基于速度、实用性、hash质量做出的权衡的实现：扩容rehash的优化按照我们的思路，正常扩容必须先申请更大的数组，再申请原数组。每个元素被重新散列以确定在新数组中的位置，然后一个一个地移动到那里。这个是1.7实现的，1.8这里做了优化。重点是数组的长度是2的幂，展开2倍。因为数组的长度是2的n次方，假设之前的数组长度（16）二进制表示是01000，那么新的数组长度（32）二进制表示就是10000，这个应该很容易理解吧？它们的区别在于高位多了一个1，而我们通过key的hash值定位它在数组中位置的方法是(arraylength-1)&hash。我们以16和32的长度为例：16-1=15，二进制为0011132-1=31，二进制为01111，所以关键在于key的hash值从左到右第四位是否为1，如果是1表示需要重新定位到新的位置，新位置的下标为原下标+16（原数组的大小）。如果为0，则表示无法访问到新数组length的高位，所以还在原来的位置，不需要迁移。所以，我们只是用旧数组的长度（01000）来判断高位是否为1。这里只有两种情况，要么是1，要么是0。从上面的源码可以看出，链接的数据list计算一次然后串运，因为在扩容的时候，节点的下标只会变到原来的位置，或者原来的位置+旧数组的长度，不会有第二个三选项。上面的位运算，包括为什么原来的下标+旧数组的长度等等，不懂的可以拿几个数带进去计算一下，就可以理解了。综上所述，1.8的扩展不需要每个节点重写hash计算下标，而是通过**&**计算与旧数组长度是否为0来确定新下标的位置。再补充一个问题：为什么HashMap的长度一定要是2的n次方？原因出在数组下标的计算上。由于下标的计算公式使用的是i=(n-1)&hash，是按位运算，一般我们可以想到的是%(余数)计算，但是相对于位运算，效率比较低，所以推荐位运算，为满足上式，n的大小必须为2的n次方。即：当b等于2的n次方时，a%b运算等于a&(b-1)头插尾尾插法1.7为头插法，如上图所示。头插入方式的优点是插入时不需要遍历链表，直接用头节点代替，缺点是展开时会倒序，倒序可能会导致多线程运行下循环，然后无限循环。然后1.8就是尾插法。如果每次都从末尾插入，扩容后的链表顺序还是和之前一样，所以多线程扩容是不可能成环的。事实上，我在网上搜索过。很多文章都说尾部插入方式的优化是为了避免多线程运行形成循环的问题。我对此表示怀疑。因为HashMap根本就不是线程安全的，我要优化你的多线程情况？我认为开发者不应该做这样的优化。那为什么会变成塞尾法呢？我没有找到官方答案，如果有人知道，请教我。让我们再扩展一点。HashMap改成尾插入方式后会不会死循环？1.7插入扩容时机的改变是先判断put的键值对是新的还是替换的。如果是更换，则直接更换。如果是Adding会判断当前元素个数是否大于等于阈值。如果超过阈值，数组索引命中的位置已经有元素，那么扩容。if((size>=threshold)&&(null!=table[bucketIndex])){resize(2*table.length);散列=（空！=键）？散列（键）：0；bucketIndex=indexFor(hash,table.length);}createEntry(...)所以1.7先展开，再插入。1.8中，先插入，再判断size是否大于阈值，大于则扩容。就是这样的区别。至于为什么，嗯，我查了也没查出来，我自己也不清楚。我个人认为两者没有区别。.可能是重构的时候改了顺序（引入红黑树）...其实没什么作用，其他的也想不出来了。在网上也没有找到比较有说服力的答案，有知道的请再教教我。HashMap大概只有这么几点。建议看源码，巩固一下。LinkedHashMapLinkedHashMap的父类是HashMap，所以它具有HashMap的一切，然后在HashMap的基础上做了一些扩展。首先，它在HashMap的Entry中添加了两个指针：before和after。目的已经很明显了，就是把插入的Entry关联成一个双向链表。下图中红色的就是新添加的两个指针，里面还有一个accessOrder成员。默认为false，表示链表的顺序是按照插入的顺序排列的。如果为真，则根据访问顺序进行调整，也就是我们熟悉的那种LRU。如果一个节点被访问，它将被移动到最后，代表最近访问的节点。具体实现其实就是HashMap埋了几个方法，然后LinkedHashMap实现了这些方法来做操作，比如下面三个，从方法名就可以看出来：访问节点后做什么；插入节点后做什么；删除节点后要做什么。以afterNodeInsertion为例，它埋在HashMap的put中，插入一个新的节点后，会调用这个方法，然后LinkedHashMap实现这个方法，可以看到这个方法主要是用来移除最旧的节点。看到这里你能想到什么？如果想使用map作为本地缓存，由于缓存的个数不能无限，可以继承LinkedHashMap来实现。当节点数量超过一定数量时，同时插入新的节点，移除长时间未被访问的最旧节点，这样就实现了LRU。具体方法是将accessOrder设置为true，这样每访问一个节点，就会把刚访问的节点移到最后，然后重写removeEldestEntry方法。LinkedHashMap的默认实现是直接返回true。你可以做一个：protectedbooleanremoveEldestEntry(Entry
