Java 集合框架主要分为两种：集合类（Collection）和 图类（Map）。

Collection

Collection.png

List

有序可重复

  • Vector—— 线程安全

Vector 是 Java 早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的
数组，并拷贝原有数组数据。

  • ArrayList—— 线程不安全

ArrayList 是应用更加广泛的 动态数组 实现，它本身不是线程安全的，所以性能要好很多。与 Vector 近似，
ArrayList 也是可以根据需要调整容量，不过两者的调整逻辑有所区别，Vector 在扩容时会提高 1 倍，而
ArrayList 则是增加 50%。

  • LinkedList—— 线程不安全

LinkedList 顾名思义是 Java 提供的 双向链表，所以它不需要像上面两种那样调整容量，也不是线程安全的。

Set

无序唯一

  • HashSet

底层数据结构是哈希表。(无序,唯一)
如何来保证元素唯一性?
依赖两个方法：hashCode() 和 equals()

  • LinkedHashSet

底层数据结构是链表和哈希表。(FIFO插入有序,唯一)

  • TreeSet

底层数据结构是 红黑树。(唯一，有序)
1. 如何保证元素排序的呢?
自然排序
比较器排序
2.如何保证元素唯一性的呢?
根据比较的返回值是否是 0 来决定

Queue/Deque

是 Java 提供的标准队列结构的实现，除了集合的基本功能，它还支持类似先入先出（FIFO， First-in-First-Out）或者后入先出（LIFO，Last-In-First-Out）等特定行为

  • LinkedList—— 线程不安全

LinkedList 顾名思义是 Java 提供的 双向链表，所以它不需要像上面两种那样调整容量，也不是线程安全的。

Map

Map.png

HashMap

无序，线程不安全

HashTable

无序，线程安全，不允许为 null 值

TreeMap

有序

SparseArray

在 Android 开发时，我们使用的大部分都是 Java 的 api，比如 HashMap，使用率非常高，但是对于 Android 这种对内存非常敏感的移动平台，很多时候使用一些 java 的 api 并不能达到更好的性能，相反反而更消耗内存，所以针对 Android 这种移动平台，也推出了更符合自己的 api，比如 SparseArray、ArrayMap 用来代替 HashMap 在有些情况下能带来更好的性能提升。
image.png
image.png

常见问题

ArrayList 源码

  • 扩容
    • ArrayList 的初始大小是 0，然后，当 add 第一个元素的时候大小则变成 10
    • oldCapacity >> 1 右移运算符，原来长度的一半，再加上原长度也就是每次扩容是原来的 1.5 倍

image.png

  • 线程不安全

HashMap 源码

推荐阅读

模型

它可以看作是数组（Node[] table）和 链表 结合组成的复合结构，数组被分为一个个桶（bucket），通过哈希值决定了键值对在这个数组的寻址；哈希值相同的键值对，则以链表形式存储，你可以参考下面的示意图。这里需要注意的是，如果链表大小超过阈值（TREEIFY_THRESHOLD, 8），图中的链表就会被改造为 树形 结构。

✍🏽 集合 - 图6
bucket + 链表/红黑树

  • 哈希桶数组 table 存放 Node 把任意长度的 输入 通过散列算法转换为固定的长度
  • 多个 key 定位到的位置相同( hash 碰撞)，会导致时间复杂度的提升
      1. 增大哈希桶数组的长度 —— 扩容
      1. 设计更好的 hash 算法
  • 一旦链过长，会严重影响性能
    • 树化（链表转红黑树）

当链表长度超过8 && 数组长度不小于 64，链表转为红黑树
利用红黑树快速增删查的特点提高性能

核心概念

  • Hash

把任意长度的 输入 通过散列算法转换为固定的长度

  • 初始化容量（capacity）

默认 16

  • 负载因子（load factor）

默认 0.75

  • 阈（yù ）值

HashMap 容量 * 负载因子，

  • 扩容

大于阈值则需扩容，扩容后的容量为 原来的两倍

  • 树化

当 链表长度超过 8 && 数组长度不小于 64，链表转为红黑树（红黑树快速增删查（O(log2(N))））

  • putVal()
  • resize()

jdk 1.7 与 1.8 区别

链表的插入方式

- 1.7 头插法
- 1.8 尾插法（避免逆序链表死循环问题）
扩容后的数据位置

- 1.7 hash值 & length-1
- 1.8
- 新增运算位为 0 ：原位置
- 新增运算位为 1：原位置 + 扩容大小
- 不必每次进行计算
扩容插入时机

- 1.7 扩容后插入
- 1.8 扩容前插入

✍🏽 集合 - 图7

SparseArray 源码

核心

  • 使用两个数组，一个 int 数组作为 key，一个 Object 数组作为 value
  • 默认初始化长度 10
  • 避免了自动拆装箱
  • key 按序排列
  • 插入和添加时使用二分查找
  • 延迟删除

delete/remove

image.png

get

image.png

set/put

image.png

HashTable 与 ConcurrentHashMap

  • HashTable 所有方法都加锁，可以不许为空