集合相关面试看这篇就够了

超、凢脫俗 2022-01-27 02:37 282阅读 0赞

### 集合 ###

#### 集合和数组的区别： ####

1：数组是固定长度的；集合可变长度的。

2：数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。

3：数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

#### List和Map区别【软通动力】 ####

一个是存储单列数据的集合，另一个是存储键和值这样的双列数据的集合，List中存储的数据是有顺序，并且允许重复；Map中存储的数据是没有顺序的，其键是不能重复的，它的值是可以有重复的。

List是对象集合，允许对象重复。

Map是键值对的集合，不允许key重复。

#### List和Set区别 ####

List,Set都是继承自Collection接口

List特点：元素有放入顺序，元素可重复

Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉

（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set的Object必须定义equals()方法，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）

Set和List对比：

Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

#### List、Map、Set三个接口，存取元素时，各有什么特点？ ####

首先，List与Set具有相似性，它们都是单列元素的集合，所以，它们有一个功共同的父接口Collection接口。Set里面不允许有重复的元素，即不能有两个相等的对象。

List表示有先后顺序的集合，当我们多次调用add(Obje)方法时，每次加入的对象就像火车站买票有排队顺序一样，按先来后到的顺序排序。

Map与List和Set不同，它是双列的集合每次存储时，要存储一对key/value，不能存储重复的key，这个重复的规则也是按equals比较相等。取则可以根据key获得相应的value，即get(Objectkey)返回值为key所对应的value。另外，也可以获得所有的key的结合。

总结：List以特定次序来持有元素，可有重复元素。Set无法拥有重复元素,内部排序。Map保存key-value值，value可多值。上面是大致不同，另外上述3个只是接口，而具体实现类中，用法大同小异，只是实现的数据结构不同，例如List接口下的LinkedList主要实现了双链表的存储特点，Vector是线程安全的集合类。

#### List、Set、Map是否继承自Collection接口? ####

List、Set是，Map不是；Map接口定义的是Key-Value存储的特性，与List和Set不同，Map在存储对象时，先要定义这个对象的key的值，再存入与这个key相对应的Object，Map集合的取值时根据存入的key（关键字）来获取与这个关键字对应的对象。

#### Set里的元素是不能重复的，那么用什么方法来区分重复与否呢?是用==还是equals()?它们有何区别? ####

Set里的元素是不能重复的，元素重复与否是使用equals()方法进行判断的。

#### 说出ArrayList,Vector,LinkedList的存储性能和特性。【大唐动力面试题】 ####

ArrayList和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，Vector由于使用了synchronized方法（线程安全），通常性能上较ArrayList差，而LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

LinkedList也是线程不安全的，LinkedList提供了一些方法，使得LinkedList可以被当作堆栈和队列来使用。

#### 如何去掉一个Vector集合中重复的元素 ####

VectornewVector=newVector();

for(inti=0;i<vector.size();i++)\{

Objectobj=vector.get(i);

if(!newVector.contains(obj);

newVector.add(obj);

还有一种简单的方式，HashSetset=newHashSet(vector);

#### Arraylist与LinkedList区别 ####

ArrayList是基于动态数组，LinkList是基于链表的数据结构，查询arraylist好，新增删除linklist好。

线程都不同步，也就是线程不安全。

Arraylist：

优点：ArrayList是实现了基于动态数组的数据结构,因为地址连续，一旦数据存储好了，查询操作效率会比较高（在内存里是连着放的）。

缺点：因为地址连续，ArrayList要移动数据,所以插入和删除操作效率比较低。

LinkedList：

优点：LinkedList基于链表的数据结构,地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址，对于新增和删除操作add和remove，LinedList比较占优势。LinkedList适用于要头尾操作或插入指定位置的场景

缺点：因为LinkedList要移动指针,所以查询操作性能比较低。

适用场景分析：

当需要对数据进行对此访问的情况下选用ArrayList，当需要对数据进行多次增加删除修改时采用LinkedList。

整理

1.  是否保证线程安全： ArrayList 和 LinkedList  
    都是不同步的，也就是不保证线程安全；
2.  底层数据结构： Arraylist 底层使用的是Object数组；LinkedList  
    底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别：）；  
    详细可阅读[JDK1.7-LinkedList循环链表优化][JDK1.7-LinkedList]
3.  插入和删除是否受元素位置的影响：

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

1.  是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList  
    支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index)  
    方法)。
2.  内存空间占用： ArrayList的空  
    间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。  
    \-\*\*
3.  发

补充内容:RandomAccess接口

public interface RandomAccess \{

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来  
RandomAccess 接口不过是一个标识罢了。标识什么？  
标识实现这个接口的类具有随机访问功能。

在binarySearch（）方法中，它要判断传入的list  
是否RamdomAccess的实例，如果是，调用indexedBinarySearch（）方法，如果不是，那么调用iteratorBinarySearch（）方法

Scanner input = new Scanner([System.in][]);

String s  = input.nextLine();

input.close();

BufferedReader input = new BufferedReader(new InputStreamReader([System.in][]));

String s = input.readLine();

ArrayList 实现了 RandomAccess 接口， 而 LinkedList  
没有实现。为什么呢？我觉得还是和底层数据结构有关！

ArrayList 底层是数组，而 LinkedList  
底层是链表。数组天然支持随机访问，时间复杂度为  
O（1），所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为  
O（n），所以不支持快速随机访问。，

ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。  
RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess  
接口才具有快速随机访问功能的！

下面再总结一下 list 的遍历方式选择：

实现了RandomAccess接口的list，优先选择普通for循环 ，其次foreach,

未实现RandomAccess接口的list，  
优先选择iterator遍历（foreach遍历底层也是通过iterator实现的），大size的数据，千万不要使用普通for循环

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

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

![Image 1][]

#### ArrayList和Vector的区别【博炎科技】 ####

这两个类都实现了List接口（List接口继承了Collection接口），他们都是有序集合，即存储在这两个集合中的元素的位置都是有顺序的，相当于一种动态的数组，我们以后可以按位置索引号取出某个元素，并且其中的数据是允许重复的。并且都是以数组的方式存储数据的

接着说ArrayList与Vector的区别，这主要包括两个方面：

1、同步性：

Vector是线程安全的，也就是说是它的方法之间是线程同步的，而ArrayList是线程序不安全的，它的方法之间是线程不同步的。如果只有一个线程会访问到集合，那最好是使用ArrayList，因为它不考虑线程安全，效率会高些；如果有多个线程会访问到集合，那最好是使用Vector，因为不需要我们自己再去考虑和编写线程安全的代码。

备注：对于Vector&ArrayList、Hashtable&HashMap，要记住线程安全的问题，记住Vector与Hashtable是旧的，是java一诞生就提供了的，它们是线程安全的，ArrayList与HashMap是java2时才提供的，它们是线程不安全的。

2、数据增长：

ArrayList与Vector都有一个初始的容量大小，当存储进它们里面的元素的个数超过了容量时，就需要增加ArrayList与Vector的存储空间，每次要增加存储空间时，不是只增加一个存储单元，而是增加多个存储单元，每次增加的存储单元的个数在内存空间利用与程序效率之间要取得一定的平衡。Vector默认增长为原来两倍，而ArrayList的增长为原来的1.5倍。ArrayList与Vector都可以设置初始的空间大小，Vector还可以设置增长的空间大小，而ArrayList没有提供设置增长空间的方法。

publicArrayList(intinitialCapacity)//构造一个具有指定初始容量的空列表。

publicArrayList()//构造一个初始容量为10的空列表。

publicArrayList(Collection<?extendsE>c)//构造一个包含指定collection的元素的列表

Vector有四个构造方法：

publicVector()//使用指定的初始容量和等于零的容量增量构造一个空向量。

publicVector(intinitialCapacity)//构造一个空向量，使其内部数据数组的大小，其标准容量增量为零。

publicVector(Collection<?extendsE>c)//构造一个包含指定collection中的元素的向量

publicVector(intinitialCapacity,intcapacityIncrement)//使用指定的初始容量和容量增量构造一个空的向量

#### ArrayList和Vector都是用数组实现的，主要有这么三个区别： ####

Vector是多线程安全的，线程安全就是说多线程访问同一代码，不会产生不确定的结果。而ArrayList不是，这个可以从源码中看出，Vector类中的方法很多有synchronized进行修饰，这样就导致了Vector在效率上无法与ArrayList相比；

两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同。

Vector可以设置增长因子，而ArrayList不可以。

Vector是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。

适用场景分析：

Vector是线程同步的，所以它也是线程安全的，而ArrayList是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用ArrayList效率比较高。

如果集合中的元素的数目大于目前集合数组的长度时，在集合中使用数据量比较大的数据，用Vector有一定的优势。

#### HashMap的理解 ####

链表+数组

外层是一个链表，而一个链表中又是一个数组，存储时先通过key获取hashcode并计算出value存储的链表位置，如果不存在hash碰撞则value存在该链表中数组的第一个位置，如果发生hash碰撞则存在在该链表的数组的最后一个位置。

#### HashMap的工作原理及代码实现 ####

JDK1.8之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap  
通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash  
判断当前元素存放的位置（这里的 n  
指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash  
值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash  
方法也就是扰动函数是为了防止一些实现比较差的hashCode() 方法  
换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

static final int hash(Object key) \{

int h;

// key.hashCode()：返回散列值也就是hashcode

// ^ ：按位异或

// >>>:无符号右移，忽略符号位，空位都以0补齐

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

对比一下 JDK1.7的 HashMap 的 hash 方法源码.

static int hash(int h) \{

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash  
方法的性能会稍差一点点，因为毕竟扰动了 4 次。

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

![Image 1][]

JDK1.8之后

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

![Image 1][]

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

推荐阅读：

《Java 8系列之重新认识HashMap》 ：[https://zhuanlan.zhihu.com/p/21673805][https_zhuanlan.zhihu.com_p_21673805]

#### HashMap和Hashtable的区别 ####

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都实现Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，在只有一个线程访问的情况下，效率要高于Hashtable。

HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。

HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。

Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Mapinterface的一个实现。

最大的不同是，Hashtable的方法是synchronized的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap就必须为之提供外同步。

Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异。

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

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

1.  对Null key 和Null value的支持： HashMap 中，null  
    可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在  
    HashTable 中 put 进的键值只要有一个 null，直接抛出 NulPointerException。
2.  初始容量大小和每次扩充容量大小的不同 ：  
    ①创建时如果不指定容量初始值，Hashtable  
    默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap  
    默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么  
    Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap  
    中的 tableSizeFor() 方法保证，下面给出了源代码）。也就是说 HashMap  
    总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
3.  底层数据结构： JDK1.8 以后的 HashMap  
    在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable  
    没有这样的机制。

HasMap 中带有初始容量的构造函数：

public HashMap(int initialCapacity, float loadFactor) \{

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

if (initialCapacity > MAXIMUM\_CAPACITY)

initialCapacity = MAXIMUM\_CAPACITY;

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

this.loadFactor = loadFactor;

this.threshold = tableSizeFor(initialCapacity);

public HashMap(int initialCapacity) \{

this(initialCapacity, DEFAULT\_LOAD\_FACTOR);

下面这个方法保证了 HashMap 总是使用2的幂作为哈希表的大小。

/\*\*

\* Returns a power of two size for the given target capacity.

\*/

static final int tableSizeFor(int cap) \{

int n = cap - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM\_CAPACITY) ? MAXIMUM\_CAPACITY : n + 1;

参考：[http://blog.csdn.net/qq\_22118507/article/details/51576319][http_blog.csdn.net_qq_22118507_article_details_51576319]

#### HashSet和HashMap区别 ####

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了  
clone() 方法、writeObject()方法、readObject()方法是 HashSet  
自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。）

set是线性结构，set中的值不能重复，hashset是set的hash实现，hashset中值不能重复是用hashmap的key来实现的。

map是键值对映射，可以空键空值。HashMap是Map接口的hash实现，key的唯一性是通过key值hash值的唯一来确定，value值是则是链表结构。

他们的共同点都是hash算法实现的唯一性，他们都不能持有基本类型，只能持有对象

![Image 1][]

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

为了能让 HashMap  
存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash  
值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“  
(n - 1) & hash ”。（n代表数组长度）。这也就解释了 HashMap  
的长度为什么是2的幂次方。

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

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

#### HashMap和ConcurrentHashMap的区别 ####

ConcurrentHashMap是线程安全的HashMap的实现。

（1）ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的syn关键字锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。

（2）HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。

#### HashMap 多线程操作导致死循环问题 ####

在多线程下，进行 put 操作会导致 HashMap 死循环，原因在于 HashMap 的扩容  
resize()方法。由于扩容是新建一个数组，复制原数据到数组。由于数组下标挂有链表，所以需要复制链表，但是多线程操作有可能导致环形链表。复制链表过程如下:

以下模拟2个线程同时扩容。假设，当前 HashMap 的空间为2（临界值为1），hashcode  
分别为 0 和 1，在散列地址 0 处有元素 A 和 B，这时候要添加元素 C，C 经过 hash  
运算，得到散列地址为 1，这时候由于超过了临界值，空间不够，需要调用 resize  
方法进行扩容，那么在多线程条件下，会出现条件竞争，模拟过程如下：

线程一：读取到当前的 HashMap 情况，在准备扩容时，线程二介入

![Image 1][]

线程二：读取 HashMap，进行扩容

![Image 1][]

线程一：继续执行

![Image 1][]

这个过程为，先将 A 复制到新的 hash 表中，然后接着复制 B 到链头（A  
的前边：B.next=A），本来  
B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将  
B.next=A，所以，这里继续复制A，让A.next=B，由此，环形链表出现：B.next=A;  
A.next=B

注意：jdk1.8已经解决了死循环的问题。

#### ConcurrentHashMap原理（中高级） ####

分段

#### ConcurrentHashMap 和 Hashtable 的区别 ####

当HashTable增加到一定数量时性能会急剧降低，因为迭代时会锁很长时间。

而ConcurrentHashMap使用了分割，无论数量多大，都只需要锁map的某一个部分。

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

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

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

两者的对比图：

图片来源：[http://www.cnblogs.com/chengxiao/p/6842045.html][http_www.cnblogs.com_chengxiao_p_6842045.html]

HashTable:

![Image 1][]

JDK1.7的ConcurrentHashMap：

![Image 1][]

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

![Image 1][]

#### ConcurrentHashMap的工作原理及代码实现 ####

JDK1.7（上面有示意图）

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

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

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

static class Segment<K,V> extends ReentrantLock implements Serializable \{

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

JDK1.8 （上面有示意图）

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

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

#### Hashtable的原理【北辰网络】 ####

通过节点的关键码确定节点的存储位置,即给定节点的关键码k,通过一定的函数关系H(散列函数),得到函数值H(k),将此值解释为该节点的存储地址。

#### Linkedlist、Arraylist内部是如何实现的（更深入的问了LinkedList与ArrayList的区别）【天威诚信面试题】 ####

ArrayList的内部实现是基于内部数组Object\[\]，它更像是对数组实现的一种封装，所以在向ArrayList的前面或中间插入数据时，必须将其后的所有数据相应的后移，这样必然要花费较多时间。

而LinkedList的内部实现是基于一组双向链表实现的存储特性，所以提供了链表一样访问的API接口，它们在性能上有很大的差别。当你访问Linkedlist链表中的某个元素时，就必须从链表的一端开始沿着连接方向一个一个元素地去查找，直到找到所需的元素为止，所以，当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。

而当你的操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能。

#### Collections和Collection的区别【天晟科技】 ####

> Collection是个java.util下的接口，它是各种集合结构的父接口，定义了集合对象的基本操作方法。

> Collections是个java.util下的工具类，它包含有各种有关集合操作的静态方法，主要是针对集合类的一个帮助类或者叫包装类，它提供一系列对各种集合的搜索，排序，线程安全化等操作方法。

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

Collection

1.  List

Arraylist： Object数组

Vector： Object数组

LinkedList： 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)  
详细可阅读JDK1.7-LinkedList循环链表优化

1.  Set

HashSet（无序，唯一）: 基于 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）》][LinkedHashMap _JDK1.8]

HashTable: 数组+链表组成的，数组是 HashMap  
的主体，链表则是主要为了解决哈希冲突而存在的TreeMap:  
红黑树（自平衡的排序二叉树）

#### ArrayList如何实现插入的数据按自定义的方式有序存放 ####

实现Comparable比较接口，并实现compareTo方法。排序的方法，取决于compareTo方法中的比较定义的返回值,一般有3个返回值：1、-1、0表示不同的比较结果。

程序示例：

classMyBeanimplementsComparable\{

publicintcompareTo(Objectobj)\{

if(!objinstanceofMyBean)

thrownewClassCastException();

MyBeanother=(MyBean)obj;

returnage>other.age?1:age==other.age?0:-1;

classMyTreeSet\{

privateArrayListdatas=newArrayList();

publicvoidadd(Objectobj)\{

for(inti=0;i<datas.size();i++)\{

if(obj.compareTo(datas.get(i)!=1)\{

datas.add(i,obj);

#### Arrays.sort实现原理和Collection实现原理 ####

Collection.sort()底层会调用Arrays.sort()

Array.sout()底层实现是TimeSort,TimeSort的算法就是先找到已经排好序数据的子序列，然后对剩余部分数据进行排序，然后再合并起来。

[JDK1.7-LinkedList]: https://www.cnblogs.com/xingele0917/p/3696593.html
[System.in]: http://System.in
[Image 1]: 
[https_zhuanlan.zhihu.com_p_21673805]: https://zhuanlan.zhihu.com/p/21673805
[http_blog.csdn.net_qq_22118507_article_details_51576319]: https://link.jianshu.com/?t=http%3A%2F%2Fblog.csdn.net%2Fqq_22118507%2Farticle%2Fdetails%2F51576319
[http_www.cnblogs.com_chengxiao_p_6842045.html]: http://www.cnblogs.com/chengxiao/p/6842045.html
[LinkedHashMap _JDK1.8]: https://www.imooc.com/article/22931