这几道Java集合框架面试题在面试中几乎必问

　　主要内容：

　　Arraylist与LinkedList异同

　　ArrayList与Vector区别

　　HashMap的底层实现

　　HashMap和Hashtable的区别

　　HashMap的长度为什么是2的幂次方

　　HashSet和HashMap区别

　　ConcurrentHashMap和Hashtable的区别

　　ConcurrentHashMap线程安全的具体实现方式/底层具体实现

　　集合框架底层数据结构总结

　　Arraylist与LinkedList异同

　　1.是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全；

　　2.底层数据结构：Arraylist底层使用的是Object数组；LinkedList底层使用的是双向循环链表数据结构；

　　3.插入和删除是否受元素位置的影响：①ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(Ee)方法的时候，ArrayList会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置i插入和删除元素的话（add(intindex,Eelement)）时间复杂度就为O(n-i)。因为在进行上述操作的时候集合中第i和第i个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。②LinkedList采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似O（1）而数组为近似O（n）。

　　4.是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList实现了RandmoAccess接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(intindex)方法)。

　　5.内存空间占用：ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

　　补充：数据结构基础之双向链表

　　双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表，如下图所示，同时下图也是LinkedList底层使用的是双向循环链表数据结构。

　　ArrayList与Vector区别

　　Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

　　Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。

　　HashMap的底层实现

　　JDK1.8之前

　　JDK1.8之前HashMap由数组+链表组成的（“链表散列”即数组和链表的结合体），数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（HashMap采用“拉链法也就是链地址法”解决冲突），如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，即需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找.

　　所谓“拉链法”就是将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

　　JDK1.8之后

　　相比于之前的版本，JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

　　TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

　　HashMap和Hashtable的区别

　　线程是否安全：HashMap是非线程安全的，HashTable是线程安全的；HashTable内部的方法基本都经过synchronized修饰。（如果你要保证线程安全的话就使用ConcurrentHashMap吧！）；

　　效率：因为线程安全的问题，HashMap要比HashTable效率高一点。另外，HashTable基本被淘汰，不要在代码中使用它；

　　对Nullkey和Nullvalue的支持：HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null。。但是在HashTable中put进的键值只要有一个null，直接抛出NullPointerException。

　　初始容量大小和每次扩充容量大小的不同：①创建时如果不指定容量初始值，Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。也就是说HashMap总是使用2的幂次方作为哈希表的大小,后面会介绍到为什么是2的幂次方。

　　底层数据结构：JDK1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable没有这样的机制。

　　HashMap的长度为什么是2的幂次方

　　为了能让HashMap存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。

　　这个算法应该如何设计呢？

　　我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说hash%length==hash&(length-1)的前提是length是2的n次方；）。”并且采用二进制位操作&，相对于%能够提高运算效率，这就解释了HashMap的长度为什么是2的幂次方。

　　HashSet和HashMap区别

　　ConcurrentHashMap和Hashtable的区别

　　ConcurrentHashMap和Hashtable的区别主要体现在实现线程安全的方式上不同。

　　底层数据结构：JDK1.7的ConcurrentHashMap底层采用分段的数组+链表实现，JDK1.8采用的数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Hashtable和JDK1.8之前的HashMap的底层数据结构类似都是采用数组+链表的形式，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的；

　　实现线程安全的方式（重要）：①在JDK1.7的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。）到了JDK1.8的时候已经摒弃了Segment的概念，而是直接用Node数组+链表/红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作。（JDK1.6以后对synchronized锁做了很多优化）整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本；②Hashtable(同一把锁):使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用put添加元素，另一个线程不能使用put添加元素，也不能使用get，竞争越激烈效率越低。

　　两者的对比图：

　　JDK1.7的ConcurrentHashMap：

　　JDK1.8的ConcurrentHashMap（TreeBin:红黑二叉树节点；Node:链表节点）：

　　ConcurrentHashMap线程安全的具体实现方式/底层具体实现

　　JDK1.7（上面有示意图）

　　首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。

　　ConcurrentHashMap是由Segment数组结构和HahEntry数组结构组成。

　　Segment实现了ReentrantLock,所以Segment是一种可重入锁，扮演锁的角色。HashEntry用于存储键值对数据。

　　staticclassSegment<K,V>extendsReentrantLockimplementsSerializable{}

　　一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似，是一种数组和链表结构，一个Segment包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得对应的Segment的锁。

　　JDK1.8（上面有示意图）

　　ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。

　　synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

　　集合框架底层数据结构总结

　　Collection

　　1.List

　　Arraylist：Object数组

　　Vector：Object数组

　　LinkedList：双向循环链表

　　2.Set

　　HashSet（无序，唯一）:基于HashMap实现的，底层采用HashMap来保存元素。HashMap底层数据结构见下。

　　LinkedHashSet：LinkedHashSet继承与HashSet，并且其内部是通过LinkedHashMap来实现的。有点类似于我们之前说的LinkedHashMap其内部是基于Hashmap实现一样，不过还是有一点点区别的。

　　TreeSet（有序，唯一）：红黑树(自平衡的排序二叉树。)

　　Map

　　HashMap：JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间

　　LinkedHashMap:LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap源码详细分析（JDK1.8）》：http://www.imooc.com/article/22931

　　HashTable:数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的

　　TreeMap:红黑树（自平衡的排序二叉树）

　　以上就是极悦注册机构介绍的“这几道Java集合框架面试题在面试中几乎必问”的内容，希望通过此文，能够帮助到那些正在找工作的Java程序员，更多Java面试题请在线咨询，有专业老师为你提供名企Java面试题。

　　相关推荐

　　Java面试题请点击：