第17章 容器

集合类库图:

container-taxonomy-min

  • 可选操作

执行各种不同的添加和移除的方法在Collection接口中都是可选操作,这意味着实现类并不需要为这些方法提供功能定义。简单来说,就是抽象类的某些派生类实现里,或者接口的某个实现类里面,某个方法是无意义的。

  • 未获支持的操作

最常见的未获支持的操作,都来源于本和由固定尺寸的数据接口支持的容器。当你用Arrays.adList()将数组转换为List时,就会得到这样的容器。当然你也可以将它方法ArrayList将它转成一个支持所有方法的list:

因为Arrays.asList()会生成一个List,它基于一个固定大小的数组,仅支持哪些不会改变数组大小的操作,对它而言是有道理的。(可以看到代码中,是可以set的)

把Arrays.asList()的结果作为构造器的参数传递给任何Colelction(或者使用addAll,或者Collections.addAll()静态方法),这样就可以生成允许使用所有方法的普通容器。

Collections.unmodifiableList()产生补课修改的列表。(包括set)

  • 17.6 Set和存储顺序
描述
Set(interface)存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set不保证维护元素的次序
HashSet为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()
TreeSet保持次序的Set,底层为树结构。元素必须实现Comparable接口
LinkedHashSet具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的顺序)
  • 17.7 队列

Queue在Java SE5中仅有的两个实现是LinkedList和PriorityQueuq,它们的差异在于排序行为而不是性能。(public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

除了优先级队列,Queue将精确地按照元素被置于Queue中的顺序产生它们。

  • 17.8.1 性能

HashMap使用的特殊的值,称作散列码,来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值,它是通过将该对象的某些信息进行转换而成的。(后面会有详细介绍)

描述
HashMapMap基于散列表的实现(它取代了Hashtable)
LinkedHashMap类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是其插入次数,或者是最近最少使用(LRU)次数。只比HashMap慢一点,而在迭代访问时反而更快,因为它使用链表维护内部次序
TreeMap基于红黑树的实现。内部是有序的
WeakHashMap弱键(weak key)映射,允许释放映射所指向的对象
ConcurrentHashMap一种线程安全的Map,但是不涉及同步加锁
IdentityHashMap使用==代替equals()对key进行比较

总结来说,任何键都必须具有一个equals()方法,如果键被用于散列Map,那么它必须还具有恰当的hashCode()方法,如果键被用于TreeMap,那么它必须实现Comparable。

  • 17.8.3 LinkedHashMap

可以在构造器中设定采用最近最少使用(LRC)算法:

在输出可以看到,键值对是以插入的顺序进行遍历的,甚至LRC算法的版本也是如此。

  • 17.9 散列与散列码

当你自己创建用作HashMap的键的类,有可能会忘记在其中放置必需的方法,而这时通常会犯的一个错误:


它无法找到数字3这个键,因为Groundhog自动继承自基类Object,所以这里使用Object的hashCode()方法生成散列码,而它默认是用对象的地址计算散列码的,因此两个的散列码是不同的。

但是只编写恰当的hashCode()方法也不够,因为HashMap是使用equals()来判断当前的键是否与表中存在的键相同。

正确的equals()方法必须满足于下列5个条件:
1. 自反性。对任意x,x.equals(x)一定为true。
2. 对称性。对任意x和y,如果y.equals(x)返回true,则x.equals(y)也返回true。
3. 传递性。对任意x、y、z,如果有x.equals(y)返回true,y.equals(z)返回true,则x.equals(z)一定返回true。
4. 一致性。对任意x和y,x.equals(y)无论调用多少次,返回结果应该保持一致。
5. 对任何不是null的x,x.equals(null)一定返回false。(调用instanceof可以悄悄地检查此对象是否为null

默认的Object.equals()只是比较对象的地址,因此如果要使用自己的类作为HashMap的键,必须同时重载hashCode和equals()

  • 17.9.1 理解hashCode()

如果不为你的键覆盖hashCode()和equals(),那么使用散列的数据结构(HashSet,HashMap,LinkedHashSet或LinkedHashMap)就无法正确处理你的键。

使用散列的目的在于:想要使用一个对象来查找另一个对象。

  • 17.9.2 为速度而散列

如果键没有按照任何特定顺序保存,所以只能使用简单的线性查询,而线性查询时最慢的查询方式。

散列中使用存储最快的数据结构数组来表示键的信息(是键的信息而不是键本身),因为数组不能调整容量,而我们希望在Map中保存数量不确定的值,因此数组不保存键本身,而是通过键对象生成一个数字,将其作为数组的下标,这个数字就是散列码。由定义在Object中的、且可能由你的类覆盖的hashCode()方法(在计算机科学的术语中成为散列函数)生成。

不同的键可以产生相同的下标,通常冲突是由外部链接处理:数组并不直接保存值,而是保存值的list。(如果能保证没有冲突,那可能就有了一个完美散列函数)因此,不是查询整个list,而是快速的跳到数组的某个位置,只对很少的元素进行比较,这边是HashMap会如此快的原因。

一个简单的散列Map:

因为散列表中的“槽位”(slot)通常称为桶位(bucket),因此我们将表示实际散列表的数组命名为bucket。
  • 17.9.3 覆盖hashCode()

设计hashCode()时最重要的因素就是:无论何时,对同一个对象调用hashCode()都应该生成相同的值。此外,也不应该使hashCode()依赖于具有唯一性的对象信息,尤其是使用this的值。

对于String来说,它们的hashCode()是基于String的内容的,不管是=,还是new,只要内容一样,hashCode()的结果就是一样的。

好的hashCode()应该产生分布均匀的散列码。

Joshua Bloch为怎样写出一份像样的hashCode()给出了基本的指导:
1. 对int变量result赋予某个非0常值,例如17.
2. 对对象内每个有意义的域f(即每个可以做equals()操作的域)计算出一个int散列码c:

域类型计算
booleanc = (f?0:1)
byte、char、short或intc=(int)f
longc = (int)(f^(f>>>32))
floatc = Float.floatToIntBits(f)
doublec = long l =Double.doubleToLongBits(f); c = (int)(l^(l>>>32))
Objectc = f.hashCode()
数组对每个元素应用上诉规则

3. 合并计算得到的散列码:result=37*result+c
4. 返回result。
5. 检查hashCode()最后生成的结果,确保相同的对象有相同的散列码

一个简单的例子:

  • 17.10.2 对list的选择

最佳的做法可能是将ArrayList(随机访问快)作为默认首选,只有你需要使用额外的功能,或者当程序的性能因为从表中进行插入和删除而变差的时候,才去选择LinkedList。如果使用的是固定数量的元素,那么既可以使用背后由数组支撑的List(Arrays.asList()产生的列表),也可以选择真正的数组。

  • 17.10.4 对Set的选择

HashSet的性能基本上总是比TreeSet好,当需要一个排好序的Set时,才应该使用TreeSet。因为TreeSet内部结构支持排序,因此用TreeSet迭代通常比用HashSet要快。

对于插入操作,LinkedHashSet比HashSet的代价更高,这是由维护链表所带来额外开销造成的。

  • 17.10.5 对Map的选择

Hashtable的性能大体上与HashMap相当,因为HashMap是用来替代Hashtable的。

使用Map时,你的第一选择应该是HashMap,只有在你要求Map始终保持有序时,才需要使用TreeMap.

HashMap的性能因子
1. 容量:表中的桶位数
2. 初始容量:表在创建时所拥有的桶位数。
3. 尺寸:表中当前存储的项数。
4. 负载因子:尺寸/容量。当负载情况达到该因子的水平是,容器将自动增加其容量(桶位数),实现方式是史容量大致加倍,并重新将现有对象分布到新的桶位集中(这被称为再散列)。默认的负载因子是0.75。更高的负载因子可以降低表所需要的空间,但是会增加查找代价。

  • 17.11.3 Collection或Map的同步控制

Java容器类类库采用快速保存机制,她会探查容器上任何除了你的进程所进行的操作以外的所有变化,一旦它发现其他进程修改了容器,就会立刻抛出ConcurrentModificationException异常。

  • 17.12 持有引用

强引用(StrongReference)

强引用是使用最普遍的引用。如果一个对象具有强引用,那垃圾回收器绝不会回收它。当内存空间不足,Java虚拟机宁愿抛出OutOfMemoryError错误,使程序异常终止,也不会靠随意回收具有强引用的对象来解决内存不足的问题。

软引用(SoftReference)

如果一个对象只具有软引用,则内存空间足够,垃圾回收器就不会回收它;如果内存空间不足了,就会回收这些对象的内存。只要垃圾回收器没有回收它,该对象就可以被程序使用。软引用可用来实现内存敏感的高速缓存。

软引用可以和一个引用队列(ReferenceQueue)联合使用,如果软引用所引用的对象被垃圾回收器回收,Java虚拟机就会把这个软引用加入到与之关联的引用队列中。

弱引用(WeakReference)

弱引用与软引用的区别在于:只具有弱引用的对象拥有更短暂的生命周期。在垃圾回收器线程扫描它所管辖的内存区域的过程中,一旦发现了只具有弱引用的对象,不管当前内存空间足够与否,都会回收它的内存。不过,由于垃圾回收器是一个优先级很低的线程,因此不一定会很快发现那些只具有弱引用的对象。

弱引用可以和一个引用队列(ReferenceQueue)联合使用,如果弱引用所引用的对象被垃圾回收,Java虚拟机就会把这个弱引用加入到与之关联的引用队列中。

虚引用(PhantomReference)

“虚引用”顾名思义,就是形同虚设,与其他几种引用都不同,虚引用并不会决定对象的生命周期。如果一个对象仅持有虚引用,那么它就和没有任何引用一样,在任何时候都可能被垃圾回收器回收。

虚引用主要用来跟踪对象被垃圾回收器回收的活动。虚引用与软引用和弱引用的一个区别在于:虚引用必须和引用队列(ReferenceQueue)联合使用。当垃圾回收器准备回收一个对象时,如果发现它还有虚引用,就会在回收对象的内存之前,把这个虚引用加入到与之 关联的引用队列中。

  • 17.12.1 WeakHashMap

和HashMap一样,WeakHashMap 也是一个散列表,它存储的内容也是键值对(key-value)映射,而且键和值都可以是null。

不过WeakHashMap的键是“弱键”。在 WeakHashMap中,当某个键不再正常使用时,会被从WeakHashMap中被自动移除。更精确地说,对于一个给定的键,其映射的存在并不阻止垃圾回收器对该键的丢弃,这就使该键成为可终止的,被终止,然后被回收。某个键被终止时,它对应的键值对也就从映射中有效地移除了。

这个“弱键”的原理呢?大致上就是,通过WeakReference和ReferenceQueue实现的。WeakHashMap的key是“弱键”,即是WeakReference类型的;ReferenceQueue是一个队列,它会保存被GC回收的“弱键”。实现步骤是:

  1. 新建WeakHashMap,将“键值对”添加到WeakHashMap中。实际上,WeakHashMap是通过数组table保存Entry(键值对);每一个Entry实际上是一个单向链表,即Entry是键值对链表。
  2. 当某“弱键”不再被其它对象引用,并被GC回收时。在GC回收该“弱键”时,这个“弱键”也同时会被添加到ReferenceQueue(queue)队列中。
  3. 当下一次我们需要操作WeakHashMap时,会先同步table和queue。table中保存了全部的键值对,而queue中保存被GC回收的键值对;同步它们,就是删除table中被GC回收的键值对。
    这就是“弱键”如何被自动从WeakHashMap中删除的步骤了
Telegram频道已经开通,关注flyzythink,随手分享正能量,了解VPS优惠与补货
Telegram群组已经开通,加入flyzy小站,FREE TO TALK
搬瓦工用户交流TG群,加入搬瓦工用户交流群,畅聊搬瓦工
VPS交流群1(已满):780593286 flyzy小站
VPS交流群2:729726961 flyzy小站
搬瓦工交流群(搬瓦工用户推荐):938957834 flyzy小站
搬瓦工补货通知群:618922256 搬瓦工补货通知群
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注