分类：
2008-11-18 20:18:02
使用LinkedList制作队列
LinkedList提供了方法以支持“队列”的行为，由此可以用来制作Queue类
import com.bruceeckel.simpletest.*;
import java.util.*;
public class Queue {
private static Test monitor = new Test();
private LinkedList list = new LinkedList();
public void put(Object v) { list.addFirst(v); }
public Object get() { return list.removeLast(); }
public boolean isEmpty() { return list.isEmpty(); }
public static void main(String[] args) {
Queue queue = new Queue();
for(int i = 0; i < 10; i++)
queue.put(Integer.toString(i));
while(!queue.isEmpty())
System.out.println(queue.get());
monitor.expect(new String[] {
"0",
"1",
"2",
"3",
"4",
"5",
"6",
"7",
"8",
"9"
});
}
} ///:~
Set的功能方法
Set具有与C哦来了此提哦那完全一样的接口，因此没有任何而外的功能。实际上Set就是Collection，只是行为不同。
SortedSet
使用SortedSet（TreeSet是器现阶段的唯一实现），可以确保元素处于排序状态，还可以使用SortedSet接口提供的附加功能。SortedSet的意思是“按对象的比较函数对元素排序”，而不是“元素传入的次序”。
import com.bruceeckel.simpletest.*;
import java.util.*;
public class SortedSetDemo {
private static Test monitor = new Test();
public static void main(String[] args) {
SortedSet sortedSet = new TreeSet(Arrays.asList(
"one two three four five six seven eight".split(" ")));
System.out.println(sortedSet);
Object
low = sortedSet.first(),
high = sortedSet.last();
System.out.println(low);
System.out.println(high);
Iterator it = sortedSet.iterator();
for(int i = 0; i <= 6; i++) {
if(i == 3) low = it.next();
if(i == 6) high = it.next();
else it.next();
}
System.out.println(low);
System.out.println(high);
System.out.println(sortedSet.subSet(low, high));
System.out.println(sortedSet.headSet(high));
System.out.println(sortedSet.tailSet(low));
monitor.expect(new String[] {
"[eight, five, four, one, seven, six, three, two]",
"eight",
"two",
"one",
"two",
"[one, seven, six, three]",
"[eight, five, four, one, seven, six, three]",
"[one, seven, six, three, two]"
});
}
} ///:~
性能是映射中的一个大问题。看看get()要做那些事，就会明白为什么在ArrayList中搜索“键”相当慢的；而这正是HashMap提高速度的地方。HashMap使用了特殊的值，称作“散列码”，来取代对“键”的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值，它是通过讲该对象的某个信息进行转换而生成。所有Java对象都能产生散类码，因为hash Code()是定义在基类Object中的方法。HashMap就是使用对的hashCode()进行快速查询的。此方法能够显著的提高性能。
import java.util.*;
class Counter {
int i = 1;
public String toString() { return Integer.toString(i); }
}
public class Statistics {
private static Random rand = new Random();
public static void main(String[] args) {
Map hm = new HashMap();
for(int i = 0; i < 10000; i++) {
// Produce a number between 0 and 20:
Integer r = new Integer(rand.nextInt(20));
if(hm.containsKey(r))
((Counter)hm.get(r)).i++;
else
hm.put(r, new Counter());
}
System.out.println(hm);
}
} ///:~
HashMap的toString()方法会遍历所有的键值对，并对每一个键值对调用toString()。Integer.toString()是预先定义好的，而且还可以看到Counter的toString()方法。程序的输出为：
{ 15=529,4=488,…………..}
SortMap
SortMap（TreeMap是其现阶段的唯一实现），可以确保“键”处于排序状态。
LinkedHashMap
LinkedHashMap散列化所有的元素，但是在遍历“键值对”时，却又以元素的插入顺序返回“键值对”（println()会迭代遍历该映射，由此可以看到遍历的结果）。此外，可以在构造器中设定LinkedHashMap，使之采用给予访问的“最近最少使用”（LRU）算法，于是没有被访问过的（可以看作需要删除的）元素就会出现在队列的前面。对于需要定期清理元素以节省空间的程序来说，此功能使得程序很容易得以实现。
import com.bruceeckel.simpletest.*;
import com.bruceeckel.util.*;
import java.util.*;
public class LinkedHashMapDemo {
private static Test monitor = new Test();
public static void main(String[] args) {
LinkedHashMap linkedMap = new LinkedHashMap();
Collections2.fill(
linkedMap, SimplePairGenerator.gen, 10);
System.out.println(linkedMap);
// Least-recently used order:
linkedMap = new LinkedHashMap(16,
Collections2.fill(
linkedMap, SimplePairGenerator.gen, 10);
System.out.println(linkedMap);
for(int i = 0; i < 7; i++) // Cause accesses:
linkedMap.get(SimplePairGenerator.gen.items[i].key);
System.out.println(linkedMap);
linkedMap.get(SimplePairGenerator.gen.items[0].key);
System.out.println(linkedMap);
monitor.expect(new String[] {
"{one=A, two=B, three=C, four=D, five=E, " +
"six=F, seven=G, eight=H, nine=I, ten=J}",
"{one=A, two=B, three=C, four=D, five=E, " +
"six=F, seven=G, eight=H, nine=I, ten=J}",
"{eight=H, nine=I, ten=J, one=A, two=B, " +
"three=C, four=D, five=E, six=F, seven=G}",
"{eight=H, nine=I, ten=J, two=B, three=C, " +
"four=D, five=E, six=F, seven=G, one=A}"
});
}
} ///:~
“键值对”是以插入的顺序进行遍历的，甚至LRU算法的版本也是如此。在（只）访问过前面的七个元素后，最后三个元素一道了队列前面。然后在一次访问元素“one”时，它就被移到队列后端了。
散列码与散列法
在Statics.java中，标准类库中的类（Integer）被用作HashMap的“键”。它用得很好，因为它具备了“键”所需的全部性质。但是，如果自己创建类作为HashMap的“键”使用，通常会犯一个错误。
import com.bruceeckel.simpletest.*;
import java.util.*;
import java.lang.reflect.*;
public class SpringDetector {
private static Test monitor = new Test();
// Uses a Groundhog or class derived from Groundhog:
public static void
detectSpring(Class groundHogClass) throws Exception {
Constructor ghog = groundHogClass.getConstructor(
new Class[] {int.class});
Map map = new HashMap();
for(int i = 0; i < 10; i++)
map.put(ghog.newInstance(
new Object[]{ new Integer(i) }), new Prediction());
System.out.println("map = " + map + "\n");
Groundhog gh = (Groundhog)
ghog.newInstance(new Object[]{ new Integer(3) });
System.out.println("Looking up prediction for " + gh);
if(map.containsKey(gh))
System.out.println((Prediction)map.get(gh));
else
System.out.println("Key not found: " + gh);
}
public static void main(String[] args) throws Exception {
detectSpring(Groundhog.class);
monitor.expect(new String[] {
"%% map = \\{(Groundhog #\\d=" +
"(Early Spring!|Six more weeks of Winter!)" +
"(, )?){10}\\}",
"",
"Looking up prediction for Groundhog #3",
"Key not found: Groundhog #3"
});
}
} ///:~
问题出在Groundhog继承自Object。所以这里是使用Object 的hashCode()方法生成散列码，而它默认是使用对象的地址计算散列码。因此，由Groundhog(3)生成的第一个实例的散列码与由Groundhog(3)生成的第二个实例的散列码是不同的，而我们正是使用后者进行查找的。
如果只编写hashCode()方法的覆盖版本，仍然无法正常运行，除非同时覆盖equals()方法，它也是Object的一部分。
默认的Object.equals()只是比较对象的地址，如果要使用自己类作为HashMap的“键”，必须同时重载hashCode()和equals()。
public class Groundhog2 extends Groundhog {
public Groundhog2(int n) { super(n); }
public int hashCode() { return number; }
public boolean equals(Object o) {
return (o instanceof Groundhog2)
&& (number == ((Groundhog2)o).number);
}
} ///:~
HashMap速度快的原因
散列将“键”保存在某处，以便能够很快找到。因为数组的速度很快，所以用它来保存“键”的信息（而不是“键”本身）。解决数组容量固定对保存“键”信息影响的问题，数组保存通过“键”对象生成的一个数字，将其作为数组的下标。这个数字就是散列码，由定义在Object中的、且可能由你的覆盖的hashCode()（散列函数）方法生成，不同的“键”可以产生相同的下标。也就是说，可能会由冲突。因此，数组多大就不重要了，每个“键”总能在数组中找到它的位置。
于是查询一个“值”的过程首先就是计算散列码，然后使用散列码查询数组。如果能够保证没有冲突（如果“值”的数量是固定的，那么就由可能），那可就由一个完美的散列函数，但是这种情况只是特例。通常，冲突由“外部链接”处理：数组并不直接保存“值”，而是保存“值”的list。然后对list中的“值”使用equals()方法进行线性查询。这部分的查询自然会比较慢，但是，如果散列函数好的化，数组的每个位置就只有较少的“值”。因此，不是查询这个list，而是快速地跳到数组的某个位置，只对很少的元素进行比较。
import java.util.*;
import com.bruceeckel.util.*;
public class SimpleHashMap extends AbstractMap {
// Choose a prime number for the hash table
// size, to achieve a uniform distribution:
private static final int SZ = 997;
private LinkedList[] bucket = new LinkedList[SZ];
public Object put(Object key, Object value) {
Object result = null;
int index = key.hashCode() % SZ;
if(index < 0) index = -index;
if(bucket[index] == null)
bucket[index] = new LinkedList();
LinkedList pairs = bucket[index];
MPair pair = new MPair(key, value);
ListIterator it = pairs.listIterator();
boolean found = false;
while(it.hasNext()) {
Object iPair = it.next();
if(iPair.equals(pair)) {
result = ((MPair)iPair).getValue();
it.set(pair); // Replace old with new
found = true;
break;
}
}
if(!found)
bucket[index].add(pair);
return result;
}
public Object get(Object key) {
int index = key.hashCode() % SZ;
if(index < 0) index = -index;
if(bucket[index] == null) return null;
LinkedList pairs = bucket[index];
MPair match = new MPair(key, null);
ListIterator it = pairs.listIterator();
while(it.hasNext()) {
Object iPair = it.next();
if(iPair.equals(match))
return ((MPair)iPair).getValue();
}
return null;
}
public Set entrySet() {
Set entries = new HashSet();
for(int i = 0; i < bucket.length; i++) {
if(bucket[i] == null) continue;
Iterator it = bucket[i].iterator();
while(it.hasNext())
entries.add(it.next());
}
return entries;
}
public static void main(String[] args) {
SimpleHashMap m = new SimpleHashMap();
Collections2.fill(m, Collections2.geography, 25);
System.out.println(m);
}
} ///:~
注意：为了能够自动处理冲突，使用了一个LinkedList数组；每一个元素只是直接添加到list的末尾。
如果指定的“键”已经存在于list中了，那么put()将返回于此“键”相关联的旧“值”，否则返回null。
HashMap的性能因子
容量（capacity）：散列标中桶的数量。
初始化容量（initial capacity）：创建散列标时桶的数量。
尺寸（size）：当前散列表中记录的数量。
负载因子（load factor）：等于“尺寸/容量”。轻伏在的散列表具有冲突少、适宜插入与查询的特点（但是使用迭代器会变慢）。当负载达到指定值时，容器会自动成倍的增加容量（桶的数量），并将原有的对象重新分配，存入新的桶内（这称为“重散列”）。
如果知道HashMap中会由很多基类，载创建的时候就使用较大的初始化容量，可以避免自动重散列的开销。
设计hashCode()时最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该生成同样的值。
此外，也不应该使hashCode()依赖于具体唯一性的对象信息，尤其是使用this的值，这只能产生很糟糕的hashCode()。
import com.bruceeckel.simpletest.*;
public class StringHashCode {
private static Test monitor = new Test();
public static void main(String[] args) {
System.out.println("Hello".hashCode());
System.out.println("Hello".hashCode());
monitor.expect(new String[] {
"69609650",
"69609650"
});
}
} ///:~
对于String而言，hashCode()明显是给予String的内容的。
散列码不必是独一无二的（应该更关注生成速度，而不是唯一性），但是通过hashCode()和equals()，必须能够完全确定对象的身份。
好的hashCode()应该产生分布均匀的散列码。
Effective Java对于hashCode()的基本指导：
1） 给int变量result赋予某个非零值常量，例如17。
2） 为对象内每个由意义的字段f（即每个可以做equals()操作的字段）计算处一个int散列码c
3） 合并计算得到的散列码：
result = 37 * result + c;
4) 返回result
5）检查hashCode()最后是产生的结果，确保相同的对象有相同的散列码。
import com.bruceeckel.simpletest.*;
import java.util.*;
public class CountedString {
private static Test monitor = new Test();
private static List created = new ArrayList();
private String s;
private int id = 0;
public CountedString(String str) {
s = str;
created.add(s);
Iterator it = created.iterator();
// Id is the total number of instances
// of this string in use by CountedString:
while(it.hasNext())
if(it.next().equals(s))
id++;
}
public String toString() {
return "String: " + s + " id: " + id +
" hashCode(): " + hashCode();
}
public int hashCode() {
// Very simple approach:
// return s.hashCode() * id;
Using Joshua Bloch's recipe:
result = 17;
ult = 37*result + s.hashCode();
sult = 37*result + id;
return result;
}
public boolean equals(Object o) {
return (o instanceof CountedString)
&& s.equals(((CountedString)o).s)
&& id == ((CountedString)o).id;
}
public static void main(String[] args) {
Map map = new HashMap();
CountedString[] cs = new CountedString[10];
for(int i = 0; i < cs.length; i++) {
cs[i] = new CountedString("hi");
map.put(cs[i], new Integer(i));
}
System.out.println(map);
for(int i = 0; i < cs.length; i++) {
System.out.println("Looking up " + cs[i]);
System.out.println(map.get(cs[i]));
}
monitor.expect(new String[] {
"{String: hi id: 4 hashCode(): 146450=3," +
" String: hi id: 10 hashCode(): 146456=9," +
" String: hi id: 6 hashCode(): 146452=5," +
" String: hi id: 1 hashCode(): 146447=0," +
" String: hi id: 9 hashCode(): 146455=8," +
" String: hi id: 8 hashCode(): 146454=7," +
" String: hi id: 3 hashCode(): 146449=2," +
" String: hi id: 5 hashCode(): 146451=4," +
" String: hi id: 7 hashCode(): 146453=6," +
" String: hi id: 2 hashCode(): 146448=1}",
"Looking up String: hi id: 1 hashCode(): 146447",
"0",
"Looking up String: hi id: 2 hashCode(): 146448",
"1",
"Looking up String: hi id: 3 hashCode(): 146449",
"2",
"Looking up String: hi id: 4 hashCode(): 146450",
"3",
"Looking up String: hi id: 5 hashCode(): 146451",
"4",
"Looking up String: hi id: 6 hashCode(): 146452",
"5",
"Looking up String: hi id: 7 hashCode(): 146453",
"6",
"Looking up String: hi id: 8 hashCode(): 146454",
"7",
"Looking up String: hi id: 9 hashCode(): 146455",
"8",
"Looking up String: hi id: 10 hashCode(): 146456",
"9"
});
}
} ///:~
选择接口的不同实现
HashSet是最常用的，查询速度最快；LinkedHashSet保持元素插入的次序；TreeSet给予TreeMap，生成一个总是处于排序状态的Set。
对List的选择
一个例子的测试结果：
ArrayList的开销对于LinkedList。（奇怪的是，对于迭代遍历操作，LinkedList比ArrayList要快，这一点有悖于直觉）。另以方面，从中间的位置插入和删除元素，LinkedList要比ArrayList快，特别是删除操作。Vector通常比ArrayList慢。
对Set的选择
HashSet的性能总是比TreeSet好（特别是最常用的添加和查询元素操作）。TreeSet存在的唯一原因是它可以维持元素的排序状态。
对于插入操作，LinkedHashSet比HashSet略微慢一点；这是维护链表所带来的额外开销造成的。不过，因为有了链表，遍历LinkedHashSet会更快。
Map的尺寸是影响性能的最重要因素。
List的排序和查询
import com.bruceeckel.util.*;
import java.util.*;
public class ListSortSearch {
public static void main(String[] args) {
List list = new ArrayList();
Collections2.fill(list, Collections2.capitals, 25);
System.out.println(list + "\n");
Collections.shuffle(list);
System.out.println("After shuffling: " + list);
Collections.sort(list);
System.out.println(list + "\n");
Object key = list.get(12);
int index = Collections.binarySearch(list, key);
System.out.println("Location of " + key +
" is " + index + ", list.get(" +
index + ") = " + list.get(index));
AlphabeticComparator comp = new AlphabeticComparator();
Collections.sort(list, comp);
System.out.println(list + "\n");
key = list.get(12);
index = Collections.binarySearch(list, key, comp);
System.out.println("Location of " + key +
" is " + index + ", list.get(" +
index + ") = " + list.get(index));
}
} ///:~
如果使用Comparator进行排序，那么binarySearch()必须使用相同的Comparator。
Collection类的一些实用方法：
Collection 和Map的同步控制
import java.util.*;
public class Synchronization {
public static void main(String[] args) {
Collection c =
Collections.synchronizedCollection(new ArrayList());
List list =
Collections.synchronizedList(new ArrayList());
Set s = Collections.synchronizedSet(new HashSet());
Map m = Collections.synchronizedMap(new HashMap());
}
} ///:~
快速报错
Java容器有一种保护机制，能够防止多个进程同时修改同一个容器的内容。如果你正在迭代遍历某个容器，此时另一个进程介入其中，并且插入、删除或修改此容器内的某个对象，那么就会发生问题，抛出ConcurrentModificationException异常。
import java.util.*;
public class FailFast {
public static void main(String[] args) {
Collection c = new ArrayList();
Iterator it = c.iterator();
c.add("An object");
// Causes an exception:
String s = (String)it.next();
}
} ///:~
