Java集合框架

目录
1.Java集合框架常用api类图
2.Java集合框架特性图
3.RandomAccess、Cloneable、Serializable接口
---- 3.1 RandomAccess
---- 3.2 Cloneable
---- 3.3 Serializable
4.Java集合框架介绍
---- 4.1 List
-------- 4.1.1 ArrayList
-------- 4.1.2 Vector 和 Stack
-------- 4.1.3 LinekedList
-------- 4.1.4 Queue 和 Deque
---- 4.2 Set
-------- 4.2.1 HashSet
-------- 4.2.2 LinkedHashSet
-------- 4.2.3 TreeSet
---- 4.3 Map
-------- 4.3.1 HashMap
-------- 4.3.2 HashTable
-------- 4.3.3 TreeMap
-------- 4.3.4 TreeMap
-------- 4.3.5 ConCurrentHashMap

1.Java集合框架常用api类图

image

2.Java集合框架特性图

image

3.RandomAccess, Cloneable,Serializable接口

3.1 RandomAccess

随机访问 的标记接口;

表明实现这个这个接口的 List 集合是支持 快速随机访问 的；一般基于数组的集合实现类，都会实现此接口；

3.2 Cloneable

克隆 的标记接口;

只有实现这个接口后，然后在类中重写Object中的clone方法，然后通过类调用clone方法才能克隆成功，如果不实现这个接口，则会抛出CloneNotSupportedException(克隆不被支持)异常；Java集合的所有实现类一般都已实现了此接口；

3.1 Serializable

序列化 的标记接口；

一个对象序列化的接口，一个类只有实现了Serializable接口，它的对象才能被序列化；

• 什么是序列化

  把对象转换为字节序列的过程称为对象的序列化;

  把字节序列恢复为对象的过程称为对象的反序列化;

• 为什么需要序列化

  当需要把对象的状态信息通过网络进行传输，或者需要将对象的状态信息持久化，以便将来使用时都需要把对象进行序列化;

  在序列化时会有一个 serialVersionUID 生成，这个id会用于反序列化检测；

4. Java 集合框架介绍

4.1 List

Java 的 List 是非常常用的数据类型, 是有序的 Collection , 一种有序的线性结构; 常用的实现类的 ArrayList, LinkedLis t和 Queue;

4.1.1 ArrayList

基于数组实现的, 它允许对元素进行快速随机访问; 当数组大小不满足时, 会对数组进行扩容, 然后将旧数组的中元素复制到一个新的数组对象中, 每次扩容为原大小的1.5倍;

当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高; 因此，ArrayList适合随机查找和遍历，不适合插入和删除;

4.1.2 Vector 和 Stack

Vector 与 ArrayList 一样, 也是通过数组实现的, 但是 Vector 中的所有操作函数都加了synchronized 关键字, 所以它是线程安全的; 同样的它也因此导致效率较低;

Stack 继承 Vector , 是基于数组实现的栈, 同样的也是线程安全的, 但这种同步方式导致效率低下;

4.1.3 LinkedList

基于链表实现的, 适合数据的动态插入和删除，随机访问和遍历速度(需要从头指针开始)比较慢;

LinkedList 还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用 (也就是基于链表实现的队列和栈);

4.1.4 Queue 和 Deque

单端队列与双端队列接口, 具体实现方式可以是数组, 也可以是链表;

4.2 Set

Set 是元素不能重复的无序集合, 不同的实现类具有不同实现方式, 元素唯一性是通过 hashCode() 和equals() 两个函数来决定的;

4.2.1 HashSet

HashSet 是基于哈希表结构实现的, 也就是一个 key-value 的键值对, 只不过 value 为NULl;

哈希表结构图如下(数组+链表, 数组里面存链表):

哈希表.png

哈希表保证元素唯一依赖于 hashCode() 和 equals() 方法, 其方式如下:

• 当哈希表结构的集合添加元素时, 会先调用元素的 hashCode() 方法计算哈希值, 然后把这个哈希值经过 ^ 或者 & 或者位运算 (jdk版本不同方式不一样) 拿到一个 index 值, 也就是数组索引;
• 如果此 index 索引处没有元素则直接加入;
• 如果此 index 索引处有元素:
  • 调用该元素的 equals() 方法与该 index 索引处链表上的所有元素进行一一比较;
  • 如果该 index 索引处的链表上有任意一个元素与该元素相等, 那么就不存储;
  • 如果该 index 索引处的链表上没有一个元素与该元素相等, 那么就存到此链表头或尾 (与jdk版本有关);

4.2.2 LinkedHashSet

LinkedHashSet 是基于链表+哈希表 , 是在 HashSet 的基础上多加了一个链表维护元素的存取顺序;

4.2.3 TreeSet

TreeSet 是基于红黑树存储的 value 为 NUll 的链值对, 同样通过 HashCode 与 equals 方法保证元素唯一, 但它没有哈希碰撞; 使用元素的 自然顺序 或 指定的排序方式 对元素进行排序, 无法记录元素的加入顺序;

4.3 Map

Key-Value链值对双列集合的顶层父接口;

4.3.1 HashMap

HashMap 在 jdk 1.8以后基于 数组+链表+红黑树 实现;

HashMap的结构图如下:

HashMap.png

• HashMap保证元素唯一的方式 (与HashSet类似, 实际上 HashSet 依赖于HashMap) 同样依赖于 hashCode() 和 equals() 方法;
• HashMap 保证是的 key 唯一, 但是 value 值是可以重复的;
• HashMap 存储元素
  • 前半部分与 HashSet 基于相同, 通过 key 元素计算出 hash值, 再通过 hash 值得到索引;
  • 如果索引处没有元素, 则直接存入;
  • 如果索引处有元素, 则通过 equals 方法 比较链表上 key 的值;
    • 如果 key 值也相同则直接覆盖;
    • 如果 key 值不相同:
      • 如果此索引处链表上的元素个数是等于 7 个, 那么此链表会转为红黑树存储;
      • 如果超过 8 个会扩容 ;
      • 如果此索引处链表上的元素个数小于7个, 那么新元素会直接添加到表尾 ;
• HashMap 的扩容
  • capacity：当前数组容量, 始终保持 2^n, 可以扩容, 扩容后数组大小为当前的 2 倍;
  • loadFactor：负载因子, 默认为 0.75;
  • threshold：扩容的阈值, 等于 capacity * loadFactor;
  • 比如当有一个 数组大小为 16 的 HashMap, 那么存储的实际元素数量大于160 x 0.75 = 12 时就会扩容, 扩容之后新的数组大小为 32, 新的扩容阈值为24, 扩容之后所存储元素的数组索引会通过 reHash 重新分布, 这么做的目的是为了保证HashMap 性能;
  • 当 HashMap 中的数组大小扩容到 64 时, 索引处上的链表元素个数为小于等于6个会重新转为链接存储, 大于 6 个就会再转为红黑树并扩容;
  • HashMap 这么设计的原因, 是为了提高查找效率, 因为链表只能从头指针处开始遍历一个一个的查找;

4.3.2 HashTable

线程安全的 HashMap 也是在操作函数上加了 synchronized 关键字

4.3.3 LinekdHashMap

LinekdHashMap 是基于链表 + 哈希表 , 是在 HashMap 的基础上多加了一个链表维护元素的存取顺序;

4.3.4 TreeMap

基于红黑树, 无法保证存取顺序, 但可以对元素的键 进行排序，排序方式有两种:自然排序和 按指定方式排序；

4.3.5 ConCurrentHashMap

线程安全的 HashMap, 采用 分段锁 思想; 其结构图如下:

ConCurrentHashMap.png

ConCurrentHashMap 是在 Segment 数组中, 每一个数组元素都存一个HashMap 然后对 Segment数组中的每个 Segment 对象进行加锁;

这么设计的目的是为了提高并发能力, 可扩容的部分是 Segment 数组中所存储的 HashMap; 也就是说并发能力有限, Segment 的数组长度就是最大锁的数量, 也是可支持的最大并发数;