安卓面试总结（2）——Java 集合框架

安卓面试总结（2）——Java 集合框架

上一篇

上安卓面试总结（1）——Java基础

上一篇写到了 Java 的一些基础知识，这篇将以面试的态度去回顾一些 Java 的集合框架，博文的目的不是想让看的人立马能学会多少东西（更多可以看这篇 Java 集合笔记），更多的是希望能够借精简的内容，去回忆，去发散，加深对知识的理解，或许再看一次，还会生出原来如此的想法，这是很美妙的。

1、概述

Java 容器示意图

容器

• Collection：储存对象集合
• Map：储存键值对（两个对象）的映射表（Entry）

Set

• TreeSet：基于红黑树，支持有序新操作，基于范围查找元素（SortedSet）
• HashSet：基于哈希表实现，支持快速查找，但不支持有序操作
• LinkedHashSet：具有 HashSet 的查找效率，且内部使用双向链表维护元素的顺序

List

• ArrayList：基于动态数组实现，支持随机访问（RandomAccess）
• Vectoy：和 ArrayList 类似，当是线性安全的
• LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在键表中间插入和删除元素

Queue

• LinkedList：可以用它实现双向队列（Deque）
• PriorityQueue：基于堆结构实现，可以用它实现优先队列

Map

• TreeMap：基于红黑树实现（SortedMap）
• HashMap：基于哈希表实现
• HashTable：和 HashMap 类似，但是线程安全的，可用 ConcurrentHashMap
• LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序，或者是最近最少使用顺序（LRU）

2、迭代器

Collection 继承了 Iterable 接口

Iterable --> Iterator：通过 iterator() 方法实现

Iterable 方法：

• next()
• hasNext()
• remove()：删除上次 next 方法是返回的元素（必须配合使用）
• dafault forEachRemaining(Consumer)

Iterator 的位置实际是在两个元素中间，remove 的是前一个，next 的是后一个

如何遍历数组？

3、视图与包装器

视图：好像创建了一个新集，将内容填进去，并返回这个集（keySet）

• Arrays.asList(xxx)：包装器
• 子范围
• 不可修改视图
• 同步视图：synchronizedMap()
• 受查视图

4、源码分析

① ArrayList

• RandAccess，仅标记随机访问，删除代价高
• 扩容：默认10，不够扩一半（1.5倍），需要复制数组
• modCount 记录结构变化，迭代、序列化时检查 --> ConcurrentModificationException
• transient：标记数组，只对数组内有的值进行序列化（手动操作）

② Vector

• 内部使用了 synchronized 进行同步，也有 modCount，扩容是 2 倍
• 代替：
  • 用 Collections.synchronizedList<>() 得到线程安全的 ArrayList
  • 使用 CopyOnWriteArrayList

③ CopyOnWriteArrayList

• 读：在原始数组进行、
• 写：在一个复制数组进行，有加锁，写完代替原有数组（指针）
• 优点：大大提高了读操作的效率
• 缺点：内存加倍，数据不一致，没实时性

④ LinkedList

• 双向链表实现，不支持随机访问，无需扩容
• 在任意位置添加删除元素更快

⑤ HashMap

• 内部包含了一个 Entry 类型的数组 Entry[] table，Entry 是一个链表
• 数组每个位置被当作一个同，一个同放一个链表
• 拉链法：同一个链表中存放哈希值和散列同取模运算结果相同的 Entry（头插法）
• HashMao 允许 null 键值对，以第 0 桶存放
• put 方法
  • 判断当前数组是否需要初始化，需要则对 table 初始化。
  • 如果 key 为空，则 put 一个空值进去。
  • 根据 key 计算出 hashcode，并由 hashcode 定位出所在桶。
  • 如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等，如果相等则进行覆盖。
  • 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
  • 如果桶是空的，说明当前位置没有数据存入，新增一个 Entry 对象写入当前位置。
  • 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
  • 当调用 addEntry 写入 Entry 时需要判断是否需要扩容。
• get 方法
  • 首先也是根据 key 计算出 hashcode，然后定位到具体的桶中。
  • 如果桶为空则直接返回 null 。
  • 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
  • 如果第一个不匹配，则判断它的下一个是红黑树还是链表。红黑树就按照树的查找方式返回值，不然就按照链表的方式遍历匹配返回值。
• 扩容：
  • capacity：默认大小16，必须保证为 2 的 n 次方（为什么？求模运算用了 & 优化，index = (n - 1) & hash）
  • threshold = size * loadFactor：装载因子（能够使用的百分比）* 所有元素的数量
  • 扩容后要重新调整数据在桶的位置，桶的数量变了 --> index 也变了 --> 重新拉链法
• JDK1.8 开始，一个桶的链表长度大于 8 时会将链表为红黑树
• HashTable
  • 使用 synchronized 来进行同步，不能插入 null 键
  • 迭代器是 fail-fast 迭代器（modCount）

⑥ ConcurrentHashMap

• 分段锁（Segment）：采用分段锁，每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度为锁的个数）
• Segment 继承 ReentrantLock，默认 16 个，每个 segment 维护一个 count 统计下面个数。size 操作会计算所以 count 和，先不加锁，不行再锁（重试过多）。
• JDK1.8 抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性 。

下一篇

安卓面试总结（3）——Java 多线程I