声明: 1. 本文为我的个人复习总结, 并非那种从零基础开始普及知识 内容详细全面, 言辞官方的文章
2. 由于是个人总结, 所以用最精简的话语来写文章
3. 若有错误不当之处, 请指出
有序 & 无序:
List是有序的, Set和Map是无序的;
这里的顺序指的不是元素添加顺序, 而是添加方式: Set/Map的话被Hash散列到哪个桶位置是无规律无序的, 而List是一定会被添加到链表尾
TreeSet(基于红黑树实现)对元素进行大小升序排序(元素本身具有可比较性),
LinkedHashSet使用额外的指针来记录元素的添加顺序, 但依旧都是无序的
如果添加了相同key的key-value对, 则key不变, 而value被覆盖
TreeMap是按key进行比较的
Iterable接口(Collection的祖先)里有一个方法, 叫做Iterator<T> iterator( ); // 迭代器
遍历时的坑:
迭代器遍历时, 不要修改增删集合的元素, 否则会报并发修改异常ConcurrentModificationException,
比如遍历ArrayList集合期间删除了元素 导致modCount != expectedModCount
这里的并发并非是线程并发, 而是指一边遍历一遍修改
要是想不报错, 即忽略迭代器 和 实际集合的元素数量不相等, 就使用CopyOnWriteArrayList;
仅仅是不报错而已, 迭代器并不能感知到新加的元素
构造方法:
扩容规则:
数组扩容本质是 new一个新数组, 然后再把旧数组的值拷贝进去
add(Object o):
addAll(Collection c):
ArrayList没有元素时,扩容为max(10, 实际元素个数)
ArrayList有元素时, 扩容为max(原容量 1.5 倍, 实际元素个数)
LinkedList
ArrayList
树化的意义:
红黑树用来避免 DOS 攻击,防止链表超长时性能下降;
TreeNode占用空间较大,如非必要的话尽量还是使用链表
树化应当是极少的偶然情况,是保底策略
hash 值如果足够随机,则在 hash 表内按泊松分布; 在负载因子 0.75 的情况下,长度超过 8 的链表出现概率是 0.00000006; 树化阈值选择 8 就是为了让树化几率足够小
树化的规则:
当链表长度超过树化阈值 8 时,先尝试扩容来减少链表长度;
如果数组容量已经 >=64,才会进行树化
退化规则:
在扩容时如果拆分树时,树元素个数 <= 6 则会退化链表
先计算对象的 hashCode( )
再调用 HashMap 的 hash( ) 方法进行二次哈希, 这是是为了让哈希分布更为均匀;
比如相邻的Integer整数的哈希码就相邻很近, 就没有很好的散列性了
**容量大小是2^n个的副作用: **散列性不好,所以需要二次 hash 来作为补偿
容量大小是质数时, 对质数求模的散列性较高(如.Net的Dictionary类)
Hashtable没有采用二次哈希, 也不是质数, 而是新容量=2倍旧容量+1; 散列性 没质数好, 但比2^n偶数好
最后 & (capacity – 1) 求模得到索引
HashMap 是懒惰创建数组的,首次使用才创建数组, 默认是16
如果是指定数组容量, 则会选择一个 最接近且≥指定容量的2^n的数字作为容量
计算索引(桶下标)
如果桶下标还没人占用,创建 Node 占位
如果桶下标已经有人占用
返回前检查容量是否超过阈值(总Node个数达到容量的3/4),一旦超过则进行扩容
概念: 两个Key散列后落在了同一个桶下标位置
解决办法:
扩容规则:
扩容时新容量是旧容量的2倍
扩容时元素位置的变化: 1.8 在扩容时的计算Node的索引时会优化: hash( )后的值 & 旧容量== 0 的元素留在原来位置, 否则新位置 = 旧位置 + 旧容量
并发死链问题(1.7才存在):
由于1.7的头插, 每次扩容后链表都会逆序, 容易在并发场景造成环状死链问题
并发数据覆盖问题(1.7,1.8都存在):
A线程计算得到索引1的位置没有元素, 刚准备占位但还没来得及占;
这时B线程也发现了索引1的位置没有元素, 然后也刚准备占位但还没来得及占;
切到A线程放了K-V对, 再切到B线程放K-V对时, 覆盖了A线程刚放的K-V对
Map里key 的设计要求:
HashMap 的 key 可以为 null,但Map的其他实现类并不允许key为null
作为 key 的对象, 必须实现 hashCode( ) 和 equals( ),
key 的内容不能修改;
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