写在前面
之前我们大概学习了集合类的相关知识。了解了一下基本的结合类和其中的一些方法。
但是，对于集合类的性能，并没有进行深入探究。接下来的这一章将对集合框架中具体的实现类进行深入了解。
7.2 集合框架与 ArrayList
这里先了解一下集合框架。其实集合框架还是比较复杂的，里面有非常复杂的继承、实现关系等等。先贴一张图上来。这个图看的人头晕，很正常。
Java 集合框架全家福
主要先记住每个接口的几个重要实现类。
1. List
- ArrayList
- LinkedList
- Vector（Stack就是 Vector 的子类）
2. Map
- HashMap
- LinkedHashMap
- HashTable
- TreeMap
3. Set
- HashSet
- TreeSet
- LinkedHashSet
ArrayList 可变长数组类
- List接口的 可变数组的实现。
- 非线程安全（多线程访问需要同步）
- 底层使用数组来实现
- 适合查改，弱于增删
这里作者带我们看了一下ArrayList的几种方法的底层实现。其中元素更改和查询方法都很简单，然而 add() 、remove() 方法由于要调用 System.arraycopy() 方法，效率比较低。所以才是，上面说的适合改查，弱于增删。
数组扩充，这里介绍了ArrayList内部使用的 ensureCapacity() 方法，这个方法是用来判断一个 index 是否满足目前最大长度要求，不满足则按照 1.5 倍扩容。
7.3 LinkedList 双端队列类
-
List接口的链接列表实现。
-
实现 Deque 接口，为 add / poll 提供 FIFO 操作 以及 其他 堆栈和双端队列操作。
-
非线程安全的
-
底层数据结构基于双向循环链表，头结点中不存放数据。
LinkedList 数据结构
-
适合增删，弱于改查
然后作者介绍了 LinkedList 类中几个常用方法的实现原理。用来说明，LinkedList 的特性为何如此。
- 获取双端队列的某个节点
在 LinkedList 双端队列的数据结构中，根据 index 来获取某个节点，是需要遍历的，不过由于是双端的，所以最多只需要遍历 size/2 即可。
这就是为什么弱于改查
- addBefore() 方法
即在某个节点前插入新的节点。
这里可以看到跟上面的 ArrayList 不同，这里添加时候，不需要进行 copy 操作，所以才是 适合增删。
7.4 HashMap & HashTable
HashMap
- 基于哈希表的 Map 接口实现
- 非线程安全
- 不保证映射顺序
首先要了解一下 HashMap 的数据结构。为了避免 hash 冲突问题，HashMap采用了 数组+链表 的存储方式 。
可以这么理解，HashMap 的主体是一个 Entry<key,value> 数组。数组的每一项又是一个单链表。
数组的大小必须是 2^n。为了尽量减少 hash 碰撞。为什么会碰撞
HashMap 的数组+链表的数据结构
将 hash值相同的的元素放到一个链表中。
然后作者讲了一下 get() & put() 方法。没什么特殊的。
扩容：
要理解扩容，就要理解 初始容量&加载因子。 前者是 HashMap 中，数组的长度，后者是在扩容前可以达到多满。比如（100,0.75），那么就是说当 HashMap 长度达到 100*0.75 = 75 的时候就要进行扩容操作。扩容使得容量翻倍。
在 jdk 1.8 中，HashMap 的 单链表在长度变大之后，出于性能的考虑，变成了红黑树。
对 HashMap 做一下总结：
- HashMap 存储顺序是无序的。所谓无序就是说，你存的时候是 {1:1,2:2,3:3}，>但是实际上并不是第一个就放 1:1。
- Hash 碰撞是通过拉链法解决的
- 为了减少 Hash 碰撞，长度必须是 2^n
- HashMap 不支持相同的 可以，会覆盖
- put() 方法，先通过 index 计算hash，用hash算出数组中的 index，然后遍历 >index所在的链表，如果有相同的 key 存在，更新；否则，插入到表头。时间复杂>度是 O(n)
- get() 方法。同上。O(n)
- 从上面的 put() 和 get() 方法就可以看出，线程不安全。
HashTable
- 存储机制和 HashMap 一致
- 不允许有 null 存在
- 线程安全
- 迭代器有强一致性
不知道这一条在说什么
7.5 TreeMap 和 LinkedHashMap
TreeMap
- Map接口的树实现
- 不允许有 null 存在
- 非线程安全
- 键值有序
TreeMap 数据结构是红黑树。可以在 O(logn)时间内做到查找和删除。
Entry 是红黑树的节点，其包含了 key、value、left、right、parent、color.
TreeMap 与 HashMap比较
- 空间利用率高
- HashMap 为了减少 Hash 碰撞，长度必须是 2^n，TreeMap 不用。
- TreeMap 中每一个节点就代表一个元素
- 性能好
- HashMap 中的 Hash 碰撞会提高查询开销
- HashMap 扩容的时候需要 rehash，开销
- TreeMap 所有操作都可以在 O(logn) 内完成
LinkedHashMap
之前一个小节中，我们学习了 HashMap，知道 HashMap 存数据是无序的，当希望可以有序的存储 key-value 的时候，就需要用 LinkedHashMap 了。
- Map 接口的 哈希表和链接列表实现，允许使用 null 的 key&value
- 非线程安全
- 可预知的迭代顺序
总结一下LinkedHashMap：
- LinkedHashMap 继承自 HashMap。
- LinkedHashMap有序。
- LinkedHashMap线程不安全。
好了，看了这么多 Map 接口的实现类。对其适用范围做一个小小的总结：
- HashMap适用于一般的 key. value 映射需求
- HashTable 适用于多线程
- TreeMap 适用于按照key 排序的迭代场合
- LinkedHashMap适用于特殊顺序迭代场合（LRU算法）
7.6 HashSet
对于 Set 接口，其特性就是不含重复元素。
这里主要看一下 HashSet 这个实现类
- 允许 null 元素
- 不保证 set 的迭代顺序
HashSet 的底层使用 HashMap 来实现的。
LinkedHashSet 底层使用 LinkedHashMap 实现
TreeSet 使用 TreeMap 实现
总结一下，Set 接口的实现类都是建立在 Map接口的相关实现类上实现的。因此具有近似的使用特性。
网友评论