安卓面试总结（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 类似，但是线程安全的，可用 ConcurrentHashMapLinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序，或者是最近最少使用顺序（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 记录结构变化，迭代、序列化时检查 --> ConcurrentModificationExceptiontransient：标记数组，只对数组内有的值进行序列化（手动 *** 作） ② 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 来保证并发安全性 。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/web/2990146.html