扯淡 Java 集合
大致分类:List、Set、Queue、Map
Iterable
Collection 接口中继承 Iterable 接口。这个接口为 for each 循环设计、接口方法中有返回Iterator对象
我们看个例子来理解一下上面的话
反编译之后
Iterator
在 Iterable 接口中出现了这么一个迭代器
主要是为了统一遍历方式、使集合的数据结构和访问方式解耦
我们来看看最常见的 ArrayList 类中的内部类
我们都知道在 ArrayList 中 forEach 中的时候 remove 会导致 ConcurrentModificationException
而我们使用 Iterator 进行 remove 的时候就不会有这个问题、
List
ArrayList
动态数组
线程不安全
元素允许为 null
实现了 List、RandomAccess、Cloneable、Serializable
连续的内存空间
增加和删除都会导致 modCount 的值改变
默认扩容为一半
Vector
线程安全
扩容是上一次的一倍
存在 modCount
每个操作数组的方法都加上了 synchronized
CopyOnWriteArrayList
写时复制、加锁
耗内存
实时性不高
不存在 ConcurrentModificationException
数据量最好不要太大
使用 ReentrantLock 进行加锁
Collections.synchronizedList
synchronized 代码块
对象锁可以参数传进去、或者当前对象
需要传 List 对象进去
LinkedList
ArrayList 增删效率低、改查效率高、而 LinkedList刚刚相反
链表实现
for 循环的时候、根据 index 是靠近前半段还是后半段来决定是顺序还是逆序
增删的时候会改变 modCount
Map
常见的四个实现类
HashMap
HashTable
LinkedHashMap
TreeMap
HashMap
HashMap 是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的,如下如所示。
table 的长度默认是 16 、loadFactor 的默认值是 0.75
继续看看 Node 的数据结构
确定哈希桶数组索引的位置
这里的Hash算法本质上就是三步:取key的hashCode值、*高位运算*、取模运算
取模运算就是 ``h & (length - 1 )
` 、其实它是等价于
`h%length
`` 、因为 length 总是 2 的 n 次方。因为 &比%具有更高的效率
``(h = key.hashCode()) ^ (h >>> 16)
`` 将 key 的 hashCode 与 它的高 16 位进行 异或的操作
其实为啥这么操作呢、是因为当 table 的数组的大小比较小的时候、key 的 hashCode 的高位信息就会直接被丢弃掉、这个时候就会增加了低位的冲突、所以将高位的信息通过异或保留下来
那其实为啥要异或呢?双目运算不是还有 & || 吗
来自知乎的解答
方法一其实叫做一个扰动函数、hashCode的高位和低位做异或、就是为了混合原始哈希码的高位和低位、以此加大低位的随机性、而且混合后的低位掺杂了高位的部分特征、这样高位的信息也被变相地保留下来 、经过扰动之后、有效减少了哈希冲突
>
至于这里为什么使用异或运行、因为在双目运算 & || ^ 中 异或是混洗效果最好的、结果占双目运算两个数的50% 、混洗性是比较好的
>
https://www.zhihu.com/question/20733617/answer/111577937
>
https://codeday.me/bug/20170909/69679.html
关于 JDK 1.7 扩容导致循环链表问题
下面是 JDK 1.7 的扩容代码
我们先看看美团博客上面的例子
单线程环境下是正常完成扩容的、但是有没有发现、倒置了、key7 在 key3 前面了。这个很关键
我们再来看看多线程下、导致循环链表的问题
其实出现循环链表这种情况、就是因为扩容的时候、链表倒置了
而 JDK1.8 中、使用两个变量解决链表倒置而发生了循环链表的问题
通过 head 和 tail 两个变量、将扩容时链表倒置的问题解决了、循环链表的问题就解决了
但是无论如何、在并发的情况下、都会发生丢失数据的问题、就比如说上面的例子就丢失了 key5
HashTable
遗留类、很多功能和 HashMap 类似、但是它是线程安全的、但是任意时刻只能有一个线程写 HashTable、并发性不如 ConcurrentHashMap,因为 ConcurrentHashMap 使用分段锁。不建议使用
LinkedHashMap
LinkedHashMap继承自HashMap、在HashMap基础上、通过维护一条双向链表、解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题
重写了 HashMap 的 newNode 方法
并且重写了 afterNodeInsertion 方法、这个方法本来在 HashMap 中是空方法
而方法 removeEldestEntry 在 LinkedHashMap 中返回 false 、我们可以通过重写此方法来实现一个 LRU 队列的
默认为 false 遍历的时候控制顺序
TreeMap
TreeMap底层基于红黑树实现
Set
没啥好说的
Queue
PriorityQueue
默认小顶堆、可以看看关于堆排序的实现 八种常见的排序算法
强烈推荐文章参考的美团的这篇文章、关于 HashMap 的
>
https://tech.meituan.com/2016/06/24/java-hashmap.html
版权声明: 本文为 InfoQ 作者【CoderLi】的原创文章。
原文链接:【http://xie.infoq.cn/article/fd406f6d5521c91be3f5533e3】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论 (1 条评论)