转载

Java 容器

1、Java集合类框架的基本接口有哪些？

总共有两大接口：Collection 和 Map ，一个元素集合，一个是键值对集合；其中 List 和 Set 接口继承了 Collection 接口，一个是有序元素集合，一个是无序元素集合；而 ArrayList 和 LinkedList 实现了 List 接口，HashSet 实现了 Set 接口，这几个都比较常用； HashMap 和 HashTable 实现了 Map 接口，并且 HashTable 是线程安全的，但是 HashMap 性能更好；

2、Collection 和 Collections 有什么区别？

java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection 接口在 Java 类库中有很多具体的实现。Collection 接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有 List 与 Set。
Collections 则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

3、为什么集合类接口没有实现 Cloneable 和 Serializable 接口？

克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。

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

5、什么是迭代器(Iterator)？

迭代器是一种设计模式，它是一个对象，它可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。

Java 中的 Iterator 功能比较简单，并且只能单向移动：

(1) 使用方法 iterator()要求容器返回一个 Iterator。第一次调用 Iterator 的 next()方法时，它返回序列的第一个元素。注意：iterator()方法是 java.lang.Iterable 接口,被 Collection 继承。

(2) 使用 next()获得序列中的下一个元素。

(3) 使用 hasNext()检查序列中是否还有元素。

(4) 使用 remove()将迭代器新返回的元素删除。

Iterator 是 Java 迭代器最简单的实现，为 List 设计的 ListIterator 具有更多的功能，它可以从两个方向遍历 List，也可以从 List 中插入和删除元素。

6、Iterator 和 ListIterator 的区别是什么？

Iterator 可用来遍历 Set 和 List 集合，但是 ListIterator 只能用来遍历 List。

Iterator 对集合只能是前向遍历，ListIterator 既可以前向也可以后向。

ListIterator 实现了 Iterator 接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引等等。

7、快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

快速失败：当你在迭代一个集合的时候，如果有另一个线程正在修改你正在访问的那个集合时，就会抛出一个 ConcurrentModification 异常。

在 java.util 包下的都是快速失败，不能在多线程下发生并发修改（迭代过程中被修改）。

安全失败：你在迭代的时候会去底层集合做一个拷贝，所以你在修改上层集合的时候是不会受影响的，不会抛出 ConcurrentModification 异常。

在 java.util.concurrent 包下的全是安全失败的。可以在多线程下并发使用，并发修改。

8、HashMap 和 Hashtable 有什么区别？

1、HashMap 是非线程安全的，HashTable 是线程安全的。

2、HashMap 的键和值都允许有 null 值存在，而 HashTable 则不行。

3、因为线程安全的问题，HashMap 效率比 HashTable 的要高。

4、Hashtable 是同步的，而 HashMap 不是。因此，HashMap 更适合于单线程环境，而 Hashtable 适合于多线程环境。

5、两者提供了可供应用迭代的键的集合，都是快速失败的。此外 Hashtable 提供了对键的列举(Enumeration)

6、 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的 tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

一般现在不建议用 HashTable, ①是 HashTable 是遗留类，内部实现很多没优化和冗余。②即使在多线程环境下，现在也有同步的 ConcurrentHashMap 替代，没有必要因为是多线程而用 HashTable。

HashMap 中带有初始容量的构造函数：

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
复制代码

下面这个方法保证了 HashMap 总是使用2的幂作为哈希表的大小。

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
复制代码

9、ConcurrentHashMap 和 Hashtable 的区别

底层数据结构 ：ConcurrentHashMap 在 JDK1.7 底层采用 分段的数组+链表 实现，在 JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样， 数组+链表/红黑二叉树 。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式 ： ① 在 JDK1.7 的时候，ConcurrentHashMap（ 分段锁 ）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后对 synchronized锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

两者的对比图：

图片来源：http://www.cnblogs.com/chengxiao/p/6842045.html

HashTable:

JDK1.7 的 ConcurrentHashMap：

JDK1.8 的 ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：

10、ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程访问其中一个段数据时，只是占用当前数据段的锁，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}
复制代码

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

JDK1.8（上面有示意图）

ConcurrentHashMap 取消了Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

11、Java 中的 HashMap 的工作原理是什么？

hashmap 是一个 key-value 键值对的数据结构，从结构上来讲在 jdk1.8 之前是用数组加链表的方式实现，jdk1.8 加了红黑树，hashmap 数组的默认初始长度是 16，hashmap 数组只允许一个 key 为 null，允许多个 value 为 null。

hashmap 的内部实现，hashmap 是使用数组+链表+红黑树的形式实现的，其中数组是一个一个 Node[]数组，我们叫他 hash 桶数组，它上面存放的是 key-value 键值对的节点。HashMap 是用 hash 表来存储的，在 hashmap 里为解决 hash 冲突，使用链地址法，简单来说就是数组加链表的形式来解决，当数据被 hash 后，得到数组下标，把数据放在对应下标的链表中。

然后再说一下 hashmap 的方法实现

put 方法，put 方法的第一步，就是计算出要 put 元素在 hash 桶数组中的索引位置，得到索引位置需要三步，计算要 put 元素 key 的 hashcode 值，高位运算，取模运算，高位运算就是用第一步得到的值 h，用 h 的高 16 位和低 16 位进行异或操作，第三步为了使 hash 桶数组元素分布更均匀，采用取模运算，取模运算就是用第二步得到的值和 hash 桶数组长度-1的值取与。这样得到的结果和传统取模运算结果一致，而且效率比取模运算高。
jdk1.8 中 put 方法的具体步骤，先判断 hashmap 是否为空，为空的话扩容，不为空计算出 key 的索引值 i，然后看 table[i]是否为空，为空就直接插入，不为空判断当前位置的 key 和 table[i] 是否相同，相同就覆盖，不相同就查看 table[i] 是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于 8，转为红黑树结构，执行完成后看 size 是否大于阈值 threshold，大于就扩容，否则直接结束。
get 方法就是计算出要获取元素的 hash 值，去对应位置取即可。

HashMap 的两个重要属性是容量 capacity 和加载因子 loadfactor，默认值分布为 16 和 0.75，当容器中的元素个数大于 capacity*loadfactor 时，容器会进行扩容 resize 为 2n，在初始化 Hashmap 时可以对着两个值进行修改，负载因子 0.75 被证明为是性能比较好的取值，通常不会修改，那么只有初始容量 capacity 会导致频繁的扩容行为，这是非常耗费资源的操作，所以，如果事先能估算出容器所要存储的元素数量，最好在初始化时修改默认容量 capacity，以防止频繁的 resize 操作影响性能。

扩容机制，hashmap 的扩容中主要进行两步，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算 hash 插入到新数组中，在 jdk1.8 时，不用重新计算 hash，只用看看原来的 hash 值新增的一位是零还是 1，如果是 1，这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二步一个非常重要的方法是 transfer 方法，采用头插法，把旧数组的元素插入到新数组中。

12、hashmap 大小为什么是 2 的幂次方

在计算插入元素在 hash 桶数组的索引时第三步，为了使元素分布的更加均匀，用取模操作，但是传统取模操作效率低，然后优化成 h&(length-1)，设置成 2 幂次方，是因为 2 的幂次方-1后的值每一位上都是 1，然后与第二步计算出的 h 值与的时候，最终的结果只和 key 的 hashcode 值本身有关，这样不会造成空间浪费并且分布均匀。

如果 length 不为 2 的幂，比如 15。那么 length-1 的 2 进制就会变成 1110。在 h 为随机数的情况下，和 1110 做&操作。尾数永远为 0。那么 0001、1001、1101 等尾数为 1 的位置就永远不可能被 entry 占用。这样会造成浪费，不随机等问题。

13、hashCode()和 equals()方法的重要性体现在什么地方？

HashMap 的很多函数要基于 equal()函数和 hashCode()函数。hashCode()用来定位要存放的位置，equal()用来判断是否相等。hashcode 和 equals 组合在一起确定元素的唯一性。

查找元素时，如果单单使用 equals 来确定一个元素，需要对集合内的元素逐个调用 equals 方法，效率太低。因此加入了 hashcode 方法，将元素映射到随机的内存地址上，通过 hashcode 快速定位到元素（大致）所在的内存地址，再通过使用 equals 方法确定元素的精确位置。

比较两个元素时，先比较 hashcode，如果 hashcode 不同，则元素一定不相等；如果相同，再用 equals 判断。

HashMap 采用这两个方法实现散列存储，提高键的索引性能。HashSet 是基于 HashMap 实现的。

14、数组(Array)和列表(ArrayList)有什么区别？什么时候应该使用 Array 而不是 ArrayList？

数组可以包含基本数据类型和引用类型，ArrayList 只能包含引用类型。注意：Array 数组在存放的时候一定是同种类型的元素。ArrayList 就不一定了，因为 ArrayList 可以存储 Object。
数组空间大小是固定的，但 ArrayList 空间大小是动态变化的，初始化的时候没有定义它的默认容量大小，那么默认是 10，之后的增长规则是：((旧容量 * 3) / 2) + 1
ArrayList 是 List 接口的实现类，相比数组支持更多的方法和特性。

适用场景：

当集合长度固定时，使用数组；当集合的长度不固定时，使用 ArrayList。
由于 ArrayList 不支持基本数据类型，所以保存基本数据类型时需要装箱处理，对比数组性能会下降。这种情况尽量使用数组。
数组支持的操作方法很少，但内存占用少，如果只需对集合进行随机读写，选数组

15、ArrayList 和 LinkedList 有什么区别？

ArrayList 和 LinkedList 都实现了 List 接口，他们有以下的不同点：

ArrayList 是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问，适合元素查找。与此对应，LinkedList 基于链表，为双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)，每一个元素都和它的前一个和后一个元素链接在一起，在这种情况下，查找某个元素的时间复杂度是 O(n)。

相对于 ArrayList，LinkedList 增删操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。

LinkedList 比 ArrayList 更占内存，因为 LinkedList 为每一个节点存储了两个引用，一个指向前一个元素，一个指向后一个元素。

16、Comparable 和 Comparator 接口是干什么的？列出它们的区别。

Comparable & Comparator 都是用来实现集合中元素的比较、排序的。

Comparable 接口（内部比较器）：

Comparable 位于 java.lang 包下。
comparable 接口是在内部类通过重写 compareTo 方法实现的。在使用 Collections.sort(List list)或者Array.sort(Object[] a)对对象集合进行排序的时候，就会根据对象自定义的排序方法排序。
comparable 接口实现较简单，但对于多元素排序不方便，因为在重写 compareTo 方法时事先定义好了元素比较顺序
使用 Comparable 方式比较时，我们将比较的规则写入了比较的类型中，其特点是高内聚。但如果哪天这个规则需要修改，那么我们必须修改这个类型的源代码。

Comparator 接口（外部比较器）：

Comparator 位于 java.util 包下。
comparator 接口则是在外部类通过重写 compare 与 equals 方法实现的。
comparator 接口实现较复杂，可能定义多个外部类，但对于多元素比较使用起来很方便。
使用 Comparator 方式比较，那么我们不需要修改比较的类，其特点是易维护，但需要自定义一个比较器，后续比较规则的修改，仅仅是改这个比较器中的代码即可。

17、什么是 Java 优先级队列(Priority Queue)？

PriorityQueue 的逻辑结构是一棵完全二叉树，存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组。

PriorityQueue 是一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。在创建的时候，我们可以给它提供一个负责给元素排序的比较器。PriorityQueue 不允许 null 值，因为他们没有自然顺序，或者说他们没有任何相关联的比较器。最后，PriorityQueue 不是线程安全的，入队和出队的时间复杂度是 O(log(n))。

18、Java集合类框架的最佳实践有哪些？

19、HashSet 和 TreeSet 有什么区别？

Hashset 的底层是由哈希表实现的，Hashset 中的元素是无序的。add()，remove()，contains()方法的时间复杂度是 O(1)。

Treeset 底层是由红黑树实现的。如果需要在 Treeset 中插入对象，需要实现 Comparable 接口，重写 compareTo 方法。

20、HashSet 的实现原理？

HashSet 底层由 HashMap 实现
HashSet 的值存放于 HashMap 的 key 上
HashMap 的 value 统一为 PRESENT

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

List 转换成为数组：调用 ArrayList 的 toArray 方法。

数组转换成为 List：调用 Arrays 的 asList 方法。

21、Arrays.asList()使用指南

String[] myArray = { "Apple", "Banana", "Orange" }； 
List<String> myList = Arrays.asList(myArray);
//上面两个语句等价于下面一条语句
List<String> myList = Arrays.asList("Apple","Banana", "Orange");
复制代码

注意：使用工具类 Arrays.asList()把数组转换为集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

说明：asList 的返回对象是一个 Arrays 内部类，并没有实现集合的修改方法。Arrays.asList 体现的是适配器模式，只是转换接口，后台的数据仍是数组。

String[] str = new String[]{"and","you"};
List list = Arrays.asList(str);
System.out.println(list.get(1));//输出you
list.add("yes");//抛出异常
str[0] = s"yes";
System.out.println(list);//list也会发生改变，输出[yes, you]
复制代码

Arrays.asList()是泛型方法，传入的参数对象必须是对象数组。

int[] myArray = { 1, 2, 3 };
List myList = Arrays.asList(myArray);
System.out.println(myList.size());//1
System.out.println(myList.get(0));//数组地址值
System.out.println(myList.get(1));//报错：ArrayIndexOutOfBoundsException
int [] array=(int[]) myList.get(0);
System.out.println(array[1]);//1
复制代码

当传入一个原生数据类型数组时，Arrays.asList() 的真正得到的参数就不是数组中的元素，而是数组对象本身！此时List 的唯一元素就是这个数组，这也就解释了上面的代码。

转换为包装数据类型即可。

Integer[] myArray = { 1, 2, 3 };
List myList = Arrays.asList(myArray);
System.out.println(myList.size());//数组长度3
System.out.println(myList.get(0));//1
System.out.println(myList.get(1));//2
复制代码

使用集合的修改方法:add()、remove()、clear()会抛出异常。

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类,这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

List myList = Arrays.asList(1, 2, 3);
System.out.println(myList.getClass());//class java.util.Arrays$ArrayList
复制代码

如何正确的将数组转换为ArrayList?

1、自定义代码

static <T> List<T> arraysToList(T[] array){
    List<T> list = new ArrayList<T>(array.length);

    for(T obj:array){
        list.add(obj);
    }
    return list;
}

String[] str = new String[]{"and","you"};
List ll = arraysToList(str);
System.out.println(ll.getClass());//class java.util.ArrayList

int[] myArray = { 1, 2, 3 };
List ll2 = arraysToList(myArray);//编译报错
复制代码

该方法暂不支持基本数据类型。

2、最简便的方法(推荐)

List list = new ArrayList<>(Arrays.asList("a", "b", "c"))
复制代码

3、使用 Java8 的 Stream(推荐)

Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).collect(Collectors.toList());
//基本类型也可以实现转换（依赖boxed的装箱操作）
int [] myArray2 = { 1, 2, 3 };
List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());
复制代码

4、使用 Guava(推荐)

对于可变集合，你可以使用 Lists 类及其 newArrayList()工厂方法：

String[] str = {"acd","yes"};
List list = Lists.newArrayList(str);//class java.util.ArrayList

int[] myArray = { 1, 2, 3 };
list = Lists.newArrayList(myArray);//class java.util.ArrayList
复制代码

5、使用 Apache Commons Collections

List<String> list = new ArrayList<String>();
CollectionUtils.addAll(list, str);
复制代码

Collection.toArray()方法使用的坑&如何反转数组

该方法是一个泛型方法： T[] toArray(T[] a); 如果 toArray 方法中没有传递任何参数的话返回的是 Object 类型数组。

String [] s= new String[]{
    "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.asList(s);//class java.util.Arrays$ArrayList
Collections.reverse(list);
s=list.toArray(new String[0]);//没有指定类型的话会报错，s2类型为String
Object[] s2 = list.toArray();//效果同上

list = Lists.newArrayList(s);//class java.util.ArrayList
Collections.reverse(list);
s = list.toArray(new String[0]);//编译报错
Object[] s2 = list.toArray(new String[0]);//s2类型为String
复制代码

综上可知，当数组为引用类型数组时，使用 Arrays.asList 转换为 List，反转操作后，再转换为数组，无论 toArray()方法中是否有参数，声明为 Object 类型的数组实际类型都为原引用类型。使用其他数组转 List 方法，比如 Lists.newArrayList，需要在 toArray()参数中传入对应类型，最后得到的数组类型也是原类型。

当数组为基本数据数组时，最后转换之后得到的数组为 Object 类型。