本文快速回顾了Java中容器的知识点,用作面试复习,事半功倍。
其它知识点复习手册
容器主要包括 Collection 和 Map 两种,Collection 又包含了 List、Set 以及 Queue。
Collection
在这里插入图片描述
在这里插入图片描述
数组和集合的区别:
1. Set(元素不可重复)
2. List(有序(存储顺序和取出顺序一致),可重复)
3. Queue
Map
在这里插入图片描述
Fail-Fast 机制和 Fail-Safe 机制
https://blog.csdn.net/Kato_op/article/details/80356618
Fail-Fast
Fail-fast 机制是 java 集合(Collection)中的一种错误机制。 当多个线程对同一个集合的内容进行操作时,就可能会产生 fail-fast 事件。
注意,如果集合发生变化时修改modCount值, 刚好有设置为了expectedmodCount值, 则异常不会抛出.(比如删除了数据,再添加一条数据)
所以,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。
迭代器的快速失败行为应该仅用于检测程序错误, 而不是用他来同步。
java.util包下的集合类都是Fail-Fast机制的,不能在多线程下发生并发修改(迭代过程中被修改).
Fail-Safe
采用安全失败(Fail-Safe)机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先copy原有集合内容,在拷贝的集合上进行遍历。
原理:
由于迭代时是对原集合的拷贝的值进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会出发ConcurrentModificationException
缺点:
迭代器并不能访问到修改后的内容(简单来说就是, 迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的)
使用场景:
java.util.concurrent包下的容器都是Fail-Safe的,可以在多线程下并发使用,并发修改
迭代器模式
在这里插入图片描述
Collection 实现了 Iterable 接口,其中的 iterator() 方法能够产生一个 Iterator 对象,通过这个对象就可以迭代遍历 Collection 中的元素。
从 JDK 1.5 之后可以使用 foreach 方法来遍历实现了 Iterable 接口的聚合对象。
适配器模式
适配器模式解释:https://www.jianshu.com/p/93821721bf08
java.util.Arrays#asList() 可以把数组类型转换为 List 类型。
如果要将数组类型转换为 List 类型,应该注意的是 asList() 的参数为泛型的变长参数,因此不能使用基本类型数组作为参数,只能使用相应的包装类型数组。
也可以使用以下方式生成 List。
ArrayList
关键词
概览
在这里插入图片描述
实现了 RandomAccess 接口,因此支持随机访问。这是理所当然的,因为 ArrayList 是基于数组实现的。
扩容
如果不够时,需要使用 grow() 方法进行扩容,新容量的大小为 oldCapacity + (oldCapacity >> 1),也就是旧容量的 1.5 倍。
扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中
因此最好在创建 ArrayList 对象时就指定大概的容量大小,减少扩容操作的次数。
加入元素:add
add(E e)
首先去检查一下数组的容量是否足够
扩容到原来的1.5倍,第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
add(int index, E element)
步骤:
删除元素:remove
步骤:
需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上,复制的代价很高。
复制数组:System.arraycopy()
看到arraycopy(),我们可以发现:该方法是由C/C++来编写的
在这里插入图片描述
Fail-Fast
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作,或者是调整内部数组的大小,仅仅只是设置元素的值不算结构发生变化。
在进行序列化或者迭代等操作时,需要比较操作前后 modCount 是否改变,如果改变了需要抛出 ConcurrentModificationException。
构造器
ArrayList 提供了三种方式的构造器:
序列化
补充:transient讲解
http://www.importnew.com/21517.html
你只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。
ArrayList 基于数组实现,并且具有动态扩容特性,因此保存元素的数组不一定都会被使用,那么就没必要全部进行序列化。
保存元素的数组 elementData 使用 transient 修饰,该关键字声明数组默认不会被序列化。
ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。
序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法,原理类似。
Vector
关键词
替代方案
可以使用 Collections.synchronizedList(); 得到一个线程安全的 ArrayList。
也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
CopyOnWriteArrayList
关键词
读写分离
适用场景
CopyOnWriteArrayList 在写操作的同时允许读操作,大大提高了读操作的性能,因此很适合读多写少的应用场景。
缺陷
所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。
LinkedList
关键词
概览
在这里插入图片描述
基于双向链表实现,内部使用 Node 来存储链表节点信息。
每个链表存储了 Head 和 Tail 指针:
在这里插入图片描述
ArrayList 与 LinkedList 比较
删除元素:remove
在这里插入图片描述
获取元素:get
替换元素:set
set方法和get方法其实差不多,根据下标来判断是从头遍历还是从尾遍历
其他方法
LinkedList实现了Deque接口,因此,我们可以操作LinkedList像操作队列和栈一样
LinkedList的方法比ArrayList的方法多太多了,这里我就不一一说明了。具体可参考:
HashMap
http://wiki.jikexueyuan.com/project/java-collection/hashmap.html
源码分析:https://segmentfault.com/a/1190000014293372
关键词
存储结构
hashMap的一个内部类Node:
在这里插入图片描述
Node内部包含了一个 Entry 类型的数组table,数组中的每个位置被当成一个桶。
Entry 存储着键值对。它包含了四个字段,从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶,一个桶存放一个链表。
HashMap 使用拉链法来解决冲突,同一个链表中存放哈希值相同的 Entry。
构造器
在这里插入图片描述
构造时就会调用tableSizeFor():返回一个大于输入参数且最近的2的整数次幂。
拉链法
应该注意到链表的插入是以头插法方式进行的
查找需要分成两步进行:
put 操作
HashMap 允许插入键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法,也就无法确定该键值对的桶下标,只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。
使用链表的头插法,也就是新的键值对插在链表的头部,而不是链表的尾部。
补充:hashmap里hash方法的高位优化:
https://www.cnblogs.com/liujinhong/p/6576543.html
https://note.youdao.com/yws/res/18743/50AADC7BB42845B29CDA293FC409250C?ynotemdtimestamp=1548155508277
设计者将key的哈希值的高位也做了运算(与高16位做异或运算,使得在做&运算时,此时的低位实际上是高位与低位的结合),这就增加了随机性,减少了碰撞冲突的可能性!
为何要这么做?
table的长度都是2的幂,因此index仅与hash值的低n位有关,hash值的高位都被与操作置为0了。
这样做很容易产生碰撞。设计者权衡了speed, utility, and quality,将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了,而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下,既减少了系统的开销,也不会造成的因为高位没有参与下标的计算(table长度比较小时),从而引起的碰撞。
确定桶下标
很多操作都需要先确定一个键值对所在的桶下标。
4.1 计算 hash 值
4.2 取模
令 x = 1<<4,即 x 为 2 的 4 次方,它具有以下性质:
令一个数 y 与 x-1 做与运算,可以去除 y 位级表示的第 4 位以上数:
这个性质和 y 对 x 取模效果是一样的:
我们知道,位运算的代价比求模运算小的多,因此在进行这种计算时用位运算的话能带来更高的性能。
确定桶下标的最后一步是将 key 的 hash 值对桶个数取模:hash%capacity,如果能保证 capacity 为 2 的 n 次方,那么就可以将这个操作转换为位运算。
当 length 总是 2 的 n 次方时,h& (length-1)运算等价于对 length 取模,也就是 h%length,但是 & 比 % 具有更高的效率。这看上去很简单,其实比较有玄机的,我们举个例子来说明:
h & (table.length-1) hash table.length-1 8 & (15-1): 0100 & 1110 = 0100 9 & (15-1): 0101 & 1110 = 0100 8 & (16-1): 0100 & 1111 = 0100 9 & (16-1): 0101 & 1111 = 0101
所以说,当数组长度为 2 的 n 次幂的时候,不同的 key 算得得 index 相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小
扩容-基本原理
设 HashMap 的 table 长度为 M,需要存储的键值对数量为 N,如果哈希函数满足均匀性的要求,那么每条链表的长度大约为 N/M,因此平均查找次数的复杂度为 O(N/M)。
为了让查找的成本降低,应该尽可能使得 N/M 尽可能小,因此需要保证 M 尽可能大,也就是说 table 要尽可能大。HashMap 采用动态扩容来根据当前的 N 值来调整 M 值,使得空间效率和时间效率都能得到保证。
和扩容相关的参数主要有:capacity、size、threshold 和 load_factor。
参数 含义 capacity table 的容量大小,默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。 size 键值对数量。 threshold size 的临界值,当 size 大于等于 threshold 就必须进行扩容操作。 loadFactor 装载因子,table 能够使用的比例,threshold = capacity * loadFactor。
从下面的添加元素代码中可以看出,当需要扩容时,令 capacity 为原来的两倍。
扩容使用 resize() 实现,需要注意的是,扩容操作同样需要把 oldTable 的所有键值对重新插入 newTable 中,因此这一步是很费时的。
扩容-重新计算桶下标
Rehash优化:https://my.oschina.net/u/3568600/blog/1933764
在进行扩容时,需要把键值对重新放到对应的桶上。HashMap 使用了一个特殊的机制,可以降低重新计算桶下标的操作。
假设原数组长度 capacity 为 16,扩容之后 new capacity 为 32:
对于一个 Key,
总结:
经过rehash之后,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置
因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示意图:
在这里插入图片描述
计算数组容量
HashMap 构造函数允许用户传入的容量不是 2 的 n 次方,因为它可以自动地将传入的容量转换为 2 的 n 次方。
先考虑如何求一个数的掩码,对于 10010000,它的掩码为 11111111,可以使用以下方法得到:
mask+1 是大于原始数字的最小的 2 的 n 次方。
以下是 HashMap 中计算数组容量的代码:
链表转红黑树
并不是桶子上有8位元素的时候它就能变成红黑树,它得同时满足我们的键值对大于64才行的
这是为了避免在哈希表建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。
HashTable
关键词:
HashMap 与 HashTable
在这里插入图片描述
ConcurrentHashMap
谈谈ConcurrentHashMap1.7和1.8的不同实现:
http://www.importnew.com/23610.html
详细源码分析(还未细看):
https://blog.csdn.net/yan_wenliang/article/details/51029372
https://segmentfault.com/a/1190000014380257
主要针对jdk1.7的实现来介绍
关键词
存储结构
jdk1.7
jdk1.7中采用Segment + HashEntry的方式进行实现
在这里插入图片描述
Segment:其继承于 ReentrantLock 类,从而使得 Segment 对象可以充当锁的角色。
Segment 中包含HashBucket的数组,其可以守护其包含的若干个桶。
ConcurrentHashMap采用了分段锁,每个分段锁维护着几个桶,多个线程可以同时访问不同分段锁上的桶,从而使其并发度更高(并发度就是 Segment 的个数)。
jdk1.8
在这里插入图片描述
1.8中放弃了Segment臃肿的设计,取而代之的是采用Node数组 + CAS + Synchronized来保证并发安全进行实现
添加元素:put
在这里插入图片描述
只让一个线程对散列表进行初始化!
获取元素:get
从顶部注释我们可以读到,get方法是不用加锁的,是非阻塞的。
Node节点是重写的,设置了volatile关键字修饰,致使它每次获取的都是最新设置的值
获取大小:size
每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数。
在执行 size 操作时,需要遍历所有 Segment 然后把 count 累计起来。
ConcurrentHashMap 在执行 size操作时先尝试不加锁,如果连续两次不加锁操作得到的结果一致,那么可以认为这个结果是正确的。
尝试次数使用 RETRIES_BEFORE_LOCK 定义,该值为 2,retries 初始值为 -1,因此尝试次数为 3。
如果尝试的次数超过 3 次,就需要对每个 Segment 加锁。
删除元素:remove
在这里插入图片描述
为什么用这么方式删除呢,细心的同学会发现上面定义的HashEntry的key和next都是final类型的,所以不能改变next的指向,所以又复制了一份指向删除的结点的next。
Collections.synchronizedMap()与ConcurrentHashMap的区别
参考:https://blog.csdn.net/lanxiangru/article/details/53495854
总结
ConcurrentHashMap 的高并发性主要来自于三个方面:
LinkedHashMap
http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
https://segmentfault.com/a/1190000014319445
关键词
概论
在这里插入图片描述
在这里插入图片描述
成员变量
该 Entry 除了保存当前对象的引用外,还保存了其上一个元素 before 和下一个元素 after的引用,从而在哈希表的基础上又构成了双向链接列表。
构造器
在这里插入图片描述
获取元素:get
LinkedHashMap 重写了父类 HashMap 的 get 方法,实际在调用父类 getEntry() 方法取得查找的元素后,再判断当排序模式 accessOrder 为 true 时,记录访问顺序,将最新访问的元素添加到双向链表的表头,并从原来的位置删除。
由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失。
遍历元素
为啥注释说:初始容量对遍历没有影响?
因为它遍历的是LinkedHashMap内部维护的一个双向链表,而不是散列表(当然了,链表双向链表的元素都来源于散列表)
LinkedHashMap应用
http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap-lrucache.html
LRU最近最少使用(访问顺序)
用这个类有两大好处:
Java里面实现LRU缓存通常有两种选择:
以下是使用 LinkedHashMap 实现的一个 LRU 缓存:
实现详细代码请参考文章:补充知识点-缓存
FIFO(插入顺序)
还可以在插入顺序的LinkedHashMap直接重写下removeEldestEntry方法即可轻松实现一个FIFO缓存
TreeMap
关键词
概览
在这里插入图片描述
获取元素:get
详细看:
https://segmentfault.com/a/1190000014345983#articleHeader4
总结:
删除元素:remove
删除节点并且平衡红黑树
HashSet
http://wiki.jikexueyuan.com/project/java-collection/hashset.html
https://segmentfault.com/a/1190000014391402
关键词:
如果添加的是在 HashSet 中不存在的,则返回 true;如果添加的元素已经存在,返回 false。
对于 HashSet 中保存的对象,请注意正确重写其 equals 和 hashCode 方法,以保证放入的对象的唯一性。
HashSet 和 HashMap 的区别
重要:
1. HashMap中使用键对象来计算hashcode值
2. HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false
在这里插入图片描述
TreeSet
关键词
LinkedHashSet
关键词
总结Set
HashSet:
TreeSet:
LinkedHashSet:
WeekHashMap
存储结构
WeakHashMap 的 Entry 继承自 WeakReference,被 WeakReference 关联的对象在下一次垃圾回收时会被回收。
WeakHashMap 主要用来实现缓存,通过使用 WeakHashMap 来引用缓存对象,由 JVM 对这部分缓存进行回收。
ConcurrentCache
Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 来实现缓存功能。
ConcurrentCache 采取的是分代缓存:
Enumeration和Iterator接口的区别
Iterator替代了Enumeration,Enumeration是一个旧的迭代器了。
与Enumeration相比,Iterator更加安全,因为当一个集合正在被遍历的时候,它会阻止其它线程去修改集合。
区别有三点:
ListIterator有什么特点
在这里插入图片描述
与Java集合框架相关的有哪些最好的实践
如果是单列的集合,我们考虑用Collection下的子接口ArrayList和Set。
如果是映射,我们就考虑使用Map
本人目前为后台开发工程师,主要关注Python爬虫,后台开发等相关技术。
原创博客主要内容:
同步更新以下几大博客:
页面更新:2024-03-29
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号