二、容器

1.java 容器都有哪些？

主要有Collection和Map两个接口。
Collection的子类有Set和List。其中Set的实现类有HashSet、TreeSet。List的实现类有ArrayList、LinkedList、Vector。
Map的实现类有HashMap、HashTable、TreeMap，HashMap的子类有LinkedHashMap。Map的子类有ConcurrentMap，ConcurrentMap的实现类是ConcurrentHashMap。

2.Collection 和 Collections 有什么区别？

Collection是集合接口，Collections是一个工具类，里面提供了许多操作集合的方法。比如判空、排序等。

3.List、Set、Map 之间的区别是什么？

List和Set都是Collection的子类，Map接口与Collection是同级的。

4.HashMap 和 Hashtable 有什么区别？

1.HashMap类大致相当于哈希表，但它是非同步的，并且允许空值。(HashMap允许空值作为键和值，而哈希表不允许空)。
2.主要之一HashMap与Hashtable的区别是HashMap是非同步的，而Hashtable是同步的，这意味着哈希表线程安全，可以在多个线程之间共享，但是HashMap如果没有适当的同步，就不能在多个线程之间共享。Java 5介绍ConcurrentHashMap它是Hashtable的另一种选择，它提供了比Java中的Hashtable更好的可伸缩性。
3.HashMap和Hashtable之间的另一个显著区别是，HashMap中的迭代器是失败快速迭代器，而Hashtable的枚举器不是，如果任何其他线程通过添加或删除Iterator自己的remove()方法之外的任何元素在结构上修改映射，则抛出ConcurrentModificationException。但是这不是一种有保证的行为，JVM将尽最大努力来完成。这也是Java中枚举和迭代器之间的一个重要区别。

4. Hashtable和HashMap之间一个更显著的区别是，由于线程安全性和同步性，如果在单线程环境中使用，Hashtable比HashMap慢得多。因此，如果您不需要同步，并且HashMap仅由一个线程使用，那么它的性能将优于Java中的Hashtable。
5. HashMap不能保证映射的顺序在一段时间内保持不变。
   （Java迭代器分为快速失败和安全失败。快速失败是指运行中发生错误，会立即停止操作，并暴露错误。安全失败是指发生错误时不会停止运行，因为它是在集合的克隆对象迭代的，所以任何对原集合对象的结构性修改都会被迭代器忽略，但是这类迭代器有一些缺点，其一是它不能保证你迭代时获取的是最新数据，因为迭代器创建之后对集合的任何修改都不会在该迭代器中更新，还有一个缺点就是创建克隆对象在时间和内存上都会增加一些负担。ArrayList，Vector，HashMap等集合返回的迭代器都是快速失败类型的。ConcurrentHashMap返回的迭代器是安全失败迭代器。）

5.如何决定使用 HashMap 还是 TreeMap？

TreeMap<K,V>的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。
HashMap<K,V>的Key值实现散列hashCode()，分布是散列的、均匀的，不支持排序；数据结构主要是桶(数组)，链表或红黑树。适用于在Map中插入、删除和定位元素。
如果你需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。除此之外，由于HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。

6.说一下HashMap的实现原理？

JDK1.8之前的版本，HashMap是使用entry数组加链表的形式实现的。Map中的key和value以entry的形式，保存在数组中。而在数组中的位置是由key的hashcode计算得到的。如果两个key通过计算得出的hashcode相同了，发生了哈希冲突，hashmap使用链表解决冲突。将数组中的entry设置为新值的next。比如A和B都hash后都映射到下标i中，之前已经有A了，当map.put(B)时，将B放到下标i中，A则为B的next，所以新值存放在数组中，旧值在新值的链表上。
JDK1.8版本，采用entry数组+链表+红黑树的形式。当同一个哈市值得节点数不小于8的时候，将不再以单链表的形式存储，而是改为红黑树。
1）介绍HashMap：
按照特性来说明一下：储存的是键值对，线程不安全，非Synchronied，储存的比较快，能够接受null。

按照工作原理来叙述一下：Map的put（key，value）来储存元素，通过get（key）来得到value值，通过hash算法来计算hascode值，用hashCode标识Entry在bucket中存储的位置，储存结构就算哈希表。

“2）你知道HashMap的工作原理吗？” “你知道HashMap的get()方法的工作原理吗？”
“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。
当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。
”这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。
这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，或者错误的认为仅仅只在bucket中存储值的话，你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确，也显示出面试者确实知道hashing以及HashMap的工作原理。

3）提问：两个hashcode相同的时候会发生说明？
hashcode相同，bucket的位置会相同，也就是说会发生碰撞，哈希表中的结构其实有链表（LinkedList），这种冲突通过将元素储存到LinkedList中，解决碰撞。储存顺序是放在表头。

4）如果两个键的hashcode相同，如何获取值对象？
如果两个键的hashcode相同，即找到bucket位置之后，我们通过key.equals（）找到链表LinkedList中正确的节点，最终找到要找的值对象。
一些优秀的开发者会指出使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。

5）如果HashMap的大小超过了负载因子(load factor)定义的容量？怎么办？
HashMap里面默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

6）重新调整HashMap大小的话会出现什么问题？
多线程情况下会出现竞争问题，因为你在调节的时候，LinkedList储存是按照顺序储存，调节的时候回将原来最先储存的元素（也就是最下面的）遍历，多线程就好试图重新调整，这个时候就会出现死循环。

当多线程的情况下，可能产生条件竞争(race condition)。
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

7）HashMap在并发执行put操作，会引起死循环，为什么？
是因为多线程会导致hashmap的node链表形成环形链表，一旦形成环形链表，node 的next节点永远不为空，就会产生死循环获取node。从而导致CPU利用率接近100%。

8）为什么String, Interger这样的wrapper类适合作为键？
因为他们一般不是不可变的，源码上面final，使用不可变类，而且重写了equals和hashcode方法，避免了键值对改写。提高HashMap性能。

String, Interger这样的wrapper类作为HashMap的键是再适合不过了，而且String最为常用。因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

9）使用CocurrentHashMap代替Hashtable？
可以，但是Hashtable提供的线程更加安全。
Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。
10）hashing的概念
散列法（Hashing）或哈希法是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。

11）扩展：为什么equals()方法要重写？
判断两个对象在逻辑上是否相等，如根据类的成员变量来判断两个类的实例是否相等，而继承Object中的equals方法只能判断两个引用变量是否是同一个对象。这样我们往往需要重写equals()方法。

我们向一个没有重复对象的集合中添加元素时，集合中存放的往往是对象，我们需要先判断集合中是否存在已知对象，这样就必须重写equals方法。

7.说一下 HashSet 的实现原理？

①是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。
②当我们试图把某个类的对象当成 HashMap的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的equals(Object obj)方法和hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。
③HashSet的其他操作都是基于HashMap的。

8.ArrayList 和 LinkedList 的区别是什么？

• 数据结构实现：
ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
• 随机访问效率：
ArrayList 比 LinkedList 在随机访问的时候效率要高，
因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
• 增加和删除效率：
在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，
因为 ArrayList 增删操作要影响数组内的其他数据的下标。
• 综合来说：
在需要频繁读取集合中的元素时，更推荐使用 ArrayList，
而在插入和删除操作较多时，更推荐使用 LinkedList。

9.如何实现数组和 List 之间的转换？

数组转List

public static void testArray2List() {
    String[] strs = new String[] {"aaa", "bbb", "ccc"};
    List<String> list = Arrays.asList(strs);
    for (String s : list) {
        System.out.println(s);
    }
}

List转数组

public static void testList2Array() {
    List<String> list = Arrays.asList("aaa", "bbb", "ccc");
    String[] array = list.toArray(new String[list.size()]);
    for (String s : array) {
        System.out.println(s);
    }
}

10.ArrayList 和 Vector 的区别是什么？

线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
性能：ArrayList 在性能方面要优于 Vector。
扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，
只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。