Thking in java（第四版）-查缺补漏（第17章）

背景

继续查缺补漏，加油

1.Java容器类库简化图

2.填充容器

(1).Collections.fill()方法只复制同一个对象 引用来填充容器，只对List对象有用。

(2).享元：可以在普通的解决方案需要过多的对象，或产生不同对象太占用空间时使用。

享元模式使得对象的一部分被具体化，因此，与对象中的所有事物都包含在对象内部不

同，我们可以在更加高效的外部表中查找对象的一部分或整体。

(3).为了创建只读Map，可以继承AbstractMap并实现entrySet()。为了创建只读的Set，

可以继承AbstracSet并实现iterator()和size()。

(4)创建只读List，继承AbstractList并实现get()和size()。例如：

package tools;
import java.util.*;
public class CountingIntegerList extends AbstractList<Integer> {
	private int size;
	public CountingIntegerList(int size){
		this.size=size<0?0:size;
	}
	public Integer get(int index){
		return Integer.valueOf(index);
	}
	public int size(){	return size;}
	public static void main(String[] args){
		System.out.println(new CountingIntegerList(30));
	}
}

(5)下面的示例使用了享元的模式：Map.Entry对象只存储了它的索引，而不是实际的键和值。

EntrySet.Iterator，每个迭代器只有一个Map.Entry，而不是为每个数据对都创建Map.Entry。

Entry对象被用数据的视窗，它只包含静态字符串数组的引用。

package tools;
import java.util.*;
public class CountingMapData extends AbstractMap<Integer,String> {
	private int size;
	private static String[] chars=
			"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z".split(" ");
	public CountingMapData(int size){
		if(size<0) this.size=0;
		this.size=size;
	}
	private static class Entry implements Map.Entry<Integer, String>{
		int index;
		Entry(int index){this.index=index;}
		public boolean equals(Object o){
			return Integer.valueOf(index).equals(o);
		}
		public Integer getKey(){	return index;}
		public String getValue(){
			return chars[index%chars.length]+Integer.toString(index/chars.length);
		}
		public String setValue(String value){
			throw new UnsupportedOperationException();
		}
		public int hashCode(){
			return Integer.valueOf(index).hashCode();
		}
	}
	static class EntrySet extends AbstractSet<Map.Entry<Integer,String>>{
		private int size;
		EntrySet(int size){
			if(size<0)
				this.size=0;
			this.size=size;
		}
		public int size(){return size;}
		private class Iter implements Iterator<Map.Entry<Integer,String>>{
			private Entry entry=new Entry(-1);
			public boolean hasNext(){
				return entry.index<size-1;
			}
			public Map.Entry<Integer,String> next(){
				entry.index++;
				return entry;
			}
			public void remove(){
				throw new UnsupportedOperationException();
			}
		}
		public Iterator<Map.Entry<Integer, String>> iterator(){
			return new Iter();
		}
	}
	public Set<Map.Entry<Integer,String>> entrySet(){
		return new EntrySet(size);
	}

	public static void main(String[] args){
		System.out.println(new CountingMapData(60));
	}
}

3.可选操作

执行各种不同的添加和移除的方法在Collection接口中都是可选操作，这意味着实现类

并不需要为这些方法提供功能定义。这样做可以防止在设计中出现接口爆炸的情况。

如果一个操作未获支持，那么实现接口的时候可能就会导致UnsupportedOperationException。

4.Set和存储顺序

例如：

class SetType{
	int i;
	public SetType(int n){	i=n;}
	public boolean equals(Object o){
		return o instanceof SetType &&(i==((SetType)o).i);
	}
	public String toString(){	return Integer.toString(i);}
}
class HashType extends SetType{
	public HashType(int n){	super(n);}
	public  int hashCode(){return i;}
}
class TreeType extends SetType implements Comparable<TreeType>{
	public TreeType(int n){	super(n);}
	public int compareTo(TreeType arg){
		return (arg.i<i?-1:(arg.i==i?0:1));
	}
}

SortedSet 按对象的比较函数对元素排序。

5.队列

Queue仅有的两个实现是LinkedList和PriorityQueue，它们的差异在于排序行为而不是性能。

优先级队列：

package containers;
import java.util.*;
public class Ex11 extends PriorityQueue<Ex11.Ex> {
	public static Random rand=new Random(47);
	static class Ex implements Comparable<Ex>{
		private Integer i;
		private char pri;
		private int sec;
		public Ex(Integer i,char pri,int sec){
			this.i=i;
			this.pri=pri;
			this.sec=sec;
		}
		@Override
		public int compareTo(Ex o) {
			if(pri>o.pri)
				return +1;
			if(pri==o.pri)
				if(sec>o.sec)
					return +1;
				else if(sec==o.sec)
					return 0;
			return -1;
		}
		public String toString(){
			return Character.toString(pri)+sec+": "+i.toString();
		}
	}
	public void add(Integer in,char priority,int second){
		super.add(new Ex(in,priority,second));
	}
	public static void main(String[] args){
		Ex11 e=new Ex11();
		e.add(rand.nextInt(100),'A',2);
		e.add(rand.nextInt(100),'A',3);
		while(!e.isEmpty())
			System.out.println(e.poll());
	}
}

LinkedList支持双向队列

6.Map

 get()中使用线性搜索，执行速度会很慢，而HashMap使用了特殊的值，称作散列码。

HashMap就是使用对象的hashCode()进行快速查询，能提高性能。

SortedMap（TreeMap是其实现），可以确保键处于排序状态。

使用自己的类作为HashMap的键，必须同时重载hashCode()和equals()。

LinkedHashMap，才构造器中设置，使它采用基于访问的最近最少使用算法（LRU），

没有访问过的元素就会出现在队列前面。可以应用在需要定期清理元素以节省空间的程序。

例如：

package containers;
import java.util.*;
import tools.*;
import static tools.Print.*;
public class LinkedHashMapDemo {
	public static void main(String[] args){
		LinkedHashMap<Integer,String> linkedMap=new LinkedHashMap<Integer,String>(new CountingMapData(9));
		print(linkedMap);
		linkedMap=new LinkedHashMap<Integer,String>(16,0.75f,true);
		linkedMap.putAll(new CountingMapData(9));
		print(linkedMap);
		for(int i=0;i<6;i++)
			linkedMap.get(i);
		print(linkedMap);
		linkedMap.get(0);
		print(linkedMap);
	}
	
}

7.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)多少次，

返回的结果应该保持一致，要么一直是true，要么一直是false。

(5)对任何不是null的x，x.equals(null)一定返回false。

8.散列与散列码

(1) 使用散列的目的在于：想要使用一个对象来查找另一个对象。

散列的价值在于速度：散列使得查询得以快速进行。

(2)散列将键保存在某处，存储一组元素最快的数据结构是数组，所以用它来表示键的信息。

如果键的数量被数组容量限制了，该怎么办？

数组并不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个数字就是

散列码，由hashCode()方法生成，也称为散列函数。有时候会有冲突，数组多大已经不重要

了，任何键总能在数组中找到它的位置。

查询一个值的过程首先是计算散列码，然后使用散列码查询数组。

通常冲突由外部链接处理：数组并不直接保存值，而是保存值得list，然后对list中的值使用equals()

方法进行线性查询。这部分查询会比较慢，但是如果散列函数好的话，数组的每个位置只有较少的

值。

下面是散列原理的实现：

package containers;
import java.util.*;
import tools.*;
public class SimpleHashMap<K,V> extends AbstractMap<K,V>{
	//Choose a prime number for the hash table
	//size, to achieve a uniform distribution:
	static final int SIZE=997;
	//YOU can't have a physical array of generics,
	//but you can upcast to one:
	@SuppressWarnings("unchecked")
	LinkedList<MapEntry<K,V>>[] buckets=new LinkedList[SIZE];
	public V put(K key,V value){
		V oldValue=null;
		int index=Math.abs(key.hashCode())%SIZE;
		if(buckets[index]==null){
			buckets[index]=new LinkedList<MapEntry<K,V>>();
		}
		LinkedList<MapEntry<K,V>> bucket=buckets[index];
		MapEntry<K,V> pair=new MapEntry<K,V>(key,value);
		boolean found=false;
		ListIterator<MapEntry<K,V>> it=bucket.listIterator();
		while(it.hasNext()){
			MapEntry<K,V> iPair=it.next();
			if(iPair.getKey().equals(key)){
				oldValue=iPair.getValue();
				it.set(pair);
				found=true;
				break;
			}
		}
		if(!found)
			buckets[index].add(pair);
		return oldValue;
	}
	public V get(Object key){
		int index=Math.abs(key.hashCode())%SIZE;
		if(buckets[index]==null)	return null;
		for(MapEntry<K,V> iPair: buckets[index])
			if(iPair.getKey().equals(key))
				return iPair.getValue();
		return null;
	}
	public Set<Map.Entry<K, V>> entrySet(){
		Set<Map.Entry<K, V>> set=new HashSet<Map.Entry<K,V>>();
		for(LinkedList<MapEntry<K,V>> bucket:buckets){
			if(bucket==null)	continue;
			for(MapEntry<K,V> mpair:bucket)
				set.add(mpair);
		}
		return set;
	}
	public static void main(String[] args){
		SimpleHashMap<String,String> m=new SimpleHashMap<String,String>();
		m.put("a","A");
		m.put("b","B");
		System.out.println(m);
		System.out.println(m.get("b"));
	}
}

散列表中的“槽位”（slot）通常称为桶位（bucket） ，为使散列分布均匀，桶的数量使用质数。

为了自动处理冲突，使用了一个LinkedList的数组，每一个新的元素只是直接添加到list末尾的

某个特定桶位中。get和put使用相同的方式计算在buckets数组中的索引。

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

建议：

1.给int变量result赋予某个非零值常量；

2.为对象内每个有意义的域f（即每个可以做equals()操作的域）计算出一个int散列码c：

3.合并计算得到的散列码： result=37*result+c;

4.返回result

5.检查hashCode()最后生成的结果，确保相同的对象有相同的散列码。

例如：

public class CountedString {
	private static List<String> created=new ArrayList<String>();
	private String s;
	private char c;
    private int id=0;
	public int hashCode(){
		//The very simple approach:
		//return s.hashCode()*id:
		//using Joshua Bloch's recipe:
		int result=17;
		result=37*result+s.hashCode();
		result=37*result+(int)c;
		result=37*result+id;
		return result;
	}
}

9.选择接口的不同实现

容器之间的区别通常归结为由什么在背后“支持”它们。

剖析器可以把性能分析工作做得比较好，java提供了一个剖析器。

(1)ArrayList底层由数组支持；而LinkedList是由双向链表实现的，因此要经常在表中插入或删除元素

就用LinkedList，否则就使用ArrayList

(2)HashSet，查询最快；LinkedHashSet保持元素插入次序；TreeSet基于TreeMap，生成一个总是处于

排序状态的Set。注意，对于插入操作，LinkedHashSet比HashSet的代价更高；这是由维护链表所带来

额外开销造成的。

(3)Hashtable的性能大体上与HashMap相当，因为HashMap是用来替代Hashtable的，因此它们使用了相

同的底层存储和查找机制。当时用Map时，第一选择是HashMap，只有在需要Map保持有序时，才需要使

用TreeMap。LinkedHashMap在插入时比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表。

10.HashMap性能因子

我们可以通过手工调整HashMap来提高其性能。

容量：表中的桶位数。

初始容量：表在创建时所拥有的桶位数。HashMap和HashSet都允许你指定初始容量。

尺寸：表中当前存储的项数。

负载因子：尺寸/容量。空表的负载因子是0，而半满表的负载因子是0.5，以此类推。负载轻的表产生冲突的

可能性小，因此对于插入和查找都是最理想的。HashMap和HashSet都具有允许你指定负载因子的构造器，表

示当负载情况达到负载因子的水平时，容器将自动增加其容量（桶位数），实现方式是使容量大致加倍，并重

新将现有对象分布到新的桶位集中（这被称为再散列）。

HashMap使用的默认负载因子是0.75。更高的负载因子可以降低表所需的空间，当时会增加查找代价。所以你可

以根据需要创建一个具有恰当大小的初始容量，从而避免自动再散列的开销。

11.colletions

(1)设定Collection或Map为不可修改：

Collection<String> c=Collections.unmodifiableCollection(new ArrayList<String>(data));

(2)Collection或Map的同步控制：

Collection<String> c=Collections.synchronizedCollection(new ArrayList<String>());

(3)使用Collections.enumration()方法从Collection生成一个Enumberation

Enumration<String> e=v.elements();
e=Collections.enumeration(new ArrayList<String>());

12.持有引用

java.lang.ref类库包含了一组类，为垃圾回收提供了更大的灵活性。有三个继承自抽象类Reference的类：

SoftReference,WeakReference,PhantomReference。

如果想继续持有对某个对对象的引用，希望以后还能够访问到该对象，但是也希望能够允许垃圾回收器释

放它，这是就应该使用Reference对象。以Reference对象作为你和普通引用之间的媒介（代理），另外不

能有普通的引用指向那个对象。因为如果垃圾回收器发现某个对象通过普通引用是可获得的，该对象就不会

释放。

(1)SoftReference用来实现内存敏感的高速缓存。

(2)WeakReference是为实现“规范映射”而设计的，它不妨碍垃圾回收期回收映射的“键”（或“值”）。“规范映射”

中对象的实例可以在程序的多次被同时使用，以节省存储空间。

(3)Phantomreference用来调度回收前的清理工作，比java终止机制更灵活

package containers;
import java.lang.ref.*;
import java.util.*;
class VeryBig{
	private static final int SIZE=10000;
	private long[] la=new long[SIZE];
	private String ident;
	public VeryBig(String id){	ident=id;}
	public String toString(){	return ident;}
	protected void finalize(){
		System.out.println("Finalizing "+ident);
	}
}
public class References {
	private static ReferenceQueue<VeryBig> rq=new ReferenceQueue<VeryBig>();
	public static void checkQueue(){
		Reference<? extends VeryBig> inq=rq.poll();
		if(inq!=null)
			System.out.println("In queue: "+inq.get());
	}
	public static void main(String[] args){
		int size=10;
		SoftReference<VeryBig> s=new SoftReference<VeryBig>(new VeryBig("soft"));
		WeakReference<VeryBig> w=new WeakReference<VeryBig>(new VeryBig("Weak"));
		System.gc();
		LinkedList<PhantomReference<VeryBig>> pa=new 
                LinkedList<PhantomReference<VeryBig>>();
		for(int i=0;i<size;i++){
			pa.add(new PhantomReference<VeryBig>(new VeryBig("Phantom"+i),rq));
			System.out.println("just created: "+pa.getLast());
			checkQueue();
			
		}
	}
}

WeakHashMap：在映射中，每个值只保存一份实例以节省存储空间。当程序需要那个“值”时，便在

影视中查询现有的对象，然后只用它。允许垃圾回收器自动清理键和值，可以节省存储空间。

public class CanonicalMapping {
	public static void main(String[] args){
		WeakHashMap<Key,Value> map=new WeakHashMap<Key,Value>();
		for(int i=0;i<size;i++){
			Key k=new Key(Integer.toString(i));
			Value v=new Value(Integer.toString(i));
			if(i%3==0)
				keys[i]=k;
			map.put(k,v);
		}
		System.gc();
	}
}

总结

这一章最大的收获是怎么写散列函数，还有怎么为HashTable调优。