声明: 1. 本文为我的个人复习总结, 并非那种从零基础开始普及知识 内容详细全面, 言辞官方的文章
2. 由于是个人总结, 所以用最精简的话语来写文章
3. 若有错误不当之处, 请指出
基础:
- List和Set都是Collection, Map不是Collection
- ArrayList底层是数组, LinkedList底层是双向链表, HashSet底层是HashMap
- LinkedList功能很强, 它同时是Queue和Deque的实现类
有序 & 无序:
List是有序的, Set和Map是无序的;
这里的顺序指的不是元素添加顺序, 而是添加方式: Set/Map的话被Hash散列到哪个桶位置是无规律无序的, 而List是一定会被添加到链表尾
TreeSet(基于红黑树实现)对元素进行大小升序排序(元素本身具有可比较性),
LinkedHashSet使用额外的指针来记录元素的添加顺序, 但依旧都是无序的
如果添加了相同key的key-value对, 则key不变, 而value被覆盖
TreeMap是按key进行比较的
Iterator:
Iterable接口(Collection的祖先)里有一个方法, 叫做Iterator<T> iterator( ); // 迭代器
遍历时的坑:
迭代器遍历时, 不要修改增删集合的元素, 否则会报并发修改异常ConcurrentModificationException,
比如遍历ArrayList集合期间删除了元素 导致modCount != expectedModCount
这里的并发并非是线程并发, 而是指一边遍历一遍修改
要是想不报错, 即忽略迭代器 和 实际集合的元素数量不相等, 就使用CopyOnWriteArrayList;
仅仅是不报错而已, 迭代器并不能感知到新加的元素
ArrayList:
构造方法:
- ArrayList( ) 使用长度为零的数组
- ArrayList(int initialCapacity) 使用指定容量的数组
- public ArrayList(Collection<? extends E> c) 使用c的大小作为数组容量, 并拷贝c的元素
扩容规则:
数组扩容本质是 new一个新数组, 然后再把旧数组的值拷贝进去
-
add(Object o):
- 首次添加元素扩容为 10
- 以后添加元素扩容为上次容量的 1.5 倍
-
addAll(Collection c):
-
ArrayList没有元素时，扩容为max(10, 实际元素个数)
-
ArrayList有元素时, 扩容为max(原容量 1.5 倍, 实际元素个数)
-
LinkedList 对比 ArrayList 的区别:
LinkedList
- 基于双向链表，无需连续内存
- 随机访问慢(要沿着链表遍历)
- 头尾插入删除性能高; 其他部位插入删除性能略低
- 占用内存多, 因为要维护额外的
ArrayList
- 基于数组，需要连续内存
- 随机访问, 根据下标访问时较快; 如果要remove(Object o) 时较慢,因为没用到下标
- 尾部插入、删除性能高; 其它部分插入、删除性能很低, 因为要移动数据
- 可以利用 cpu 缓存+局部性原理, cpu会对访问过的元素以及它附近的元素加到缓存里, 那样下次访问附近元素时会较快
HashMap:
底层数据结构:
- 1.7 数组 + 链表
- 1.8 数组 + （链表 | 红黑树）
树化与退化:
树化的意义:
-
红黑树用来避免 DOS 攻击，防止链表超长时性能下降;
-
TreeNode占用空间较大，如非必要的话尽量还是使用链表
-
树化应当是极少的偶然情况，是保底策略
hash 值如果足够随机，则在 hash 表内按泊松分布; 在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006; 树化阈值选择 8 就是为了让树化几率足够小
树化的规则:
当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度;
如果数组容量已经 >=64，才会进行树化
退化规则:
在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表
- 情况1, 在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表
- 情况2, remove 树节点时，若 root、root.left、root.right、root.left.left 中任意一个为 null，也会退化为链表
索引桶下标计算:
计算方法:
-
先计算对象的 hashCode( )
-
再调用 HashMap 的 hash( ) 方法进行二次哈希, 这是是为了让哈希分布更为均匀;
比如相邻的Integer整数的哈希码就相邻很近, 就没有很好的散列性了
**容量大小是2^n个的副作用: **散列性不好，所以需要二次 hash 来作为补偿
容量大小是质数时, 对质数求模的散列性较高(如.Net的Dictionary类)
Hashtable没有采用二次哈希, 也不是质数, 而是新容量=2倍旧容量+1; 散列性 没质数好, 但比2^n偶数好
-
最后 & (capacity – 1) 求模得到索引
数组容量为何是 2^n
- 计算索引时效率更高：如果是2的n次幂可以使用位与运算代替取模
- 扩容时重新计算索引效率更高： hash( )后的值 & 旧容量== 0 的元素留在原来位置, 否则新位置 = 旧位置 + 旧容量
put 流程
-
HashMap 是懒惰创建数组的，首次使用才创建数组, 默认是16
如果是指定数组容量, 则会选择一个 最接近且≥指定容量的2^n的数字作为容量
-
计算索引（桶下标）
-
如果桶下标还没人占用，创建 Node 占位
-
如果桶下标已经有人占用
- 已经是 TreeNode 走红黑树的添加或更新逻辑
- 是普通 Node，走链表的添加或更新逻辑; 如果链表长度超过树化阈值，走树化逻辑
-
返回前检查容量是否超过阈值(总Node个数达到容量的3/4)，一旦超过则进行扩容
哈希冲突:
概念: 两个Key散列后落在了同一个桶下标位置
解决办法:
- 开放定址法: 发生冲突时就依次往下一个桶下标位置找, 直至找到空位为止
- 再哈希法: 有多个Hash函数, 这个冲突了就用别的备用Hash函数
- 链地址法: 冲突的元素都放在这个桶下标位置, 靠 链表或红黑树 来连接这多个元素
- 建立一个公共溢出区: 将哈希表分为基本表和溢出表两部分, 凡是和基本表发生冲突的元素, 一律填入溢出表
1.7 与 1.8 的区别
- 1.7 是头插法，1.8 是尾插法
- 1.7 是≥阈值 & 此桶下标位置已有元素时 扩容，而 1.8 是>阈值时扩容
- 1.8 在扩容时的计算Node的索引时会优化
扩容因子为何是 0.75?
- 在 空间占用 与 查询时间 之间取得较好的折中权衡
- 大于这个值，空间节省了，但链表就会比较长影响性能
- 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多
扩容规则:
扩容时新容量是旧容量的2倍
扩容时元素位置的变化: 1.8 在扩容时的计算Node的索引时会优化: hash( )后的值 & 旧容量== 0 的元素留在原来位置, 否则新位置 = 旧位置 + 旧容量
并发问题:
并发死链问题(1.7才存在):
由于1.7的头插, 每次扩容后链表都会逆序, 容易在并发场景造成环状死链问题
- e 和 next 都是局部变量，用来指向当前节点和下一个节点
- 线程1的临时变量e和next刚引用了这俩节点，还未来得及移动节点，发生了线程切换，由线程2完成扩容和迁移
- 线程2 扩容完成，由于头插法，链表顺序颠倒。但线程1的临时变量e和next还引用了这俩节点，还要再来一遍迁移, 形成了死链
并发数据覆盖问题(1.7,1.8都存在):
A线程计算得到索引1的位置没有元素, 刚准备占位但还没来得及占;
这时B线程也发现了索引1的位置没有元素, 然后也刚准备占位但还没来得及占;
切到A线程放了K-V对, 再切到B线程放K-V对时, 覆盖了A线程刚放的K-V对
key 的设计:
Map里key 的设计要求:
-
HashMap 的 key 可以为 null，但Map的其他实现类并不允许key为null
-
作为 key 的对象, 必须实现 hashCode( ) 和 equals( ),
-
key 的内容不能修改;
- 会导致map中出现了相同的key
- 会导致再次查询时就查询不到数据了, 因为hashCode变了, 计算桶下标时就可能会找错桶
put时会计算索引位置, 会查看key的值; 而put进map集合后, 对于key的变化 map就感知不到了
-
key 的 hashCode 应该有良好的散列性, 使均匀分布
String 对象的 hashCode( ) 设计, 为啥每次都是乘31?
字符串中的每个字符都可以表现为一个数字，称为 S_i，其中 i 的范围是 [0, n-1]
散列公式为： S_0∗31^(n-1)+ S_1∗31^(n-2)+ … S_i ∗ 31^(n-1-i)+ …S_(n-1)∗31^0
目标: 达到较为均匀的散列效果, 每个字符串的 hashCode 足够独特;
-
为了增大散列性: 31是质数, 有较好的散列特性
-
为了提高计算效率: 31接近2^5, 2^n可以用移位操作, 所以31 * h 可以被优化为 (h<<5)-h