《⼤⼚⾯试》—Java集合连环30问
1. 常见的集合有哪些？
java集合类主要由两个跟接⼝Conllection 和 Map派⽣出来的，Conllection派⽣出了三个⼦接⼝；List、Set、Queue（Java5新增的队列），因此java集合⼤致也可以分成List、Set、Queue、Map四种接⼝体系。
注意：Conllection是⼀个接⼝，Conlletcions是⼀个⼯具类，Map不是Conllection的⼦接⼝
Java集合框架如下：
图中，List代表了有序可重复集合，可直接根据元素的索引来访问，Set代表⽆序不可重复集合，只能根据元素本⾝来访问；Queue是队列集合
Map代表的是key-value对的集合，可根据元素来访问Value
上图中淡绿⾊背景覆盖的是集合体系中常⽤的实现类，分别是ArrayList、LinkedList、ArrayQueue、HashSet、TreeSet、HashMap、TreeMap等实现类。
2. 线程安全的集合有哪些？线程不安全的呢？
线程安全的：
Hashtable：⽐HashMap多了个线程安全。
ConcurrentHashMap：是⼀种⾼效但是线程安全的集合。resizeby
Vector：⽐Arraylist多了个同步化机制。
Stack：栈，也是线程安全的，继承于Vector。
线性不安全的：
HashMap
Arraylist
LinkedList
HashSet
TreeSet
TreeMap
3. Arraylist与 LinkedList 异同点？
**是否保证线程安全：**ArrayList 和 LinedList 都是不同步的，也就是不保证线程安全的；
**底层数据结构：**ArrayList 底层使⽤的是Object数组；LinkedList 底层使⽤的是双向循环链表数据结构；
插⼊和删除是否⾸元素位置的影响： 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）。
是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ArrayList 实现了RandmoAccess 接⼝，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)⽅法)。
内存空间占⽤： ArrayList的空 间浪费主要体现在在list列表的结尾会预留⼀定的容量空间，⽽LinkedList的空间花费则体现在它的每⼀个元素都需要消耗⽐ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。
4. ArrayList 与 Vector 区别？
Vector是线程安全的，ArrayList不是线程安全的。其中，Vector在关键性的⽅法前⾯都加了synchronized关键字，来保证线程的安全性。如果有多个线程会访问到集合，那最好是使⽤ Vector，因为不需要我们⾃⼰再去考虑和编写线程安全的代码。
ArrayList在底层数组不够⽤时在原来的基础上扩展0.5倍，Vector是扩展1倍，这样ArrayList就有利于节约内存空间。
5. 说⼀说ArrayList 的扩容机制？
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原容量的1.5倍。
以JDK1.8为例说明:
public boolean add(E e){
//判断是否可以容纳e，若能，则直接添加在末尾；若不能，则进⾏扩容，然后再把e添加在末尾
ensureCapacityInternal(size +1);// Increments modCount!!
//将e添加到数组末尾
elementData[size++]= e;
return true;
}
// 每次在add()⼀个元素时，arraylist都需要对这个list的容量进⾏⼀个判断。通过ensureCapacityInternal()⽅法确保当前ArrayList维护的数组具有存储新元素的能⼒，经过处理之后将元素存储在数组elementData的尾部
private void ensureCapacityInternal(int minCapacity){
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData,int minCapacity){
//如果传⼊的是个空数组则最⼩容量取默认容量与minCapacity之间的最⼤值
if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity){
modCount++;
// 若ArrayList已有的存储能⼒满⾜最低存储要求，则返回add直接添加元素；如果最低要求的存储能⼒ArrayList已有的存储能⼒，这就表⽰ArrayList的存储能⼒不⾜，因此需要调⽤ grow();⽅法进⾏扩容
if(minCapacity - elementData.length >0)
grow(minCapacity);
}
private void grow(int minCapacity){
// 获取elementData数组的内存空间长度
int oldCapacity = elementData.length;
// 扩容⾄原来的1.5倍
int newCapacity = oldCapacity +(oldCapacity >>1);
//校验容量是否够
if(newCapacity - minCapacity <0)
newCapacity = minCapacity;
//若预设值⼤于默认的最⼤值，检查是否溢出
if(newCapacity - MAX_ARRAY_SIZE >0)
newCapacity =hugeCapacity(minCapacity);
/
/ 调⽤pyOf⽅法将elementData数组指向新的内存空间
//并将elementData的数据复制到新的内存空间
elementData = pyOf(elementData, newCapacity);
}
6. Array 和 ArrayList 有什么区别？什么时候该应 Array ⽽不是 ArrayList 呢？
Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
Array ⼤⼩是固定的，ArrayList 的⼤⼩是动态变化的。
ArrayList 提供了更多的⽅法和特性，⽐如：addAll()，removeAll()，iterator() 等等。
7. HashMap的底层数据结构是什么？
在JDK1.7 和JDK1.8 中有所差别：
在JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的。
在JDK1.8 中，由“数组+链表+红⿊树”组成。当链表过长，则会严重影响 HashMap 的性能，红⿊树搜索时间复杂度是 O(logn)，⽽链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进⼀步的优化，引⼊了红⿊树，链表和红⿊树在达到⼀定条件会进⾏转换：
当链表超过 8 且数据总量超过 64 才会转红⿊树。
将链表转换成红⿊树前会判断，如果当前数组的长度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树，以减少搜索时间。
8. 解决hash冲突的办法有哪些？HashMap⽤的哪种？
解决Hash冲突⽅法有：开放定址法、再哈希法、链地址法（拉链法）、建⽴公共溢出区。HashMap中采⽤的是 链地址法 。
开放定址法也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p)，如果p1再次出现冲突，则以p1为基础，以此类推，直到到⼀个不冲突的哈希地址pi。因此开放定址法所需要的hash表的长度要⼤于等于所需要存放的元素，⽽且因为存在再次hash，所以只能在删除的节点上做标记，⽽不能真正删除节点。
再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当R1=H1(key1)发⽣冲突时，再计算R2=H2(key1)，直到没有冲突为⽌。
这样做虽然不易产⽣堆集，但增加了计算的时间。
链地址法(拉链法)，将哈希值相同的元素构成⼀个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查、插⼊和删除主要在同义词链表中进⾏。链表法适⽤于经常进⾏插⼊和删除的情况。
建⽴公共溢出区，将哈希表分为公共表和溢出表，当溢出发⽣时，将所有溢出数据统⼀放到溢出区。
9. 为什么在解决 hash 冲突的时候，不直接⽤红⿊树？⽽选择先⽤链表，再转红⿊树?
因为红⿊树需要进⾏左旋，右旋，变⾊这些操作来保持平衡，⽽单链表不需要。当元素⼩于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素⼤于 8 个的时候， 红⿊树搜索时间复杂度是 O(logn)，⽽链表是 O(n)，此时需要红⿊树来加快查询速度，但是新增节点的效率变慢了。
因此，如果⼀开始就⽤红⿊树结构，元素太少，新增效率⼜⽐较慢，⽆疑这是浪费性能的
10. HashMap默认加载因⼦是多少？为什么是 0.75，不是 0.6 或者 0.8 ？
回答这个问题前，我们来先看下HashMap的默认构造函数：
int threshold;// 容纳键值对的最⼤值
final float loadFactor;// 负载因⼦
int modCount;
int size;
Node[] table的初始化长度length(默认值是16)，Load factor为负载因⼦(默认值是0.75)，threshold是HashMap所能容纳键值对的最⼤值。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因⼦越⼤，所能容纳的键值对个数越多。
默认的loadFactor是0.75，0.75是对空间和时间效率的⼀个平衡选择，⼀般不要修改，除⾮在时间和空间⽐较特殊的情况下 ：如果内存空间很多⽽⼜对时间效率要求很⾼，可以降低负载因⼦Load factor的值 。
相反，如果内存空间紧张⽽对时间效率要求不⾼，可以增加负载因⼦loadFactor的值，这个值可以⼤于1。
我们来追溯下作者在源码中的注释（JDK1.7）
/*As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but incr ease the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its l oad factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater t han the maximum number of entries divided by the load factor, no rehash operations will ever occur.*/
翻译过来⼤概的意思是：作为⼀般规则，默认负载因⼦（0.75）在时间和空间成本上提供了很好的折衷。较⾼的值会降低空间开销，但提⾼查成本（体现在⼤多数的HashMap类的操作，包括get和put）。设置初始⼤⼩时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次
数。如果初始容量⼤于最⼤条⽬数除以负载因⼦，rehash操作将不会发⽣。
11. HashMap 中 key 的存储索引是怎么计算的？
⾸先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。看看源码的实现：
// jdk1.7
⽅法⼀：
static int hash(int h){
int h = hashSeed;
if(0!= h && k instanceof String){
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();// 为第⼀步：取hashCode值
h ^=(h >>>20)^(h >>>12);
return h ^(h >>>7)^(h >>>4);
}
⽅法⼆：
static int indexFor(int h,int length){//jdk1.7的源码，jdk1.8没有这个⽅法，但实现原理⼀样
return h &(length-1);//第三步：取模运算
}
// jdk1.8
static final int hash(Object key){
int h;
return(key == null)?0:(h = key.hashCode())^(h >>>16);
/
*
h = key.hashCode() 为第⼀步：取hashCode值
h ^ (h >>> 16)  为第⼆步：⾼位参与运算
*/
}
这⾥的 Hash 算法本质上就是三步：取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标。其中，JDK1.7和1.8的不同之处，就在于第⼆步。我们来看下详细过程，以JDK1.8为例，n为table的长度。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。