集合面试题

1，List, Set, Map三个接口，存取元素时各有什么特点

List与Set都是单列元素的集合，它们有一个功共同的父接口Collection。

Set里面不允许有重复的元素，

存元素：add方法有一个boolean的返回值，当集合中没有某个元素，此时add方法可成功加入该元素时，则返回true；当集合含有与某个元素equals相等的元素时，此时add方法无法加入该元素，返回结果为false。

取元素：没法说取第几个，只能以Iterator接口取得所有的元素，再逐一遍历各个元素。

List表示有先后顺序的集合，

存元素：多次调用add(Object)方法时，每次加入的对象按先来后到的顺序排序，也可以插队，即调用add(int index,Object)方法，就可以指定当前对象在集合中的存放位置。

取元素：方法1：Iterator接口取得所有，逐一遍历各个元素

        方法2：调用get(index i)来明确说明取第几个。

Map是双列的集合，存放用put方法:put(obj key,obj value)，每次存储时，要存储一对key/value，不能存储重复的key，这个重复的规则也是按equals比较相等。

取元素：用get(Object key)方法根据key获得相应的value。

        也可以获得所有的key的集合，还可以获得所有的value的集合，

        还可以获得key和value组合成的Map.Entry对象的集合。List以特定次序来持有元素，可有重复元素。Set 无法拥有重复元素,内部排序。Map 保存key-value值，value可多值。

2，LinkedList 是单向链表还是双向链表

Linkedlist，双向链表，优点，增加删除，用时间很短，但是因为没有索引，对索引的操作，比较麻烦，只能循环遍历，但是每次循环的时候，都会先判断一下，这个索引位于链表的前部分还是后部分，每次都会遍历链表的一半 ，而不是全部遍历。

双向链表，都有一个previous和next， 链表最开始的部分都有一个fiest和last 指向第一个元素，和最后一个元素。增加和删除的时候，只需要更改一个previous和next，就可以实现增加和删除，所以说，LinkedList对于数据的删除和增加相当的方便。

3，插入数据时，ArrayList, LinkedList, Vector谁速度较快？

  ArrayList 和Vector他们底层的实现都是一样的，都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。

      Vector中的方法由于添加了synchronized修饰，因此Vector是线程安全的容器，但性能上较ArrayList差，因此已经是Java中的遗留容器。

      LinkedList使用双向链表实现存储（将内存中零散的内存单元通过附加的引用关联起来，形成一个可以按序号索引的线性结构，这种链式存储方式与数组的连续存储方式相比，内存的利用率更高），按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。            

      Vector属于遗留容器（Java早期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器），已经不推荐使用，但是由于ArrayList和LinkedListed都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器后再使用（这是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）

4，ArrayList 和 LinkedList 的区别，什么时候用 ArrayList？

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

ArrayList是实现了基于动态数组的数据结构

ArrayList它是由数组后推得到的；而LindedLsit是由常规的双向链表实现的，每个元素都包含了数据和指向前后元素的句柄。正是由于这个原因，假如想在一个列表中进行大量的插入和删除操作，那么LindedList无疑是最恰当的选择，如果是想频繁的遍历链表，那么ArrayList的速度要快上很多。所以根据具体使用场合，选择恰当的数据结构能大大提高程序的效率。

5，ArrayList如何实现扩容  

在JDK1.7中，如果通过无参构造的话，初始数组容量为0，当真正对数组进行添加时，才真正分配容量。

每次按照1.5倍（位运算）的比率通过copeOf的方式扩容。

在JKD1.6中，如果通过无参构造的话，初始数组容量为10.每次通过copeOf的方式扩容后容量为原来的1.5倍加1.以上就是动态扩容的原理。  

6，HashSet和TreeSet有什么区别  

1、TreeSet 是二叉树实现的,Treeset中的数据是自动排好序的，不允许放入null值。 TreeSet是SortedSet接口的唯一实现类，向TreeSet中加入的应该是同一个类的对象。

2、HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。

3、HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的 String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。

7，HashSet 内部是如何工作的  

HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

8，Set保证元素唯一底层依赖的两个方法

hashCode和equals来完成的
* 如果元素的hashCode值相同，才会判断equals是否为true
* 如果hashCode的值不同，不会调用equals方法
* 注意：对于判断元素是 否存在，以及删除等操作。依赖的方法是元素的hashCode和equals方法。

9，简述一致性 Hash 算法  

一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

1、平衡性(Balance)

2、单调性(Monotonicity)

3、分散性(Spread)

4、负载(Load)

普通的哈希算法（也称硬哈希）采用简单取模的方式，将机器进行散列，这在cache环境不变的情况下能取得让人满意的结果，但是当cache环境动态变化时，这种静态取模的方式显然就不满足单调性的要求（当增加或减少一台机子时，几乎所有的存储内容都要被重新散列到别的缓冲区中）。

一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。当有一个写入缓存的请求到来时，计算Key值k对应的哈希值Hash(k)，如果该值正好对应之前某个机器节点的Hash值，则直接写入该机器节点，如果没有对应的机器节点，则顺时针查找下一个节点，进行写入，如果超过2^32还没找到对应节点，则从0开始查找(因为是环状结构)。

10，HashMap的工作原理是什么

HashMap的底层是用hash数组和单向链表实现的 ，当调用put方法是，首先计算key的hashcode，定位到合适的数组索引，然后再在该索引上的单向链表进行循环遍历用equals比较key是否存在，如果存在则用新的value覆盖原值，如果没有则插入到链表linkedlist的头部。HashMap的两个重要属性是容量capacity和加载因子loadfactor，默认值分布为16和0.75，当容器中的元素个数大于 capacity*loadfactor时，容器会进行扩容resize 为2n，在初始化Hashmap时可以对着两个值进行修改，负载因子0.75被证明为是性能比较好的取值，通常不会修改，那么只有初始容量capacity会导致频繁的扩容行为，这是非常耗费资源的操作，所以，如果事先能估算出容器所要存储的元素数量，最好在初始化时修改默认容量capacity，以防止频繁的resize操作影响性能。

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用LinkedList来解决碰撞问题，当发生碰撞了，对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。

11，HashMap、LinkedMap、TreeMap的区别  

Hashmap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

一般情况下，我们用的最多的是HashMap,HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。

LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。

TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。      

12，Hashmap底层，存储因子，hashtable区别，怎么可以变成线程安全的

Key为null总放在数组第一个位置

Hashmap底层是由数组和链表组成的，实际上是一个静态内部类entry的数组，key，value就是存储在entry中的，entry还存储了一个指向自身的next指针，当存储元素时，会计算元素的哈希值并对数组长度取模得到一个int值，这个值就是元素要存储在数组中的位置，如果不同元素计算的存储位置相同，则会将新添加进来的entry存在数组中，并将其next指向之前的entry，形成一个链表来解决hash冲突问题；当要根据key查询元素时，会根据同样方法算出索引位置，然后迭代链表，调用equals方法判断key的相等性，如果返回true返回当前entry的value，否则返回null

        存储因子：0.75，元素个数超过容量的0.75倍扩容

        区别：

        HashTable基于Dictionary类，而HashMap是基于AbstractMap

HashMap的key和value都允许为null，而Hashtable的key和value都不允许为null

Hashtable是同步的，而HashMap是非同步的

怎么实现线程安全：

使用hashtable：hashtable的put,get方法都加了同步关键字synchronized，当一个线程在调用该put方法时，其他线程就会被阻塞，且连get方法也不能用，效率低，锁粒度大

使用ConcurrentHashMap：它包含一个segment数组，将数据分段存储，给每一段数据配一把锁（锁分段），锁粒度小，既安全又高效

创建一个类实现map接口，重写方法：在每个方法内部对有安全问题的代码块加锁

为什么线程不安全（原因解释很复杂，大概理解一下）：

存在多个线程同时对map扩容时会导致最终只有一个线程扩容后的数组会赋给table，其他线程的数据可能丢失         

                                                         

            集合面试题

1，List, Set, Map三个接口，存取元素时各有什么特点

List与Set都是单列元素的集合，它们有一个功共同的父接口Collection。

Set里面不允许有重复的元素，

存元素：add方法有一个boolean的返回值，当集合中没有某个元素，此时add方法可成功加入该元素时，则返回true；当集合含有与某个元素equals相等的元素时，此时add方法无法加入该元素，返回结果为false。

取元素：没法说取第几个，只能以Iterator接口取得所有的元素，再逐一遍历各个元素。

List表示有先后顺序的集合，

存元素：多次调用add(Object)方法时，每次加入的对象按先来后到的顺序排序，也可以插队，即调用add(int index,Object)方法，就可以指定当前对象在集合中的存放位置。

取元素：方法1：Iterator接口取得所有，逐一遍历各个元素

        方法2：调用get(index i)来明确说明取第几个。

Map是双列的集合，存放用put方法:put(obj key,obj value)，每次存储时，要存储一对key/value，不能存储重复的key，这个重复的规则也是按equals比较相等。

取元素：用get(Object key)方法根据key获得相应的value。

        也可以获得所有的key的集合，还可以获得所有的value的集合，

        还可以获得key和value组合成的Map.Entry对象的集合。List以特定次序来持有元素，可有重复元素。Set 无法拥有重复元素,内部排序。Map 保存key-value值，value可多值。

2，LinkedList 是单向链表还是双向链表

Linkedlist，双向链表，优点，增加删除，用时间很短，但是因为没有索引，对索引的操作，比较麻烦，只能循环遍历，但是每次循环的时候，都会先判断一下，这个索引位于链表的前部分还是后部分，每次都会遍历链表的一半 ，而不是全部遍历。

双向链表，都有一个previous和next， 链表最开始的部分都有一个fiest和last 指向第一个元素，和最后一个元素。增加和删除的时候，只需要更改一个previous和next，就可以实现增加和删除，所以说，LinkedList对于数据的删除和增加相当的方便。

3，插入数据时，ArrayList, LinkedList, Vector谁速度较快？

  ArrayList 和Vector他们底层的实现都是一样的，都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。

      Vector中的方法由于添加了synchronized修饰，因此Vector是线程安全的容器，但性能上较ArrayList差，因此已经是Java中的遗留容器。

      LinkedList使用双向链表实现存储（将内存中零散的内存单元通过附加的引用关联起来，形成一个可以按序号索引的线性结构，这种链式存储方式与数组的连续存储方式相比，内存的利用率更高），按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。            

      Vector属于遗留容器（Java早期的版本中提供的容器，除此之外，Hashtable、Dictionary、BitSet、Stack、Properties都是遗留容器），已经不推荐使用，但是由于ArrayList和LinkedListed都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类Collections中的synchronizedList方法将其转换成线程安全的容器后再使用（这是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）

4，ArrayList 和 LinkedList 的区别，什么时候用 ArrayList？

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

ArrayList是实现了基于动态数组的数据结构

ArrayList它是由数组后推得到的；而LindedLsit是由常规的双向链表实现的，每个元素都包含了数据和指向前后元素的句柄。正是由于这个原因，假如想在一个列表中进行大量的插入和删除操作，那么LindedList无疑是最恰当的选择，如果是想频繁的遍历链表，那么ArrayList的速度要快上很多。所以根据具体使用场合，选择恰当的数据结构能大大提高程序的效率。

5，ArrayList如何实现扩容  

在JDK1.7中，如果通过无参构造的话，初始数组容量为0，当真正对数组进行添加时，才真正分配容量。

每次按照1.5倍（位运算）的比率通过copeOf的方式扩容。

在JKD1.6中，如果通过无参构造的话，初始数组容量为10.每次通过copeOf的方式扩容后容量为原来的1.5倍加1.以上就是动态扩容的原理。  

6，HashSet和TreeSet有什么区别  

1、TreeSet 是二叉树实现的,Treeset中的数据是自动排好序的，不允许放入null值。 TreeSet是SortedSet接口的唯一实现类，向TreeSet中加入的应该是同一个类的对象。

2、HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。

3、HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的 String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。

7，HashSet 内部是如何工作的  

HashSet 的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

8，Set保证元素唯一底层依赖的两个方法

hashCode和equals来完成的
* 如果元素的hashCode值相同，才会判断equals是否为true
* 如果hashCode的值不同，不会调用equals方法
* 注意：对于判断元素是 否存在，以及删除等操作。依赖的方法是元素的hashCode和equals方法。

9，简述一致性 Hash 算法  

一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

1、平衡性(Balance)

2、单调性(Monotonicity)

3、分散性(Spread)

4、负载(Load)

普通的哈希算法（也称硬哈希）采用简单取模的方式，将机器进行散列，这在cache环境不变的情况下能取得让人满意的结果，但是当cache环境动态变化时，这种静态取模的方式显然就不满足单调性的要求（当增加或减少一台机子时，几乎所有的存储内容都要被重新散列到别的缓冲区中）。

一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。当有一个写入缓存的请求到来时，计算Key值k对应的哈希值Hash(k)，如果该值正好对应之前某个机器节点的Hash值，则直接写入该机器节点，如果没有对应的机器节点，则顺时针查找下一个节点，进行写入，如果超过2^32还没找到对应节点，则从0开始查找(因为是环状结构)。

10，HashMap的工作原理是什么

HashMap的底层是用hash数组和单向链表实现的 ，当调用put方法是，首先计算key的hashcode，定位到合适的数组索引，然后再在该索引上的单向链表进行循环遍历用equals比较key是否存在，如果存在则用新的value覆盖原值，如果没有则插入到链表linkedlist的头部。HashMap的两个重要属性是容量capacity和加载因子loadfactor，默认值分布为16和0.75，当容器中的元素个数大于 capacity*loadfactor时，容器会进行扩容resize 为2n，在初始化Hashmap时可以对着两个值进行修改，负载因子0.75被证明为是性能比较好的取值，通常不会修改，那么只有初始容量capacity会导致频繁的扩容行为，这是非常耗费资源的操作，所以，如果事先能估算出容器所要存储的元素数量，最好在初始化时修改默认容量capacity，以防止频繁的resize操作影响性能。

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用LinkedList来解决碰撞问题，当发生碰撞了，对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。

11，HashMap、LinkedMap、TreeMap的区别  

Hashmap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

Hashtable与 HashMap类似,它继承自Dictionary类，不同的是:它不允许记录的键或者值为空;它支持线程的同步，即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。

LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

一般情况下，我们用的最多的是HashMap,HashMap里面存入的键值对在取出的时候是随机的,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。

LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。

TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。      

12，Hashmap底层，存储因子，hashtable区别，怎么可以变成线程安全的

Key为null总放在数组第一个位置

Hashmap底层是由数组和链表组成的，实际上是一个静态内部类entry的数组，key，value就是存储在entry中的，entry还存储了一个指向自身的next指针，当存储元素时，会计算元素的哈希值并对数组长度取模得到一个int值，这个值就是元素要存储在数组中的位置，如果不同元素计算的存储位置相同，则会将新添加进来的entry存在数组中，并将其next指向之前的entry，形成一个链表来解决hash冲突问题；当要根据key查询元素时，会根据同样方法算出索引位置，然后迭代链表，调用equals方法判断key的相等性，如果返回true返回当前entry的value，否则返回null

        存储因子：0.75，元素个数超过容量的0.75倍扩容

        区别：

        HashTable基于Dictionary类，而HashMap是基于AbstractMap

HashMap的key和value都允许为null，而Hashtable的key和value都不允许为null

Hashtable是同步的，而HashMap是非同步的

怎么实现线程安全：

使用hashtable：hashtable的put,get方法都加了同步关键字synchronized，当一个线程在调用该put方法时，其他线程就会被阻塞，且连get方法也不能用，效率低，锁粒度大

使用ConcurrentHashMap：它包含一个segment数组，将数据分段存储，给每一段数据配一把锁（锁分段），锁粒度小，既安全又高效

创建一个类实现map接口，重写方法：在每个方法内部对有安全问题的代码块加锁

为什么线程不安全（原因解释很复杂，大概理解一下）：

存在多个线程同时对map扩容时会导致最终只有一个线程扩容后的数组会赋给table，其他线程的数据可能丢失