TIJ阅读笔记（第十一章）(5)

Java标准类库里有好几种Map：HashMap，TreeMap，LinkedHashMap，WeakHashMap，以及IdentityHashMap。它们都实现了Map的基本接口，但是在行为方式方面有着明显的诧异。这些差异体现在，效率，持有和表示对象pair的顺序，持有对象的时间长短，以及如何决定键的相等性。
性能时Map所要面对的一个大问题。如果你知道get()时怎么工作的，你就会发觉（比方说）在ArrayList里面找对象会是相当慢的。而这正是HashMap的强项。它不是慢慢地一个个地找这个键，而是用了一种被称为hash code的特殊值来进行查找的。散列（hash）时一种算法，它会从目标对象当中提取一些信息，然后生成一个表示这个对象的“相对独特”的int。hashCode()是Object根类的方法，因此所有Java对象都能生成hash code。HashMap则利用对象的hashCode()来进行快速的查找。这样性能就有了急剧的提高。
Map（接口）：维持键－－值的关系（既pairs），这样就能用键来找值了。
HashMap*：基于hash表的实现。（用它来代替Hashtable。）提供时间恒定的插入与查询。在构造函数种可以设置hash表的capacity和load factor。可以通过构造函数来调节其性能。
LinkedHashMap(JDK 1.4)：很像HashMap，但是用Iterator进行遍历的时候，它会按插入顺序或最先使用的顺序（least-recently-used(LRU)order）进行访问。除了用Iterator外，其他情况下，只是比HashMap稍慢一点。用Iterator的情况下，由于是使用链表来保存内部顺序，因此速度会更快。
TreeMap：基于红黑树数据结构的实现。当你查看键或pair时，会发现它们时按顺序（根据Comparable或Comparator，我们过一会讲）排列的。TreeMap的特点时，你锁得到的时一个有序的Map。TreeMap是Map中唯一有subMap()方法的实现。这个方法能让你获取这个树中的一部分。
WeakHashMap：一个weak key的Map，是为某些特殊问题而设计的。它能让Map释放其所持有的对象。如果某个对象除了在Map当中充当键之外，在其他地方都没有其reference的话，那它将被当作垃圾回收。
IdentityHashMap(JDK 1.4)：一个用＝＝，而不是equals()来比较键的hash map。不是为我们平常使用而设计的，是用来解决特殊问题的。
散列是往Map里存数据的常用算法。

SortedMap
SortedMap（只有TreeMap这一个实现）的键肯定是有序的，因此这个接口里面就有一些附加功能的方法了。
Comparator comparator()：返回Map所使用的comparator，如果是用Object内置的方法的话，则返回null。
Object firstKey()：返回第一个键。
Object lastKey()：返回最后一个键。
SortedMap subMap(fromKey, toKey)：返回这个Map的一个子集，其键从fromKey开始到toKey为止，包括前者，不包括后者。
SortedMap headMap(toKey)：返回这个Map的一愕嘎子集，其键均小于toKey。
SortedMap tailMap(fromKey)：返回这个Map的一个子集，其键均大于等于fromKey。
pair是按key的顺序存储的，由于TreeMap有顺序的概念，因此“位置”是有意义的，所以你可以去获取它的第一个和最后一个元素，以及它的子集。

LinkedHashMap
为了提高速度，LinkedHashMap对所有东西都做了hash，而且遍历的时候（println()会遍历整个Map，所以你能看到这个过程）还会按插入顺序返回pair。此外，你还可以在LinkedHashMap的构造函数里面进行配置，让它使用基于访问的LRU（least-recently-used）算法，这样还没被访问过的元素（同时也是要删除的候选对象）就会出现在队列的最前头。这样，为节省资源而写一个定时清理的程序就变得很简单了。

散列算法与Hash数
一个合适的equals()必须做到一下五点：
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)，它都必须一致地返回
true或false。
5 对于任何非空的x，x.equals(null)必须返回false。
默认的Object.equals()只是简单地比较两个对象的地址。
如果你想把子集写的类当HashMap的键来用的话，你就必须把hashCode()和equals（）都给覆写了。

理解hashCode()
如果你不覆写键的hashCode()和equals()的话，散列数据结构（HashSet，HashMap，LinkedHashSet，或LinkedHashMap）就没法正确地处理键。
散列的价值就在于速度：散列算法能很快地找出东西。
数组是最快的数据结构。

持有reference
java.lang.ref类库里有一套能增进垃圾回收器工作的灵活性的类。一旦碰到了“对象达到要耗光内存”的时候，这些类就会闲的格外有用。有三个类是继承抽象类Reference的：SoftReference，WeakReference和PhantomReference。如果待处理的对象只能通过这些Reference进行访问的话，那么这些Reference对象就会向垃圾回收器提供一些不同级别的暗事。

……

总结：
总结Java标准类库的容器类：
1。数组把对象和数字形式的下标联系起来。它持有的是类型确定的对象，这样提取对象的时候就不用再作类型传递了。它可以是多维的，也可以持有primitive。但是创建之后它的容量不能改了。
2。Collection持有单个元素，而Map持有相关联的pair。
3。和数组一样，List也把数字下标同对象联系起来，你可以把数组和List想成有序的容器。List会随元素的增加自动调整容量。但是List只能持有Object reference，所以不能存放primitive，而且把Object提取出来之后，还要做类型传递。
4。如果要做很多随机访问，那么请用ArrayList，但是如果要再List的中间做很多插入和删除的话，就应该用LinkedList了。
5。LinkedList能提供队列，双向队列和栈的功能。
6。Map提供的不是对象与数组的关联，而是对象和对象的关联。
HashMap看重的是访问速度，而TreeMap各国那看重键的顺序，因而它不如HashMap那么快。而LinkedHashMap则保持对象插入的顺序，但是也可以用LRU算法为它重新排序。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有