面试3——java集合类面试题总结

1.总结一下啊hashmap和hashtable的知识点？

1）关于hashmap的说法

HashMap实际上是一个“链表散列”的数据结构，在jdk1.8中添加了红黑树。HashMap底层结构是一个数组，数组中的每一项为一条链表，若链表长度超过8，使用红黑树
HashMap的实例有两个参数影响其性能：初始容量和装载因子。HashMap的初始容量为16，装载因子为0.75
HashMap是不同步的，因此是非线程安全的

HashMap的key-value都是存储在Entry中的

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

HashMap可以存null键和null值，不能保证元素的顺序，通过hashcode()方法和equals方法保证键的唯一性
解决hash冲突的方法。HashMap解决hash冲突的方法为链地址法。

2）HashMap和HashTable的区别

继承不同

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

HashTable的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境中，可以直接使用HashTable，但是要使用HashMap的话就要自己额外增加同步处理
```
 Map m = Collections.synchronizedMap(new HashMap(...)); 
```
HashTable中，key和value都不允许出现null，在HashMap中，null可以作为键，这样的键只有一个，可以有一个或者多个键所对应的值为null。当get方法返回null时，既可以表示HashMap中没有该键，也可以表示该键所对应的值为null。因此HashMap中不能由get方法来判断HashMap中是否存在某个键，而应该用containsKey方法来判断
哈希值的使用不同，HashTable直接使用对象的hashcode，而HashMap重新计算hash值
HashTable和HashMap内部实现方式的数组初始大小和扩容方式不同。HashTable中hash数组的默认大小为11，增加方式为old*2+1。HashMap中hash数组的默认大小为16，而且一定是2的倍数。

2. List、Set和Map的区别

List:

可以允许重复的对象
可以插入多个null值
是一个有序容器，即插入的顺序和读取的顺序是一致的
常用的实现类有：Arraylist、Linkedlist和Vector。Arraylist最为流行，它提供了索引的随意访问，若经常添加或删除元素的话，Linkedlist性能比Arraylist好。

　Set：

不允许有重复的对象
无序容器，无法保证每个元素的存储顺序，TreeSet通过实现Comparable中的CompareTo方法对其进行排序（此方法需要重写）
只允许一个null值

　Map：

Map不是collection的子接口或实现类，Map是一个接口
Map的每个Entry都有两个对象，一个键一个值，在map中，键是唯一的，值可以持有相同的值
Map中可以随意持有多个null值，但是最多只能有一个null键

3.什么情况下使用list、set和map

如果你经常会使用索引来对容器中的元素进行访问，那么 List 是你的正确的选择。如果你已经知道索引了的话，那么 List 的实现类比如 ArrayList 可以提供更快速的访问,如果经常添加删除元素的，那么肯定要选择LinkedList
如果你想容器中的元素能够按照它们插入的次序进行有序存储，那么还是 List，因为 List 是一个有序容器，它按照插入顺序进行存储。
如果你想保证插入元素的唯一性，也就是你不想有重复值的出现，那么可以选择一个 Set 的实现类，比如 HashSet、LinkedHashSet 或者 TreeSet。所有 Set 的实现类都遵循了统一约束比如唯一性，而且还提供了额外的特性比如 TreeSet 还是一个 SortedSet，所有存储于 TreeSet 中的元素可以使用 Java 里的 Comparator 或者 Comparable 进行排序。LinkedHashSet 也按照元素的插入顺序对它们进行存储。
如果你以键和值的形式进行数据存储那么 Map 是你正确的选择。你可以根据你的后续需要从 Hashtable、HashMap、TreeMap 中进行选择。

4.Arraylist和Linkedlist的区别

ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于双向链表的数据结构
对于随机访问，ArrayList要优于LinkedList，因为LinkedList要移动指针
对于插入和删除，LinkedList较占优势，ArrayList要移动数据。
ArrayList和LinkedList都是非线程安全的容器

5.Vector和ArrayList的区别

相同点：两者都是基于存储元素的数组来实现的，它们会在内存中开辟块连续的空间来存储，由于数据存储是连续的，它们支持用序号（下标）来访问元素，但是插入和删除是要移动容器中的元素，所以执行较慢。两者都有一个初始化的容量的大小，为10；当里面存储的元素超过这个大小时，就会动态的进行扩容。Vector默认扩充为原来的2倍，ArrayList默认扩充为原来的1.5倍。

区别：二者最大的区别在与synchronization（同步）的使用。在ArrayList中没有一个方法是同步的，而在Vector中，绝大部分方法都是同步的。所以Vector是线程安全的，而ArrayList不是线程安全的。由于Vector提供同步，所以性能上较低于ArrayList。

6.HashMap和ConcurrentHashMap的区别

　http://www.importnew.com/28263.html

7.HashMap的工作实现原理以及代码实现，什么时候用到红黑树

https://www.cnblogs.com/znn93/p/9363894.html

红黑树使用

8.多线程情况下，Hashmap死循环问题

多线程下[Hashmap]的问题

1）多线程put操作后，get操作导致死循环

2）多线程put非null元素后，get操作得到null值

3) 多线程put操作，导致元素丢失

为何会出现死循环

我们知道HashMap采用的是链地址法来解决Hash冲突。因为是链表结构，那么就很容易形成闭合的链路，这样循环的时候只要有线程对这个Hashmap进行get操作，就会产生死循环。在单线程中，只有一个线程对hashmap的数据结构进行操作，是不可能产生闭合回路的。只有在多线程并发的情况下才会发生，在进行put操作的时候，如果size>initialcapacity * loadfactor ，那么这个时候hashmap就会进行rehash操作，随之hashmap的结构就会发生翻天覆地的变化。很有可能两个线程在这个时候同时触发rehash操作，产生闭合的回路。

Hashmap 的 resize 在多线程的情况下可能产生条件竞争。因为如果两个线程都发现 hashmap 需要进行 resize 了，他们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来。因为移动到新的位置时，hashmap 并不会将元素放在链表的尾部，而是放在头部在，这是为了避免尾部遍历。(否则，针对 key 的 hashcode 相同的 entry 每次添加还要定位到尾节点)。如果条件竞争发生了，可能出现环形列表。之后，当我们调用 get(key)操作时就可能发生死循环。

9.HashMap出现Hash dos攻击问题

　　Hash dos攻击问题

Hashmap通过链地址法来解决hash冲突。

10.ConcurrentHashMap的工作原理及代码实现，如何统计所有的元素个数

工作原理链接：https://my.oschina.net/u/3777556/blog/1795495

https://www.cnblogs.com/study-everyday/p/6430462.html

11.Collection和Collections的区别

Collection是集合的上级接口，继承此接口的有set和list

Collections是针对集合类的一个工具类，提供一系列的静态方法实现对各种集合的搜索、排序、线程安全化等操作。