集合详解之 Collection
1.List 和 Set 有什么区别？
答：区别分为以下几个方面：
- List 允许有多个 null 值，Set 只允许有一个 null 值；
- List 允许有重复元素，Set 不允许有重复元素；
- List 可以保证每个元素的存储顺序，Set 无法保证元素的存储顺序。
2.哪种集合可以实现自动排序？
答：TreeSet 集合实现了元素的自动排序，也就是说无需任何操作，即可实现元素的自动排序功能。
3.Vector 和 ArrayList 初始化大小和容量扩充有什么区别？
答：Vector 和 ArrayList 的默认容量都为 10，源码如下。
Vector 默认容量源码：
public Vector() {
this(10);
}
ArrayList 默认容量源码：
private static final int DEFAULT_CAPACITY = 10;
Vector 容量扩充默认增加 1 倍，源码如下：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
其中 capacityIncrement 为初始化 Vector 指定的，默认情况为 0。
ArrayList 容量扩充默认增加大概 0.5 倍（oldCapacity + (oldCapacity >> 1)），源码如下（JDK 8）：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
4.Vector、ArrayList、LinkedList 有什么区别？
答：这三者都是 List 的子类，因此功能比较相似，比如增加和删除操作、查找元素等，但在性能、线程安全等方面表现却又不相同，差异如下：
- Vector 是 Java 早期提供的动态数组，它使用 synchronized 来保证线程安全，如果非线程安全需要不建议使用，毕竟线程同步是有性能开销的；
- ArrayList 是最常用的动态数组，本身并不是线程安全的，因此性能要好很多，与 Vector 类似，它也是动态调整容量的，只不过 Vector 扩容时会增加 1 倍，而 ArrayList 会增加 50%；
- LinkedList 是双向链表集合，因此它不需要像上面两种那样调整容量，它也是非线程安全的集合。
5.Vector、ArrayList、LinkedList 使用场景有什么区别？
答：Vector 和 ArrayList
的内部结构是以数组形式存储的，因此非常适合随机访问，但非尾部的删除或新增性能较差，比如我们在中间插入一个元素，就需要把后续的所有元素都进行移动。
LinkedList 插入和删除元素效率比较高，但随机访问性能会比以上两个动态数组慢。
6.Collection 和 Collections 有什么区别？
答：Collection 和 Collections 的区别如下：
- Collection 是集合类的上级接口，继承它的主要有 List 和 Set；
- Collections 是针对集合类的一个帮助类，它提供了一些列的静态方法实现，如 Collections.sort() 排序、Collections.reverse() 逆序等。
7.以下选项没有继承 Collection 接口的是？
A：List
B：Set
C：Map
D：HashSet
答：C
8.LinkedHashSet 如何保证有序和唯一性？
答：LinkedHashSet 底层数据结构由哈希表和链表组成，链表保证了元素的有序即存储和取出一致，哈希表保证了元素的唯一性。
9.HashSet 是如何保证数据不可重复的？
答：HashSet 的底层其实就是 HashMap，只不过 HashSet 实现了 Set 接口并且把数据作为 K 值，而 V
值一直使用一个相同的虚值来保存，我们可以看到源码：
public boolean add(E e) {
return map.put(e, PRESENT)==null;// 调用 HashMap 的 put 方法,PRESENT 是一个至始至终都相同的虚值
}
由于 HashMap 的 K 值本身就不允许重复，并且在 HashMap 中如果 K/V 相同时，会用新的 V 覆盖掉旧的 V，然后返回旧的 V，那么在
HashSet 中执行这一句话始终会返回一个 false，导致插入失败，这样就保证了数据的不可重复性。
10.执行以下程序会输出什么结果？为什么？
Integer num = 10;
Integer num2 = 5;
System.out.println(num.compareTo(num2));
答：程序输出的结果是 1，因为 Integer 默认实现了 compareTo 方法，定义了自然排序规则，所以当 num 比 num2 大时会返回
1，Integer 相关源码如下：
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
11.如何用程序实现后进先出的栈结构？
答：可以使用集合中的 Stack 实现，Stack 是标准的后进先出的栈结构，使用 Stack 中的 pop()
方法返回栈顶元素并删除该元素，示例代码如下。
Stack stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
for (int i = 0; i < 3; i++) {
// 移除并返回栈顶元素
System.out.print(stack.pop() + " ");
}
程序执行结果：c b a
12.LinkedList 中的 peek() 和 poll() 有什么区别？
答：peek() 方法返回第一个元素，但不删除当前元素，当元素不存在时返回 null；poll() 方法返回第一个元素并删除此元素，当元素不存在时返回
null。
13.Comparable 和 Comparator 有哪些区别？
答：Comparable 和 Comparator 的主要区别如下：
- Comparable 位于 java.lang 包下，而 Comparator 位于 java.util 包下；
- Comparable 在排序类的内部实现，而 Comparator 在排序类的外部实现；
- Comparable 需要重写 CompareTo() 方法，而 Comparator 需要重写 Compare() 方法；
- Comparator 在类的外部实现，更加灵活和方便。
总结
本文介绍的集合都实现自 Collection，因此它们都有同样的操作方法，如 add()、addAll()、remove() 等，Collection
接口的方法列表如下图：
当然部分集合也在原有方法上扩充了自己特有的方法，如 LinkedList 的 offer()、push()等方法。本文也提供了数组和集合互转方法，List.toArray() 把集合转换为数组，Arrays.asList(array)把数组转换为集合。最后介绍了 Comparable 和 Comparator 的使用和区别，Comparable 和 Comparator 是 Java语言排序提供的两种排序方式，Comparable 位于 java.lang 包下，如果一个类实现了 Comparable 接口，就意味着该类有了排序功能；而Comparator 位于 java.util 包下，是一个外部比较器，它无需在比较类中实现 Comparator接口，而是要新创建一个比较器类来进行比较和排序。
集合详解之 Map
1.Map 常见实现类有哪些？
答：Map 的常见实现类如下列表：
- Hashtable：Java 早期提供的一个哈希表实现，它是线程安全的，不支持 null 键和值，因为它的性能不如 ConcurrentHashMap，所以很少被推荐使用；
- HashMap：最常用的哈希表实现，如果程序中没有多线程的需求，HashMap 是一个很好的选择，支持 null 键和值，如果在多线程中可用 ConcurrentHashMap 替代；
- TreeMap：基于红黑树的一种提供顺序访问的 Map，自身实现了 key 的自然排序，也可以指定的 Comparator 来自定义排序；
- LinkedHashMap：HashMap 的一个子类，保存了记录的插入顺序，可在遍历时保持与插入一样的顺序。
2.使用 HashMap 可能会遇到什么问题？如何避免？
答：HashMap 在并发场景中可能出现死循环的问题，这是因为 HashMap
在扩容的时候会对链表进行一次倒序处理，假设两个线程同时执行扩容操作，第一个线程正在执行 B→A 的时候，第二个线程又执行了 A→B ，这个时候就会出现
B→A→B 的问题，造成死循环。
解决的方法：升级 JDK 版本，在 JDK 8 之后扩容不会再进行倒序，因此死循环的问题得到了极大的改善，但这不是终极的方案，因为 HashMap
本来就不是用在多线程版本下的，如果是多线程可使用 ConcurrentHashMap 替代 HashMap。
3.以下说法正确的是？
A：Hashtable 和 HashMap 都是非线程安全的
B：ConcurrentHashMap 允许 null 作为 key
C：HashMap 允许 null 作为 key
D：Hashtable 允许 null 作为 key
答：C
题目解析：Hashtable 是线程安全的，ConcurrentHashMap 和 Hashtable 是不允许 null 作为键和值的。
4.TreeMap 怎么实现根据 value 值倒序？
答：使用 Collections.sort(list, new Comparator<Map.Entry<String, String>>()
自定义比较器实现，先把 TreeMap 转换为 ArrayList，在使用 Collections.sort() 根据 value
进行倒序，完整的实现代码如下。
TreeMap<String, String> treeMap = new TreeMap();
treeMap.put("dog", "dog");
treeMap.put("camel", "camel");
treeMap.put("cat", "cat");
treeMap.put("ant", "ant");
// map.entrySet() 转成 List
List<Map.Entry<String, String>> list = new ArrayList<>(treeMap.entrySet());
// 通过比较器实现比较排序
Collections.sort(list, new Comparator<Map.Entry<String, String>>() {
public int compare(Map.Entry<String, String> m1, Map.Entry<String, String> m2) {
return m2.getValue().compareTo(m1.getValue());
}
});
// 打印结果
for (Map.Entry<String, String> item : list) {
System.out.println(item.getKey() + ":" + item.getValue());
}
程序执行结果：
dog:dog
cat:cat
camel:camel
ant:ant
5.以下哪个 Set 实现了自动排序？
A：LinedHashSet
B：HashSet
C：TreeSet
D：AbstractSet
答：C
6.以下程序运行的结果是什么？
Hashtable hashtable = new Hashtable();
hashtable.put("table", null);
System.out.println(hashtable.get("table"));
答：程序执行报错：java.lang.NullPointerException。Hashtable 不允许 null 键和值。
7.HashMap 有哪些重要的参数？用途分别是什么？
答：HashMap 有两个重要的参数：容量（Capacity）和负载因子（LoadFactor）。
- 容量（Capacity）：是指 HashMap 中桶的数量，默认的初始值为 16。
- 负载因子（LoadFactor）：也被称为装载因子，LoadFactor 是用来判定 HashMap 是否扩容的依据，默认值为 0.75f，装载因子的计算公式 = HashMap 存放的 KV 总和（size）/ Capacity。
8.HashMap 和 Hashtable 有什么区别？
答：HashMap 和 Hashtable 区别如下：
- Hashtable 使用了 synchronized 关键字来保障线程安全，而 HashMap 是非线程安全的；
- HashMap 允许 K/V 都为 null，而 Hashtable K/V 都不允许 null；
- HashMap 继承自 AbstractMap 类；而 Hashtable 继承自 Dictionary 类。
9.什么是哈希冲突？
答：当输入两个不同值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。
10.有哪些方法可以解决哈希冲突？
答：哈希冲突的常用解决方案有以下 4 种。
- 开放定址法：当关键字的哈希地址 p=H（key）出现冲突时，以 p 为基础，产生另一个哈希地址 p1，如果 p1 仍然冲突，再以 p 为基础，产生另一个哈希地址 p2，循环此过程直到找出一个不冲突的哈希地址，将相应元素存入其中。
- 再哈希法：这种方法是同时构造多个不同的哈希函数，当哈希地址 Hi=RH1（key）发生冲突时，再计算 Hi=RH2（key），循环此过程直到找到一个不冲突的哈希地址，这种方法唯一的缺点就是增加了计算时间。
- 链地址法：这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
- 建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
11.HashMap 使用哪种方法来解决哈希冲突（哈希碰撞）？
答：HashMap 使用链表和红黑树来解决哈希冲突，详见本文 put() 方法的执行过程。
12.HashMap 的扩容为什么是 2^n ？
答：这样做的目的是为了让散列更加均匀，从而减少哈希碰撞，以提供代码的执行效率。
13.有哈希冲突的情况下 HashMap 如何取值？
答：如果有哈希冲突，HashMap 会循环链表中的每项 key 进行 equals 对比，返回对应的元素。相关源码如下：
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) // 比对时还是先看 hash 值是否相同、再看地址或 equals
return e; // 如果当前节点 e 的键对象和 key 相同，那么返回 e
} while ((e = e.next) != null); // 看看是否还有下一个节点，如果有，继续下一轮比对，否则跳出循环
14.以下程序会输出什么结果？
class Person {
private Integer age;
public boolean equals(Object o) {
if (o == null || !(o instanceof Person)) {
return false;
} else {
return this.getAge().equals(((Person) o).getAge());
}
}
public int hashCode() {
return age.hashCode();
}
public Person(int age) {
this.age = age;
}
public void setAge(int age) {
this.age = age;
}
public Integer getAge() {
return age;
}
public static void main(String[] args) {
HashMap<Person, Integer> hashMap = new HashMap<>();
Person person = new Person(18);
hashMap.put(person, 1);
System.out.println(hashMap.get(new Person(18)));
}
}
答：1
题目解析：因为 Person 重写了 equals 和 hashCode 方法，所有 person 对象和 new Person(18)
的键值相同，所以结果就是 1。
15.为什么重写 equals() 时一定要重写 hashCode()？
答：因为 Java 规定，如果两个对象 equals 比较相等（结果为 true），那么调用 hashCode 也必须相等。如果重写了 equals()
但没有重写 hashCode()，就会与规定相违背，比如以下代码（故意注释掉 hashCode 方法）：
class Person {
private Integer age;
public boolean equals(Object o) {
if (o == null || !(o instanceof Person)) {
return false;
} else {
return this.getAge().equals(((Person) o).getAge());
}
}
// public int hashCode() {
// return age.hashCode();
// }
public Person(int age) {
this.age = age;
}
public void setAge(int age) {
this.age = age;
}
public Integer getAge() {
return age;
}
public static void main(String[] args) {
Person p1 = new Person(18);
Person p2 = new Person(18);
System.out.println(p1.equals(p2));
System.out.println(p1.hashCode() + " : " + p2.hashCode());
}
}
执行的结果：
true
21685669 : 2133927002
如果重写 hashCode() 之后，执行的结果是：
true
18 : 18
这样就符合了 Java 的规定，因此重写 equals() 时一定要重写 hashCode()。
16.HashMap 在 JDK 7 多线程中使用会导致什么问题？
答：HashMap 在 JDK 7 中会导致死循环的问题。因为在 JDK 7 中，多线程进行 HashMap 扩容时会导致链表的循环引用，这个时候使用
get() 获取元素时就会导致死循环，造成 CPU 100% 的情况。
17.HashMap 在 JDK 7 和 JDK 8 中有哪些不同？
答：HashMap 在 JDK 7 和 JDK 8 的主要区别如下。
- 存储结构：JDK 7 使用的是数组 + 链表；JDK 8 使用的是数组 + 链表 + 红黑树。
- 存放数据的规则：JDK 7 无冲突时，存放数组；冲突时，存放链表；JDK 8 在没有冲突的情况下直接存放数组，有冲突时，当链表长度小于 8 时，存放在单链表结构中，当链表长度大于 8 时，树化并存放至红黑树的数据结构中。
- 插入数据方式：JDK 7 使用的是头插法（先将原位置的数据移到后 1 位，再插入数据到该位置）；JDK 8 使用的是尾插法（直接插入到链表尾部/红黑树）。
总结
通过本文可以了解到：
- Map 的常用实现类 Hashtable 是 Java 早期的线程安全的哈希表实现；
- HashMap 是最常用的哈希表实现，但它是非线程安全的，可使用 ConcurrentHashMap 替代；
- TreeMap 是基于红黑树的一种提供顺序访问的哈希表实现；
- LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，可在遍历时保持与插入一样的顺序。
HashMap 在 JDK 7 可能在扩容时会导致链表的循环引用而造成 CPU 100%，HashMap 在 JDK 8 时数据结构变更为：数组 + 链表+ 红黑树的存储方式，在没有冲突的情况下直接存放数组，有冲突，当链表长度小于 8 时，存放在单链表结构中，当链表长度大于 8时，树化并存放至红黑树的数据结构中。
[复制链接]
发表于 2021-2-22 09:35
