Arraylist 与 LinkedList 异同
补充: 数据结构基础之双向链表
ArrayList 与 Vector 区别
HashMap 的底层实现
JDK1.8 之前
JDK1.8 之后
HashMap 和 Hashtable 的区别
HashMap 的长度为什么是 2 的幂次方
HashMap 多线程操作导致死循环问题
HashSet 和 HashMap 区别
ConcurrentHashMap 和 Hashtable 的区别
ConcurrentHashMap 线程安全的具体实现方式 / 底层具体实现
- JDK1.7(上面有示意图)
- JDK1.8 (上面有示意图)
集合框架底层数据结构总结
- Collection
- 1. List
- 2. Set
- Map
Arraylist 与 LinkedList 异同
1. 是否保证线程安全: ArrayList 和 LinkedList 都是不同步的, 也就是不保证线程安全;
2. 底层数据结构: Arraylist 底层使用的是 Object 数组; LinkedList 底层使用的是双向链表数据结构(JDK1.6 之前为循环链表, JDK1.7 取消了循环. 注意双向链表和双向循环链表的区别:); 详细可阅读 JDK1.7-LinkedList 循环链表优化 https://www.cnblogs.com/xingele0917/p/3696593.html
3. 插入和删除是否受元素位置的影响: 1 ArrayList 采用数组存储, 所以插入和删除元素的时间复杂度受元素位置的影响. 比如: 执行 add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾, 这种情况时间复杂度就是 O(1). 但是如果要在指定位置 i 插入和删除元素的话(
add(int index, E element)
)时间复杂度就为 O(n-i). 因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作. 2 LinkedList 采用链表存储, 所以插入, 删除元素时间复杂度不受元素位置的影响, 都是近似 O(1)而数组为近似 O(n).
4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问, 而 ArrayList 支持. 快速随机访问就是通过元素的序号快速获取元素对象 (对应于 get(int index) 方法).
5. 内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间, 而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据).
-6. 发
补充内容: RandomAccess 接口 **
- public interface RandomAccess {
- }
查看源码我们发现实际上 RandomAccess 接口中什么都没有定义. 所以, 在我看来 RandomAccess 接口不过是一个标识罢了. 标识什么? 标识实现这个接口的类具有随机访问功能.
在 binarySearch()方法中, 它要判断传入的 list 是否 RamdomAccess 的实例, 如果是, 调用 indexedBinarySearch()方法, 如果不是, 那么调用 iteratorBinarySearch()方法
- public static <T>
- int binarySearch(List<? extends Comparable<? super T>> list, T key) {
- if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
- return Collections.indexedBinarySearch(list, key);
- else
- return Collections.iteratorBinarySearch(list, key);
- }
ArraysList 实现了 RandomAccess 接口, 而 LinkedList 没有实现. 为什么呢? 我觉得还是和底层数据结构有关! ArraysList 底层是数组, 而 LinkedList 底层是链表. 数组天然支持随机访问, 时间复杂度为 O(1), 所以称为快速随机访问. 链表需要遍历到特定位置才能访问特定位置的元素, 时间复杂度为 O(n), 所以不支持快速随机访问.,ArraysList 实现了 RandomAccess 接口, 就表明了他具有快速随机访问功能. RandomAccess 接口只是标识, 并不是说 ArraysList 实现 RandomAccess 接口才具有快速随机访问功能的!
下面再总结一下 list 的遍历方式选择:
实现了 RandomAccess 接口的 list, 优先选择普通 for 循环 , 其次 foreach,
未实现 RandomAccess 接口的 ist, 优先选择 iterator 遍历(foreach 遍历底层也是通过 iterator 实现的), 大 size 的数据, 千万不要使用普通 for 循环
补充: 数据结构基础之双向链表
双向链表也叫双链表, 是链表的一种, 它的每个数据结点中都有两个指针, 分别指向直接后继和直接前驱. 所以, 从双向链表中的任意一个结点开始, 都可以很方便地访问它的前驱结点和后继结点. 一般我们都构造双向循环链表, 如下图所示, 同时下图也是 LinkedList 底层使用的是双向循环链表数据结构.
ArrayList 与 Vector 区别
Vector 类的所有方法都是同步的. 可以由两个线程安全地访问一个 Vector 对象, 但是一个线程访问 Vector 的话代码要在同步操作上耗费大量的时间.
Arraylist 不是同步的, 所以在不需要保证线程安全时时建议使用 Arraylist.
HashMap 的底层实现
JDK1.8 之前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列. HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值, 然后通过 (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度), 如果当前位置存在元素的话, 就判断该元素与要存入的元素的 hash 值以及 key 是否相同, 如果相同的话, 直接覆盖, 不相同就通过拉链法解决冲突.
所谓扰动函数指的就是 HashMap 的 hash 方法. 使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞.
JDK 1.8 HashMap 的 hash 方法源码:
JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化, 但是原理不变.
- static final int hash(Object key) {
- int h;
- // key.hashCode(): 返回散列值也就是 hashcode
- // ^ : 按位异或
- //>>>: 无符号右移, 忽略符号位, 空位都以 0 补齐
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
对比一下 JDK1.7 的 HashMap 的 hash 方法源码.
- static int hash(int h) {
- // This function ensures that hashCodes that differ only by
- // constant multiples at each bit position have a bounded
- // number of collisions (approximately 8 at default load factor).
- h ^= (h>>> 20) ^ (h>>> 12);
- return h ^ (h>>> 7) ^ (h>>> 4);
- }
相比于 JDK1.8 的 hash 方法 ,JDK 1.7 的 hash 方法的性能会稍差一点点, 因为毕竟扰动了 4 次.
所谓 "拉链法" 就是: 将链表和数组相结合. 也就是说创建一个链表数组, 数组中每一格就是一个链表. 若遇到哈希冲突, 则将冲突的值加到链表中即可.
JDK1.8 之后
相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化, 当链表长度大于阈值 (默认为 8) 时, 将链表转化为红黑树, 以减少搜索时间.
TreeMap,TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树. 红黑树就是为了解决二叉查找树的缺陷, 因为二叉查找树在某些情况下会退化成一个线性结构.
- public HashMap(int initialCapacity, float loadFactor) {
- if (initialCapacity <0)
- throw new IllegalArgumentException("Illegal initial capacity:" +
- initialCapacity);
- if (initialCapacity> MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- if (loadFactor <= 0 || Float.isNaN(loadFactor))
- throw new IllegalArgumentException("Illegal load factor:" +
- loadFactor);
- this.loadFactor = loadFactor;
- this.threshold = tableSizeFor(initialCapacity);
- }
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- /**
- * Returns a power of two size for the given target capacity.
- */
- static final int tableSizeFor(int cap) {
- int n = cap - 1;
- n |= n>>> 1;
- n |= n>>> 2;
- n |= n>>> 4;
- n |= n>>> 8;
- n |= n>>> 16;
- return (n <0) ? 1 : (n>= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- }
- static class Segment<K,V> extends ReentrantLock implements Serializable {
- }
- Collection
- 1. List
来源: http://www.bubuko.com/infodetail-2947035.html