共计 2392 个字符，预计需要花费 6 分钟才能阅读完成。
1.List
1.1 Arraylist 与 LinkedList 区别
- 是否保证线程安全：ArrayList 和 LinkedList 都是不同步的，也就是 不保证线程安全；
- 底层数据结构：Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构
- 插入和删除是否受元素位置的影响：① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行 add(E e)方法的时候，ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作。② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
- 是否支持快速随机访问：LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象 (对应于 get(int index) 方法)。
- 内存空间占用：ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
注意:
ArrayList 遍历时使用普通 for 循环较快.
LinkedList 遍历时使用迭代器较快.
1.2 List 中的迭代器
| for(Object obj : list){list.remove(obj) | |
| } |
| 注意: | |
| 一般 list 中迭代器不能使用此种方法移除元素, 会触发 ConcurrentModifyException, 如果要删除可以使用 Iterator.remove() | |
| 此处如果切换成 CopyOnWriteArrayList 则可以正常删除 |
1.3 ArrayList 的扩容机制
详见: https://github.com/Snailclimb…
Map
2.1 Java1.8 底层实现
底层 = 数组 + 链表(大小超过 8, 转换为红黑树)
HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n – 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法, 换句话说使用扰动函数之后可以减少碰撞。
| //hash 方法 | |
| static final int hash(Object key) { | |
| int h; | |
| // key.hashCode()：返回散列值也就是 hashcode | |
| // ^：按位异或 | |
| // >>>: 无符号右移，忽略符号位，空位都以 0 补齐 | |
| return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 扰动函数进行处理 | |
| } |
2.2 HashMap 长度为什么是 2 的幂次方
一般用 hash 对 map 的长度取模使用, 当且仅当 length 是 2 的幂次方时,hash%length==hash&(length-1)成立, 这样的话位与比取模 % 运算要更快
2.3 HashMap 线程不安全问题
HashMap 不是线程安全的类, 两个线程同时去 put 可能引起数据不一致, 在 1.7 以前还存在闭链问题,1.8 以后解决了这个问题, 并发环境下建议使用 ConcurrentHashMap;
详情参见: https://coolshell.cn/articles…
2.4 HashMap 的其他资料
更详细的资料, 请参见:
https://zhuanlan.zhihu.com/p/…
2.5 ConcurrentHashMap 的基本结构
1. 底层数据结构:
JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组 + 链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组 + 链表 / 红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组 + 链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
2. 实现线程安全的方式:
① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组 + 链表 + 红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。
Set
当你把对象加入 HashSet 时，HashSet 会先计算对象的 hashcode 值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用 equals（）方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。
