java集合常见面试题总结

一、常见的java集合以及面试常见问题

集合的继承体系

 

Set、Map、List三者对比

1. Set（底层基于Map实现）
   （1）不允许重复对象

（2）无序容器（就是无法保证每个元素的存储顺序，TreeSet通过Comparator或者Comparable维护一个排序顺序）

（3）只允许一个null元素

（4）Set常用实现类：HastSet、LinkedHashSet、TreeSet

1. Map

1. Map不是collection的子接口或实现类。Map是一个接口。
2. Map的每个Entry都持有两个对象，也就是一个key一个value，Map可能会持有相同的值对象蛋健必须唯一。
3. TreeMap通过Comparator或者Comparable维护了一个排序顺序。
4. Map可以拥有多个null值，但只能有一个null键。
5. Map常见实现类：HashMap、LinkedHashMap、Hashtable、TreeMap

1. List

（1）List是一个接口，继承Collection

（2）可以拥有重复对象

（3）可以插入多个null元素

（4）是一个有序容器

（5）常用实现类：ArrayList、LinkedList、Vector（ArrayList适用于查找，LinkedList适用于增删多的操作场合。）

那些场景下使用list、map、set呢？

1. 如果经常使用索引，那么应该使用List。细化：ArrayList适用于查询多的场景，LinkedList适用于增删多的场景。
2. 如果你想容器中的元素能按他们插入次序进行有序存储，那么依然选择List，因为list是有序容器，他按照插入顺序进行存储。
3. 如果你想保证元素的唯一性（就是没有重复元素）可以选择Set的实现类，所有Set实现类都遵循统一约束。

 

ArrayList与LinkedList区别

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构
2. 对于随机访问get和set，ArrayList性能优于LinkedList，因为LinkedList要移动指针。
3. 对于新增（add）和删除（remove），LinkedList性能优于ArrayList，因为ArrayList要移动数组。

底层实现：当程序以get（index）获取集合中指定元素时，ArrayList性能大于LinkedList。因为ArrayList底层基于数组来保存集合元素，调用get时底层调用elementData[index]返回该元素，而LinkedList必须一个一个的搜索找到元素。

               当程序以add（）添加元素时，ArrayList会对数组元素进行整体搬家，如果添加元素导致超过底层数组长度，ArrayList必须在创建一个原来长度1.5倍的数组，再有垃圾回收器回收原来的数组，系统开销比较大。对于LinkedList主要开销再entry（index）上，他必须一个一个搜索过去，找到index处元素并在该元素之前插入新元素。即使如此LinkedList性能依然高于ArrayList。

        当程序remove（index）时，ArrayList仍然需要对数组进行整体搬家，但无需创建新数组（因此ArrayList执行remove略快于add），而LinkedList使用remove时与add时开销几乎完全相同。

Vector和ArrayList区别

1. Vector的方法都是同步的（Synchronized），是线程安全的，而ArrayList不是，由于线程同步必定会损耗性能，因此ArrayList比Vector性能好（而且Java提供了一个Collections工具类，该工具类通过synchronizedList方法既可以将ArrayList包装成线程安全的）。
2. Vector或者ArrayList超过原始大小时，ArrayList总是扩充为原来的1.5倍，但Vector先判断capacityIncrement变量大于0时，则扩充后的容量为原来容量+该变量值，否则扩充为原来的2倍

HashSet与HashMap区别

1. HashSet实现Set接口，HashMap实现了Map接口
2. HastSet仅存一个对象，HashMap存储键值对
3. HashSet使用add（）添加元素，hashMap通过map（）添加元素
4. HashSet通过对象来计算hashCode的值，对于两个对象hashCode可能相同，所以用equals来判断对象相等性。HashMap通过Key计算HashCode。
5. HashMap相对于HashSet快，因为它使用唯一的键获取对象

HashMap与HashTable区别

1. HashMap是非线程安全的，HashTable是线程安全的。
2. HashMap允许key和value为null，而HasnTable都不能为null
3. HashTable继承Dictionary虚拟类，HashMap是JDK1.2中引进的Map接口实现。
4. 两者扩容方法不同，HashTable默认数组为11，扩容为old*2+1，HashMap默认大小为16，而且一定为2的指数，增加为原来的二倍。
5. 两者的hash值散列到hash表算法不同，hashTable是除留余数法，直接使用Object的hashCode，而HashMap蔷薇容量为2的幂，重新根据hashCode计算hash值，在使用hash和（hash表长度-1）进行与运算，更加高效，取得的位置更加分散。
6. hashMap的迭代器是fail-fast,而Hash Table的迭代器不是fail-fast，所以当有其他线程改变了HashMap的结构（增加或删除了元素）将会抛出ConcurrentModificationException，但迭代器本身移除元素不会抛出异常。

HastSet与TreeSet区别

1. TreeSet是二叉树实现，TreeSet中数据是自动排好序的
2. HashSet是哈希表实现，HashSet中数据是无序的，可以放入null，但只能有一个null，两者中都不能有重复。
3. HashSet要求放入的对象必须实现HashCode对象，是以HashCode为表示，而具有相同内容的对象hashCode是相同的，所以放入对象内容要不同。

TreeSet与TreeMap区别

1. 相同点：（1）两者都是非同步集合，他们不能在多线程之间共，都能通过Collections.synchronizedMap()来实现同步

（2）运行速度都不Hash集合慢，他们内部对元素操作时间复杂度为：O（logN），而HashMap/HashSet为O（1）.

              (3)都是有序集合，他们内部都是排好序的

  2.不同点：（1）TreeSet实现了set接口，TreeMap实现了Map接口

              （2）TreeSet只存储一个对象，Tree Map存储key和Value

              （3）TreeMap底层是用红黑树实现，完成数据有序插入、排序

LinkedHashMap与LinkedHashSet

1. LinkedHashMap是HashMap的一个子类，存元素是都是根据hashCode来存，都是无序的，但LinkedHashMap通过next指针以链表的形式将其来连接起来，通过双向链表维护元素的次序，当遍历集合时LinkedHashMap会根据元素添加的顺序访问集合元素。（存的时候使用哈希值，因为速度快，访问的时候用链表访问，因为有序）
2. LinkedHashSet是HashSet的一个子类，HashSet底层实现基于HashMap，原理同上一样。

HashMap为什么是线程不安全的？

在多线程环境下假设有容器map，已经达到需要扩容的阈值（16*0.75=12）而线程A和线程B同时对map进行插入操作，此时两者都需要扩容，此时A、B都进行了扩容，此时便产生了两个新的table，在进行重新赋值给原来的table时便会出现其中一个会覆盖另一个情况，导致其中一个线程插入操作失败。

如何解决：1.将HashMap替换成HashTable实现多线程安全，但会降低性能。

2.使用Collection类的synchronizedMap包装一下HashMap

              3.使用ConCurrentHashMap，它使用分段锁来保证线程安全，效率较高。

Hash碰撞

计算得到的Hash值相同，需要放到同一个桶中，但该位置已经有值存在，即产生了冲突

解决Hash碰撞方法：1.链表法：就是将相同的hash值的对象组成一个链表放在对应hash值的位置。

       2.开放地址发：通过一个探测算法，当某个位置已经被占据的情况下继续寻找下一个可以使用的位置。