Java 集合框架

张贤 2020年03月17日 137次浏览

数据结构常见考点

  • 数组和链表的区别
  • 链表的操作:如反转、链表环路检测、双向链表、循环链表以及相关操作
  • 队列、栈的应用
  • 二叉树的遍历以及其递归和非递归的实现
  • 红黑树的旋转

算法常见考点

  • 内部排序:如递归排序、交换排序(冒泡、快排)、选择排序、插入排序
  • 外部排序:应掌握如何利用有限的内存配合海量的外部存储来处理超大的数据集,写不出来也要有相关的思路

考点扩展:

  • 哪些排序是稳定的,稳定意味这什么
  • 不同数据集,各种排序最好或者最差的情况
  • 如何优化算法

使用 TreeSet 时,有两种排序方式:

  • 元素本身实现 Comparable 接口:这种情况元素还要重写 hashCode() 和 equals() 方法
  • 使用 Comparator 外部排序器
    如果即使用了 Comparator,原元素也实现了 Comparable 接口,优先使用 Comparator,而且 Comparator 的实现会影响到 TreeSet 的存储。
public class CustomerComparator implements Comparator<Customer> {
    @Override
    public int compare(Customer o1, Customer o2) {
        if (o1.getName().compareTo(o2.getName()) > 0) return -1;
        if (o1.getName().compareTo(o2.getName()) < 0) return 1;
        return 0;
    }

    public static void main(String[] args) {
        Set<Customer> set = new TreeSet<>(new CustomerComparator());
        set.add(new Customer("Tom", 1));
        set.add(new Customer("Tom", 5));
        set.add(new Customer("Tom", 3));
        Iterator<Customer> iterator = set.iterator();
        while (iterator.hasNext()) {
            Customer customer = iterator.next();
            System.out.println(customer.getName() + ":" + customer.getAge());
        }
    }
}

上面代码中,在 Comparator 的实现中只比较了 name,没有比较 age。因此往 TreeSet 里添加元素时,只要 name 相同, TreeSet 就认为是相同的元素,因此需要实现 compare() 方法时需要注意逻辑上正确性。

HashMap、HashTable、ConcurrentHashMap 的区别

  • HashMap:在 Java8 之前是数组+链表,最坏的性能是 O(n);在 Java8 之后是数组+链表+红黑树,最坏的性能是 O(logn)。

HashMap 内部的节点在 Java8 之前是Entry,在 Java8 之后是 Node,如果每个节点链表大小超过 TREEIFY_THRESHOLD = 8,并且数组大小超过 MIN_TREEIFY_CAPACITY = 64 时,则改为使用红黑树存储,而对应的 UNTREEIFY_THRESHOLD = 6。
在 HashMap 的构造函数里没有初始化数组,所以默认大小默认为 0,直到第一次添加元素才扩容为 16,采用的是懒加载。
HashMap 中 put() 方法的逻辑

  1. 如果 HashMap 未被初始化过,则初始化
  2. 对 key 求 Hash 值,然后再计算再数组中的下标
  3. 如果没有碰撞,则直接放入桶中
  4. 如果碰撞了且节点是红黑树,则把节点放入红黑树
  5. 如果碰撞了且节点是链表,则以链表的方式添加到链表尾端
  6. 如果链表长度超过阈值,就把链表转换成红黑树
  7. 如果 key 已经存在,就替换旧值
  8. 如果数组使用了容量*负载因子(0.75),就调用 resize() 方法扩容(扩容两倍),而且需要 rehash
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

混合原始 Hash 值的高位和低位,加大低位的随机性,保证 Hash 值的高16 位和低 16 位都能参与到散列过程,使得散列更为均匀,而且运算速度快,开销小
取模操作:n 总是 2 的倍数,(n - 1) & hash 等价于 对 n 进行取模,但是位运算比取模的效率更高。因此在带有容量的构造参数中,实际的容量是使用tableSizeFor()方法获得比传入参数大的最近的2的次方数。

HashMap 扩容的问题:

  • 多线程环境下,调整大小会存咋竞争,容易操作死锁
  • rehash 是一个比较耗时的操作

Hashtable 就是为每一个方法加上了 synchronized 关键字,并发度低。那么如何优化 HashTable?Java5 之后引入了 ConcurrentHashMap

  • 把锁细粒度化,将锁拆解称为多个锁进行优化。早期的 ConcurrentHashMap 是通过分段锁 Segment 来实现的,默认有 16 把锁。
  • Java8 之后 ConcurrentHashMap 使用了 CAS + synchronized 使锁更加细化

ConcurrentHashMap 中有一个 sizeCtl 变量,0 表示还没有初始化,-1 表示正在初始化,-(1+n) 表示有 n 个线程正在扩容。sizeCtl 被 volatile 修饰,对它的改动能够立刻反映到其他线程中。
ConcurrentHashMap 不允许插入 null 键或者 null 值

ConcurrentHashMap 的 put() 方法的逻辑

  1. 判断 Node[] 数组是否已经初始化,没有则进行初始化
  2. 通过 Hash 定位数组的索引,判断是否有 Node 节点,如果没有则使用 CAS 进行添加链表的头结点,添加失败则进入下次循环
  3. 如果检查到内部有其他线程正在扩容,就帮助它一块扩容
  4. 如果f!=null,则使用synchronized锁住 f 元素(链表/红黑树的投元素)
    • 如果 f 是 Node(链表结构)则执行链表的添加操作
    • 如果是 TreeNode(红黑树),则执行树的添加操作
    • 如果 f 是 ReservationNode,则抛出异常(ReservationNode 和 ConcurrentHashMap 的本地缓存相关)
  5. 判断链表长度是否已经达到临界值 8(这个值可以设置调整),如果超过 8 则把链表转换为红黑树

两道面试题:

size() 方法和 mappingCount() 方法的异同,两者计算是否准确

多线程环境下如何扩容?