引言
第三天卡...
今天主要看了下 java 容器方面的知识, 很累但是很充实. 吃两把鸡去了, 休息一下, 再战.
开始
-Collection 存储对象的集合; Map 存储键值对的映射表
-Iterator(迭代器模式)
- 集合访问器, 用于循环访问集合中的对象
- 所有实现了 Collection 接口的容器类都有 iterator 方法, 用于返回一个实现了 Iterator 接口的对象. Iterator 对象称作迭代器, Iterator 接口方法能以迭代方式逐个访问集合中
各个元素, 并可以从 Collection 中除去适当的元素
- -Collection
- -set(特征: 无序且不可重复)
-TreeSet: 基于红黑树实现, 支持有序性操作, 例如根据一个范围查找元素的操作. 但是查找效率不如 HashSet,HashSet 查找的时间复杂度为 O(1),TreeSet 则为
O(logN).
-HashSet: 基于哈希表实现, 支持快速查找, 但不支持有序性操作. 并且失去了元素的插入顺序信息, 也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的
-LinkedHashSet: 具有 HashSet 的查找效率, 且内部使用双向链表维护元素的插入顺序
- 红黑树: 漫画看懂红黑树 链接: https://www.sohu.com/a/201923614_466939
-list(特征: 有序且可重复)
-ArrayList: 基于动态数组实现, 支持随机访问.
- 概览
- 实现了 RandomAccess 接口, 因此支持随机访问. 这是理所当然的, 因为 ArrayList 是基于数组实现的, 其数组的默认大小为 10.
- 序列化
- 基于数组实现, 并且具有动态扩容特性, 因此保存元素的数组不一定都会被使用, 那么就没必要全部进行序列
transient Object[] A; //transient 关键字声明数组默认不会被序列化
- 为什么定义 A 数组要用 transient 关键字修饰, 使其默认不被序列化?
假如现在实际有了 5 个元素, 而 elementData 的大小可能是 10, 那么在序列化时只需要储存 5 个元素, 数组中的最后五个元素是没有实际意义的, 不需要储
存. 所以 ArrayList 的设计者将 elementData 设计为 transient, 然后在 writeObject 方法中手动将其序列化, 并且只序列化了实际存储的那些元素, 而不是整
个数组
- 序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出. 而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射
调用该对象的 writeObject() 来实现序列化. 反序列化使用的是 ObjectInputStream 的 readObject() 方法, 原理类似.
-java 中序列化的目的:
- 以某种存储形式使自定义对象持久化;
- 将对象从一个地方传递到另一个地方.
- 使程序更具维护性
- 扩容
- 添加元素时使用 ensureCapacityInternal() 方法来保证容量足够, 如果不够时, 需要使用 grow() 方法进行扩容, 新容量的大小为 oldCapacity + (oldCapacity
>> 1), 也就是旧容量的 1.5 倍
- 扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中, 这个操作代价很高, 因此最好在创建 ArrayList 对象时就指定大概的容量大小, 减少扩容操作
的次数
- 删除元素
- 需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上, 该操作的时间复杂度为 O(N), ArrayList 删除元素的代价是非常高的.
-fail-fast
-modCount 用来记录 ArrayList 结构发生变化的次数. 结构发生变化是指添加或者删除至少一个元素的所有操作, 或者是调整内部数组的大小, 仅仅只是设置元
素的值不算结构发生变化
- 在进行序列化或者迭代等操作时, 需要比较操作前后 modCount 是否改变, 如果改变了需要抛出 ConcurrentModificationException.
-fail-fast 与 fail-safe
-fail-fast
-fail-fast 机制在遍历一个集合时, 当集合结构被修改, 会抛出 ConcurrentModificationException.
-java.util 包下的集合类都是快速失败的, 不能在多线程下发生并发修改(迭代过程中被修改).
-fail-safe
-fail-safe 任何对集合结构的修改都会在一个复制的集合上进行修改, 不像 fail-fast 在原集合上修改, 因此不会抛出 ConcurrentModificationException
-java.util.concurrent 包下的容器都是安全失败, 可以在多线程下并发使用, 并发修改.
- 优点
- 避免了 ConcurrentModificationException
- 缺点
- 需要复制集合, 产生大量的无效对象, 开销大
- 无法保证读取的数据是目前原始数据结构中的数据.
- 迭代器并不能访问到修改后的内容, 即: 迭代器遍历的是开始遍历那一刻拿到的集合拷贝, 在遍历期间原集合发生的修改迭代器是不知道的.
-Vector: 和 ArrayList 类似, 但它是线程安全的.
- 它的实现与 ArrayList 类似, 但是使用了 synchronized 进行同步. 因此是线程安全的
- 与 ArrayList 比较
-Vector 是同步的, 因此开销就比 ArrayList 要大, 访问速度更慢. 最好使用 ArrayList 而不是 Vector, 因为同步操作完全可以由程序员自己来控制;
-Vector 每次扩容请求其大小的 2 倍空间, 而 ArrayList 是 1.5 倍.
-LinkedList: 基于双向链表实现, 只能顺序访问, 但是可以快速地在链表中间插入和删除元素. 不仅如此, LinkedList 还可以用作栈, 队列和双向队列.
- 概览
- 基于双向链表实现, 使用 Node 存储链表节点信息.
- private static class Node<E> {
- E item;
- Node<E> next;
- Node<E> prev;
- }
每个链表存储了 first 和 last 指针
- transient Node<E> first;
- transient Node<E> last;
- 与 ArrayList 的比较
-ArrayList 基于动态数组实现, LinkedList 基于双向链表实现;
-ArrayList 支持随机访问, LinkedList 不支持;
-LinkedList 在任意位置添加删除元素更快.
-Map
-TreeMap: 基于红黑树实现
-HashMap: 基于哈希表实现.
- 存储结构
- 内部包含了一个 Entry 类型的数组 table.
transient Entry[] table;
Entry 存储着键值对. 它包含了四个字段, 从 next 字段我们可以看出 Entry 是一个链表. 即数组中的每个位置被当成一个桶, 一个桶存放一个链表. HashMap 使
用拉链法来解决冲突, 同一个链表中存放哈希值相同的 Entry.
- 拉链法的工作原理
- HashMap<String, String> map = new HashMap<>();
- map.put("K1", "V1");
- map.put("K2", "V2");
- map.put("K3", "V3");
新建一个 HashMap, 默认大小为 16;
插入 <K1,V1> 键值对, 先计算 K1 的 hashCode 为 115, 使用除留余数法得到所在的桶下标 115%16=3.
插入 <K2,V2> 键值对, 先计算 K2 的 hashCode 为 118, 使用除留余数法得到所在的桶下标 118%16=6.
插入 <K3,V3> 键值对, 先计算 K3 的 hashCode 为 118, 使用除留余数法得到所在的桶下标 118%16=6, 插在 <K2,V2> 前面.
- 应该注意到链表的插入是以头插法方式进行的, 例如上面的 <K3,V3> 不是插在 <K2,V2> 后面, 而是插入在链表头部.
- 查找需要分成两步进行:
- 计算键值对所在的桶;
- 在链表上顺序查找, 时间复杂度显然和链表的长度成正比.
-put 操作
-HashMap 允许插入键为 null 的键值对. 但是因为无法调用 null 的 hashCode() 方法, 也就无法确定该键值对的桶下标, 只能通过强制指定一个桶下标来存放.
HashMap 使用第 0 个桶存放键为 null 的键值对.
- 确定桶下标
- 扩容
- 基本原理
- 重新计算桶下标
- 计算数组容量
- 链表转红黑树
- 从 JDK 1.8 开始, 一个桶存储的链表长度大于 8 时会将链表转换为红黑树
- 与 HashTable 的比较
HashTable 使用 synchronized 来进行同步.
HashMap 可以插入键为 null 的 Entry.
HashMap 的迭代器是 fail-fast 迭代器.
HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的.
-HashTable: 和 HashMap 类似, 但它是线程安全的, 这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致. 它是遗留类, 不应该去使用它. 现
在可以使用 ConcurrentHashMap 来支持线程安全, 并且 ConcurrentHashMap 的效率会更高, 因为 ConcurrentHashMap 引入了分段锁.
-LinkedHashMap: 使用双向链表来维护元素的顺序, 顺序为插入顺序或者最近最少使用 (LRU) 顺序.
来源: https://www.cnblogs.com/yonyong/p/9534972.html