这里根据个人说话口吻等编写java集合常见面试题用于记录复习后续会持续更新补充。JAVA集合该部分内容有几大考察要点1.底层源码 2.不同集合之间的对比特点1.底层源码如果是宽泛的问如ArrayList的底层原理是什么需要分别从底层数据结构核心方法讲解2.不同集合对比主要牢记不同集合的特点主要考虑线程安全底层数据结构等再组织语言回答。JAVA提供的常见集合JAVA集合概述java提供了两大类集合框架-第一类是Collection 属于单列集合第二类为Map 属于双列集合。Collection有三个子接口分别为SetListQueue。像我们常用的HashSetTreeSetArrayListPriorityQueue等等都属于该框架。Map为双列集合比较常见的实现类有HashMapTreeMapConcurrentHashMap等。ArrayList的底层原理ArrayList的实现原理ArrayList的底层数据结构是由一个动态数组实现的。这里具体说明一下add方法的底层原理。第一会先确保当前数组长度size1后足够存下一个元素如果不够将进行扩容。在扩容逻辑中会调用grow方法将容量扩容到原来的1.5倍。第二在确保新增数据有地方存储之后会将新元素添加到位于size的位置上。最后在添加成功会返回布尔值。ArrayList的成员变量DEFAULT_CAPACITY 10; 默认初始的容量**(CAPACITY)EMPTY_ELEMENTDATA {}; 用于空实例的共享空数组实例DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};用于默认大小的空实例的共享空数组实例Object[] elementData; 存储元素的数组缓冲区int size; ArrayList的大小它包含的元素数量ArrayList的构造方法第一种无参构造器会将elementData赋值为空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA此时数组容量为0只有在第一次调用add方法才会懒加载首次扩容为10第二种有参构造器如果传入参数initialCapactity0则赋值为空数组。如果传入参数initialCapactity0则创建长度为initialCapactity的数组。如果传入参数initialCapactity0则抛出异常illegalArgumentException第三种为传入集合构造器会将集合转为数组赋值给elementData数组容量为集合的size。HashMap的底层原理HashMap的实现原理第一hashmap底层使用hash表数据结构即数组和链表或红黑树。第二在增添元素时计算key的哈希值确定元素下标。如果出现hash值相同则有两种情况一是key相同那就覆盖原始值。二是key不同出现哈希冲突那就将当前key-value存入链表或红黑树。第三在获取元素时也计算key的hash值找到对应下标再进一步判断key是否相同从而找到对应值。HashMap的成员变量1.默认初始容量2.默认加载因子3.存储元素的hashmap.nodek,v []table4.包含元素数量sizeHashMap的put方法原理第一先判断键值对table是否为null或空如果是则通过resize扩容第二根据key计算hash值确定元素下标如果对应下标为空则直接添加元素。第三对应下标不为空先判断首个元素是否key相同如果相同则覆盖value第四如果key不相同则判断当前table[i]是否为红黑树如果是红黑树则插入键值对。第五如果不是红黑树则遍历table[i]在尾部插入元素。当然在遍历过程如果发现key相同则直接覆盖value第六在插入元素后检测是否需要转换红黑树链表长度大于8并且数组长度大于64或扩容扩容阈值数组容量*扩容因子。HashMap的扩容机制第一在添加元素或初始化时可能会调用resize方法进行扩容。在添加元素时达到了扩容阈值0.75*数组长度会发生扩容。第二第一次添加元素初始化数组长度为16之后每次扩容都是扩容到原来元素的二倍。第三具体扩容逻辑在扩容时会创建一个新数组并把老数组元素挪动到新数组中。这里分出三种情况1.没有hash冲突的节点直接使用 e.hash (newCap - 1) 在新数组中的元素下标2.有哈希冲突如果是链表则判断e.hasholdCap是否为0。如果是新数组元素下标与旧数组元素下标相同如果不是新数组元素下标旧数组元素下标旧数组容量3.如果是红黑树则走红黑树逻辑的添加。HashMap的寻址算法第一通过两次hash计算hash值。先计算key的hashcode再右移16位与原本的hashcode异或运算来使hash值更均匀减少hash冲突第二使用hashn-1代替取模得到数组得到索引。也因此数组长度必须是2的n次幂。为什么HashMap的数组长度一定是2的次幂第一计算索引用位运算替代取模运算更高效第二在扩容时通过hasholdcap计算元素是否留在原来位置更高效。HashMap在1.7情况下的多线程死循环第一在jdk1.7时的数据结构为数组链表第二在jdk1.7时使用头插法在进行扩容数据迁移时可能导致死循环。第三举例现有两个线程线程一读取到当前hashmap并准备扩容时线程二介入。线程二读取hashmap直接扩容将原本链表的AB顺序扩容后变成了BA线程二结束。线程一再执行就会发生死循环导致BAB。第四jdk8对扩容算法做出调整采用了尾插法避免死循环。ArrayList与Vector的区别1.ArrayList与Vector都是List的实现类ArrayList被主要使用而Vector更古老2.两底层都使用object[],ArrayList线程不安全Vector线程安全ArrayList与LinkedList的区别1.线程是否安全两个都不线程安全2.数据结构ArrayList底层采用数组LinkedList底层采用双向链表jdk1.7取消循环3.操作数据ArrayList支持按照下标查询LinkedList不支持下标查询。查找未知索引两个都需要遍历时间复杂度都是On。增删在头尾节点为O1,其它情况ArrayLits需要挪动数组LinkedLIst需要遍历都是On。4.内存空间占用ArrayList底层是数组内存连续节省空间。LinkedList还需要存两个指针更占用内存。HashMap与HashSet的区别1.底层数据结构HashSet底层使用HashMap进行存储。知识HashSet的value默认Object对象2.HashSet实现的是Set接口存储对象HashMap实现Map接口存储键值对。HashMap与HashTable的区别1.底层数据结构HashMap是数组链表红黑树。HashTable是数组链表2.线程是否安全HashMap不安全HashTable安全synchronized粒度粗效率低下。3.扩容机制HashMap是容量翻倍HashTable是翻倍14.是否可为nullHashMap能为nullHashTable不能为null5.hash算法HashMap是二次hashHashTable是hashCode简单介绍ConcurrentHashMap数据结构在1.8之前使用分段数组链表segment默认16hashentry1.8时采用数据链表红黑树线程安全1.8之前对segment数组加锁继承reentrantlock粒度粗。1.8时对Node加锁采用CASsynchronzied并发度1.8之前并发度为segment的个数为16。1.8后为Node个数并非度高。