List, Set, Map相关知识点

程序设计

HashMap 和 HashTable 的区别

线程安全

HashMap 是非线程安全的，HashTable 是线程安全的，HashTable 内部的方法基本都经过 synchronized 修饰，HashMap 有线程安全版本的实现 ConcurrentHashMap

效率

因为线程安全的问题，HashMap 要比 HashTable 效率高一些，HashTable 基本已经被淘汰了

null 的支持

HashMap 中可以将 null 设为 key（hashCode 为 0）,但是只允许有一个，value 为 null 可以有多个

HashTable 中 key 或 value 任何一个 null 都会有 NullPointerException（value 如果判断是 null 直接抛出 NPE，key 没有判断，但是 key 如果为 null,key.hashCode()就会报 NPE）(ConcurrentHashMap 无论 key 还是 value 为 null，都会主动抛 NPE)

初始容量和扩容

创建时如果不指定容量初始值，HashTable 默认的初始大小为 11，每次扩容，容量变为原来的 2n + 1；HashMap 的默认初始化大小为 16,每次扩容，容量变为原来的两倍

如果指定了初始值，HashTable 会直接用这个值，HashMap 会用 tableSizeFor()方法将其扩充为 2 的幂次方

底层数据结构

JDK 1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）并且数组长度大于 64,会将链表转为红黑树，以减少搜索时间，当红黑树节点低于 6 时，转回链表

HashTable 没有这样的机制

HashMap 和 HashSet 的区别

HashSet 底层就是基于 HashMap 来实现的，HashSet 执行 add(xxx)的时候，把 xxx 作为 key 放到 map 里，key 对应的 value 是一个无意义 new Object()，因为 map 中的 key 是唯一的，所以 set 存的元素不能重复

HashMap JDK1.7 和 JDK1.8 的区别

  • JDK 1.7 之前是数组加链表，JDK 1.8 后也属数组加链表，如果哈希冲突严重则转换为红黑树
  • JDK 1.7 头插法（先将原位置的数据移到后一位，再插入数据到该位置），JDK 1.8 尾插法（直接插入到链表尾部/红黑树），尾插法能解决并发下的死循环问题

HashMap 加载因子

为什么不能是 0.5 或者 1.0，而是 0.75

如果是 1.0，只有当 HashMap 满了才会扩容，哈希计算出来的结果很难说刚好落在每一个空的位置上，所以发生扩容的时候，很大程度上 HashMap 已经发生了多次哈希冲突了，如果 HashMap 变成了链表或者红黑树，则对元素操作的时间就会增加，运行效率就会降低，影响性能，属于时间换空间

如果是 0.5，当 HashMap 放了一半元素时则扩容，但是每次当一半的时候就扩容，则至少有一半的空间是永远用不到，造成了内存的浪费，相对地，哈希冲突概率减少，元素操作时间也会减少，属于空间换时间

HashMap 源码的注释，0.75 是一个平衡点

1
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

HashMap 扩容流程

流程：

  • 判断当前容量大小是否为空，如果为空（未设置容量初始值），则把容量扩充为 16
  • 获取 key 的 hashCode，对 hashCode 进行扰动处理，计算出元素的下标
  • 根据下标判断有无 hash 碰撞，如果没有，则直接放入桶中
  • 如果发生碰撞，比较两个 key 是否相等，相等则将新值覆盖旧值，不相等则以链表的形式插入到尾部
  • 如果插入后链表的长度超过了阈值 8，并且数组长度大于 64，则将链表转换为红黑树
  • 插入成功后，如果元素个数达到了阈值（初始容量 * 负载因子），则进行扩容操作
  • 扩容成功后，对元素的下标进行重新计算

ArrayList 和 LinkedList 的区别

ArrayList

基于动态数组，连续内存存储，随机访问（下标）快，增删满（因为长度固定，扩容需要复制原数组）

LinkedList

基于链表，存储在分散的内存中，增删快，查询慢，需要逐一遍历。遍历时候用迭代器，如果用 fori，每次都要 list.get(i)，重新进行遍历，性能消耗极大（可以用增强性 for 循环 forEach，内部实现也是迭代器）

ArrayList 和 Vector 的区别

相同点

  • 两个类都继承了相同的类，实现了相同的接口
  • 底层都属 Object 数组
  • 默认的初始化长度都是 10

不同点

  • Vector 使用了 synchronized 来实现线程同步，是线程安全的，而 ArrayList 不是线程安全的
  • 扩容的时候，ArrayList 扩容成原来的 1.5 倍，Vector 扩容成 2 倍

List 和 Set 的区别

List

有序，按对象进入的顺序来保存，可重复，允许多个 null 元素，可以使用迭代器遍历，或者下标的方式

Set

无序，不可重复，最多一个 null 元素，只能用迭代器遍历

为什么 Set 最多只能放一个 null 元素？

以用得比较多的 HashSet 为例，内部的添加元素方法 add 方法的实现是这样的

1
2
3
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

其中的 map 就是一个 HashMap

1
private transient HashMap<E,Object> map;

map 的 value PRESENT 是一个空对象

1
private static final Object PRESENT = new Object();

所以在 HashSet 中添加元素，其实最终是执行了 HashMap 的 put 方法，把这个元素当作一个 key 存进去，value 则是空对象

HashMap 的 put 方法会对 key 进行一个 hash 计算，算出来 hashCode 确定存放的位置，而当 key 是 null 的时候，hashCode 会是 0，所以如果在 HashSet 中添加了多个 null，全部都是会放到 HashMap 中 hashCode 为 0 的位置

1
2
3
4
5
6
7
8
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

所以这就是为什么 HashSet 的元素不可重复，或者只能放一个 null

HashSet 存储的元素是否有序

无序

HashSet 是 Set 的一个实现类，底层是基于 HashMap 实现的，HashSet 存储的元素对应 HashMap 的 key，因为 HashMap 不能存储重复的 key，所以 HashSet 不能存储重复元素

由于 HashMap 的 key 是基于 hashCode 的，所以 HashSet 中存储的对象是无序的

HashSet 没有提供 get 方法，只能通过 Iterator 迭代器获取数据

有一种情况是 HashSet 中存放的是纯数字，因为子类一般会重写父类的方法，hashCode() 是 Object 的，Integer 在实现的时候，把当前 int 值直接当作 hashCode 返回，所以遍历起来造成一种有序的假象

集合快速失败机制

首先要说明为什么 Java 集合遍历，不是集合类实现 Iterator，而是返回它的迭代器对象？

因为如果是集合本身去实现，那么可能你访问的是别人遍历的数据

而每次返回新的迭代器，遍历数据时就会互不影响，做到隔离性和独立性
（forEach 循环的底层实现就是迭代器）

集合本身有一个 modCount 属性用来保存集合增删操作的次数，因为迭代器是集合的成员内部类，所以可以随时访问集合的成员属性，所以当获取到集合的迭代器的时候，比如当前 modCount 是 3，next() 的时候判断，获取到的 3 和集合当前的 3 还是一样，则正常执行，否则报错 throw new ConcurrentModificationException()

那有没有办法可以解决这个问题呢？

CopyOnWriteArrayList，增删元素时，创建新数组，复制原数组，写的时候加锁，写在新数组，读的时候不加锁，读在旧数组（适用于读多写少，数据量不大的场景）