第十七章 容器深入研究
文章目录1.完整的容器分类法2.填充容器复制同一个对象引用来填充容器一种Generator解决方案Map生成器使用Abstract类3.Collection的功能方法4.可选操作5.List的功能方法6.Set和存储顺序类型从输出看出SortedSet7.队列优先级队列双向队列8.理解Map标准的Java类库中包含了Map的几种基本实现，包括：实现Map接口SortedMapLinkedHashM
·
文章目录
1.完整的容器分类法
2.填充容器
- (1) Collections.nCopies()
- (2) Collections.fill()
- (1) 所有的Collection子类型都有一个接收另一个Collection对象的构造器，用所接收的Collection对象中的元素来填充新的容器
- (2) 泛型便利方法（例如addAll()）可以减少在使用类时所必需的类型检查数量
- (1) 例
package Chapter17.Example;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
class Letters implements Generator<Pair<Integer, String>>,
Iterable<Integer> {
private int size = 9;
private int number = 1;
private char letter = 'A';
public Pair<Integer, String> next() {
return new Pair<Integer, String>(
number++, "" + letter++);
}
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
public Integer next() {
return number++;
}
public boolean hasNext() {
return number < size;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
package Chapter17.Example;
import net.mindview.util.Generator;
import java.util.Iterator;
import java.util.LinkedHashMap;
public class MapData<K, V> extends LinkedHashMap<K, V> {
public MapData(Generator<Pair<K, V>> gen, int quantity) {
for(int i = 0; i < quantity; ++i) {
Pair<K, V> p = (Pair)gen.next();
this.put(p.key, p.value);
}
}
public MapData(Generator<K> genK, Generator<V> genV, int quantity) {
for(int i = 0; i < quantity; ++i) {
this.put(genK.next(), genV.next());
}
}
public MapData(Generator<K> genK, V value, int quantity) {
for(int i = 0; i < quantity; ++i) {
this.put(genK.next(), value);
}
}
public MapData(Iterable<K> genK, Generator<V> genV) {
Iterator var4 = genK.iterator();
while(var4.hasNext()) {
K key = (K) var4.next();
this.put(key, genV.next());
}
}
public MapData(Iterable<K> genK, V value) {
Iterator var4 = genK.iterator();
while(var4.hasNext()) {
K key = (K) var4.next();
this.put(key, value);
}
}
public static <K, V> MapData<K, V> map(Generator<Pair<K, V>> gen, int quantity) {
return new MapData(gen, quantity);
}
public static <K, V> MapData<K, V> map(Generator<K> genK, Generator<V> genV, int quantity) {
return new MapData(genK, genV, quantity);
}
public static <K, V> MapData<K, V> map(Generator<K> genK, V value, int quantity) {
return new MapData(genK, value, quantity);
}
public static <K, V> MapData<K, V> map(Iterable<K> genK, Generator<V> genV) {
return new MapData(genK, genV);
}
public static <K, V> MapData<K, V> map(Iterable<K> genK, V value) {
return new MapData(genK, value);
}
}
package Chapter17.Example;
import net.mindview.util.CountingGenerator;
import net.mindview.util.RandomGenerator;
import static net.mindview.util.Print.print;
public class MapDataTest {
public static void main(String[] args) {
// Pair Generator:
print(MapData.map(new Letters(), 11));
// Two separate generators:
print(MapData.map(new CountingGenerator.Character(),
new RandomGenerator.String(3), 8));
// A key Generator and a single value:
print(MapData.map(new CountingGenerator.Character(),
"Value", 6));
// An Iterable and a value Generator:
print(MapData.map(new Letters(),
new RandomGenerator.String(3)));
// An Iterable and a single value:
print(MapData.map(new Letters(), "Pop"));
}
}
package Chapter17.Example;
public class Pair<K, V> {
public final K key;
public final V value;
public Pair(K k, V v) {
key = k;
value = v;
}
}
- (2) 创建一个Pair<V，K>类，再调用Generator.next()方法来组装Map
- (3) Map适配器可以使用各种不同的Generator、Iterator和常量值的组合来填充Map初始化对象
- (4) 通过产生一个Iterator还实现了Iterable。
- (1) 例：
package Chapter17.Test5;
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 class Entry implements Map.Entry<Integer, String> {
int index;
Entry(int index) {
this.index = index;
}
public boolean equals(Object o) {
return o instanceof Entry && index == ((Entry) o).index;
}
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();
}
}
class EntrySet extends AbstractSet<Map.Entry<Integer, String>> {
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();
}
}
private Set<Map.Entry<Integer, String>> entries =
new EntrySet();
public Set<Map.Entry<Integer, String>> entrySet() {
return entries;
}
}
package Chapter17.Test5;
public class Test5 {
public static void main(String[] args) {
System.out.println(new CountingMapData(60));
}
}
- (1) 产生容器的测试数据：创建定制的Collection和Map实现
- (2) 享元设计模式：在普通的解决方案需要过多的对象，或者产生普通对象太占用空间时使用享元
- (3) 为了创建只读的Map，可以继承AbstractMap并实现entrySet()。为了创建只读的Set，可以继承AbstractSet并实现iterator()和size()
3.Collection的功能方法
- boolean add(T)：像容器添加内容添加失败返回false
- boolean addAll(Collection<? extends E> c)：添加参数中所有元素，有任意元素添加成功则返回true
- void clear()：移除容器中所有元素
- boolean contains(T)：如果容器已经持有泛型类型T的参数，则返回true
- boolean containsAll(Collection<?>)：如果容器中持有参数中所有元素返回true
- boolean isEmpty()：容器中没有元素，返回true
- Iterator iterator()：返回一个Iterator，可用来遍历容器中的元素
- boolean remove(Object o)：如果元素再容器中，则移除一个元素实例。如果做了移除动作，则返回true
- boolean removeAll(Collection<?> c)：一处参数中所有元素。如果有移除动作，则返回true
- boolean retainAll(Collection<?> c)：只保存参数中元素。Collection发生改变返回true
- int size()：返回容器中元素数目
- Object[] toArray()：返回一个数组，该数组包含容器中所有元素
- T[] toArray(T[] a)：返回一个包含所有容器内元素的数组，但返回类型为T而不简单是Object
4.可选操作
- 执行各种不同的添加和移除的方法在Collection接口中都是可选操作。这意味着实现类并不需要为这些方法提供功能定义
- “可选操作”可以防止设计中出现接口爆炸的情况
- 容器应该易学易用，未获得支持的操作时一种特例，可以延迟到需要时再实现
- 如果一个操作未获得支持，那么实现接口会导致UnsupportedOperationException异常
- 未获支持的操作
- (1) 最常见的未获支持的操作，都是源于背后由固定尺寸的数据结构支持的容器
- (2) 任何会引起对底层数据结构的尺寸进行修改的方法都会产生一个UnsupportedOperationException异常，以表示对未获支持操作的调用（一个编程错误）
- (3) 未获支持的操作只有在运行时才能检测到，因此它们表示动态类型检查
5.List的功能方法
- 基本的List很容易使用：大多数时候只是调用add()添加对象，使用get()一次取出一个元素，以及调用iterator()获取用于该序列的Iterator
package Chapter17.Example2;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class Lists {
private static boolean b;
private static String s;
private static int i;
private static Iterator<String> it;
private static ListIterator<String> lit;
public static void basicTest(List<String> a) {//包含每个List都可执行的操作
a.add(1, "x"); // Add at location 1
a.add("x"); // Add at end
// Add a collection:
a.addAll(Countries.names(25));
// Add a collection starting at location 3:
a.addAll(3, Countries.names(25));
b = a.contains("1"); // Is it in there?
// Is the entire collection in there?
b = a.containsAll(Countries.names(25));
// Lists allow random access, which is cheap
// for ArrayList, expensive for LinkedList:
s = a.get(1); // Get (typed) object at location 1
i = a.indexOf("1"); // Tell index of object
b = a.isEmpty(); // Any elements inside?
it = a.iterator(); // Ordinary Iterator
lit = a.listIterator(); // ListIterator
lit = a.listIterator(3); // Start at loc 3
i = a.lastIndexOf("1"); // Last match
a.remove(1); // Remove location 1
a.remove("3"); // Remove this object
a.set(1, "y"); // Set location 1 to "y"
// Keep everything that's in the argument
// (the intersection of the two sets):
a.retainAll(Countries.names(25));
// Remove everything that's in the argument:
a.removeAll(Countries.names(25));
i = a.size(); // How big is it?
a.clear(); // Remove all elements
}
public static void iterMotion(List<String> a) {//使用Iterator遍历元素
ListIterator<String> it = a.listIterator();
b = it.hasNext();
b = it.hasPrevious();
s = it.next();
i = it.nextIndex();
s = it.previous();
i = it.previousIndex();
}
public static void iterManipulation(List<String> a) {//使用Iterator修改元素
ListIterator<String> it = a.listIterator();
it.add("47");
// Must move to an element after add():
it.next();
// Remove the element after the newly produced one:
it.remove();
// Must move to an element after remove():
it.next();
// Change the element after the deleted one:
it.set("47");
}
public static void testVisual(List<String> a) {//查看List的操作效果
print(a);
List<String> b = Countries.names(25);
print("b = " + b);
a.addAll(b);
a.addAll(b);
print(a);
// Insert, remove, and replace elements
// using a ListIterator:
ListIterator<String> x = a.listIterator(a.size() / 2);
x.add("one");
print(a);
print(x.next());
x.remove();
print(x.next());
x.set("47");
print(a);
// Traverse the list backwards:
x = a.listIterator(a.size());
while (x.hasPrevious())
printnb(x.previous() + " ");
print();
print("testVisual finished");
}
// There are some things that only LinkedLists can do:
public static void testLinkedList() {//LinkedList专用的操作
LinkedList<String> ll = new LinkedList<String>();
ll.addAll(Countries.names(25));
print(ll);
// Treat it like a stack, pushing:
ll.addFirst("one");
ll.addFirst("two");
print(ll);
// Like "peeking" at the top of a stack:
print(ll.getFirst());
// Like popping a stack:
print(ll.removeFirst());
print(ll.removeFirst());
// Treat it like a queue, pulling elements
// off the tail end:
print(ll.removeLast());
print(ll);
}
public static void main(String[] args) {
// Make and fill a new list each time:
basicTest(
new LinkedList<String>(Countries.names(25)));
basicTest(
new ArrayList<String>(Countries.names(25)));
iterMotion(
new LinkedList<String>(Countries.names(25)));
iterMotion(
new ArrayList<String>(Countries.names(25)));
iterManipulation(
new LinkedList<String>(Countries.names(25)));
iterManipulation(
new ArrayList<String>(Countries.names(25)));
testVisual(
new LinkedList<String>(Countries.names(25)));
testLinkedList();
}
} /* (Execute to see output) *///:~
6.Set和存储顺序
- (1) Set(interface)：存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。
- (2) HashSet：为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()
- (3) TreeSet：保持次序的Set，底层为树结构。使用它可以从set中提取有序的序列。元素必须实现Comparable接口
- (4) LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序。元素也必须实现hashCode()方法
- (1) HashSet以某种神秘的顺序保存所有的元素
- (2) LinkedHashSet按照元素插入的顺序保存元素
- (3) 而TreeSet按照排序顺序维护元素（按照CompareTo()的实现方式）
- (1) SortedSet中的元素可以保证处于排序状态
- (2) SortSet：按对象的比较函数对元素排列
- (3) Comparator comparator() 返回当前Set使用的Comparator；或者返回null，表示以自然方式排序
- (4) Object first() 返回容器中第一个元素
- (5) Object last()返回容器最后一个元素
- (6) SortedSet subSet(from,to)生成此Set子集，范围从from(包含)到 to(不包含)
- (7) SortSet headSet(to) 生成此Set子集，由 小于 to的元素组成
- (8) SortSet tailSet(to) 生成此Set子集，由 大于或等于 from的元素组成
7.队列
- (1)
package Chapter17.Example3;
import java.util.*;
/**
* @author:YiMing
* @version:1.0
*/
class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {
static class ToDoItem implements Comparable<ToDoItem> {
private char primary;
private int secondary;
private String item;
public ToDoItem(String td, char pri, int sec) {
primary = pri;
secondary = sec;
item = td;
}
/**
* compareable接口里面就是这么申明的，比较两个数，
* 1.大于0就是说明是大于的关系，
* 2.小于0就说明是小于的关系，
* 3.等于0就说明是相等的关系
* @param arg
* @return
*/
public int compareTo(ToDoItem arg) {
if (primary > arg.primary)
return +1;
if (primary == arg.primary)
if (secondary > arg.secondary)
return +1;
else if (secondary == arg.secondary)
return 0;
return -1;
}
public String toString() {
return Character.toString(primary) +
secondary + ": " + item;
}
}
public void add(String td, char pri, int sec) {
super.add(new ToDoItem(td, pri, sec));
}
public static void main(String[] args) {
ToDoList toDoList = new ToDoList();
toDoList.add("Empty trash", 'C', 4);
toDoList.add("Feed dog", 'A', 2);
toDoList.add("Feed bird", 'B', 7);
toDoList.add("Mow lawn", 'C', 3);
toDoList.add("Water lawn", 'A', 1);
toDoList.add("Feed cat", 'B', 1);
while (!toDoList.isEmpty()) System.out.println(toDoList.remove());
}
} /* Output:
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty trash
*///:~
- (2) 优先队列通过实现Comparable进行控制
- (1)
package Chapter17.Example4;
import java.util.LinkedList;
public class Deque<T> {
private LinkedList<T> deque = new LinkedList();
public Deque() {
}
public void addFirst(T e) {
this.deque.addFirst(e);
}
public void addLast(T e) {
this.deque.addLast(e);
}
public T getFirst() {
return this.deque.getFirst();
}
public T getLast() {
return this.deque.getLast();
}
public T removeFirst() {
return this.deque.removeFirst();
}
public T removeLast() {
return this.deque.removeLast();
}
public int size() {
return this.deque.size();
}
public String toString() {
return this.deque.toString();
}
}
package Chapter17.Example4;
import static net.mindview.util.Print.*;
public class DequeTest {
static void fillTest(Deque<Integer> deque) {
for (int i = 20; i < 27; i++)
deque.addFirst(i);
for (int i = 50; i < 55; i++)
deque.addLast(i);
}
public static void main(String[] args) {
Deque<Integer> di = new Deque<Integer>();
fillTest(di);
print(di);
while (di.size() != 0)
printnb(di.removeFirst() + " ");
print();
fillTest(di);
while (di.size() != 0)
printnb(di.removeLast() + " ");
}
} /* Output:
[26, 25, 24, 23, 22, 21, 20, 50, 51, 52, 53, 54]
26 25 24 23 22 21 20 50 51 52 53 54
54 53 52 51 50 20 21 22 23 24 25 26
*///:~
- (2) 双向队列可以在任何一端添加或移除元素
- (3) 可以使用组合来创建一个Deque类，并直接从LinkedList中暴露相关的方法
8.理解Map
- (1) HashMap
- (2) TreeMap
- (3) LinkedHashMap
- (4) WeakHashMap
- (5) ConcurrentHashMap
- (6) IdentityHashMap
- (1) HashMap
- Map基于散列表的实现（取代了Hashtable）。插入和查询键值对的开销是固定的。可以i通过构造器设置容量和负载因子，以调整容器的性能
- (2) LinkedHashMap
- 类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)次序。只比HashMap慢一点。而在迭代访问时反而更快，因为它使用链表维护内部次序
- (3) TreeMap
- 基于红黑树实现。查看“键”或“键值对”时，他们会被排序（次序由Comparable或Comparator决定）TreeMap的特点在于，所得到的结果是经过排序的。TreeMap是唯一带有subMap()方法的Map，他返回一个子树
- (4) WeakHashMap
- 弱键 映射，允许释放映射所指向的对象；这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个“键”，则此“键”可以被垃圾收集器回收
- (5) ConcurrentHashMap
- 一种线程安全的Map，它不涉及同步枷锁。
- (6) IdentityHashMap
- 使用==代替equals()对“键”进行比较的散列映射
- (1) 使用SortedMap（TreeMap是其现阶段的唯一实现），可以确保键处于排序状态
- (2) Comparator comparator()：返回当前Map使用的Comparator;或者返回null，以表示自然排序
- (3) T firstKey()：返回Map中的第一个键
- (4) T lastKey()：返回Map中的最后一个键
- (5) SortMap subMap(fromKet,toKey)：生成此Map的子集，范围从fromKey（包含）到toKey（不包含）的键确定
- (6) SortMap headMap(toKey)：生成此Map的子集，由键 小于toKey的所有键值对组成
- (7) SortMap tailMap(fromKey)：生成此Map的子集，由键 大于或等于 fromeKey的所有键值对组成
- (1) 为了提高速度，LinkedHashMap散列化所有的元素，但是在遍历键值对时，却又以元素的插入顺序返回键值对
- (2) 可以在构造器中设定LinkedHashMap，使之采用基于访问最近最少使用算法，于是没有被访问过的元素就会出现在队列的前面
- (3)
package Chapter17.Example5;
import java.util.*;
import net.mindview.util.*;
import static net.mindview.util.Print.*;
public class LinkedHashMapDemo {
public static void main(String[] args) {
LinkedHashMap<Integer, String> linkedMap =
new LinkedHashMap<Integer, String>(
new CountingMapData(9));
print(linkedMap);
// Least-recently-used order:
linkedMap =
new LinkedHashMap<Integer, String>(16, 0.75f, true);
linkedMap.putAll(new CountingMapData(9));
print(linkedMap);
for (int i = 0; i < 6; i++) // Cause accesses:
linkedMap.get(i);//访问前五个后，就被放在最后面了，最后的6，7，8被提前了
print(linkedMap);
linkedMap.get(0);//访问过“0“后也被放到了最后
print(linkedMap);
}
} /* Output:
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 6=G0, 7=H0, 8=I0}
{6=G0, 7=H0, 8=I0, 0=A0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0}
{6=G0, 7=H0, 8=I0, 1=B0, 2=C0, 3=D0, 4=E0, 5=F0, 0=A0}
*///:~
9.散列与散列码
- hashMap使用equals()判断当前的键是否与表中存在的键相同
2 ###### 正确的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。
- 如果要使用自己的类作为HashMap的键，必须同时重载hashCode()和equals()
- 理解hashCode()
- 使用散列的目的在于：想要使用一个对象来查找另一个对象
- (1)
package Chapter17.Example6;
import Chapter17.Test15.MapEntry;
import net.mindview.util.Countries;
import java.util.*;
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); // Replace old with new
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<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.putAll(Countries.capitals(25));
System.out.println(m);
System.out.println(m.get("ERITREA"));
System.out.println(m.entrySet());
}
}
- (2) 散列的价值在于速度：散列使得查询得以快速进行
- (3) 数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码，由定义在Object中的、且可能由你的类覆盖的hashCode()方法生成
- (4) HashMap快的原因：不是查询整个list，而是快速地跳到数组的某个位置，只对很少的元素进行比较
- (5) 由于散列表中的“槽位”（slot）通常称为桶位（bucket），因此我们将表示实际散列表的数组命名为bucket。为使散列分布均匀，同的数量通常使用质数
- (6) 为了能够自动处理冲突，使用一个LinkedList的数组；每一个新的元素只是直接添加到list末尾的某个特定桶中
-
(1) 你无法控制bucket数组的下标值的产生。这个值依赖于具体的HashMap对象的容量，而容量的改变与容器的充满程度和负载因子有关
-
(2) 设计hashCode()是最重要的因素是：无论何时，对同一个对象调用hasCode()都应该生成个同样的值
-
(3) 如果你的hashCode()方法依赖于对象中易变的数据，因此数据发生变化时，hashCode()就会生成一个不同的散列码，相当于产生了一个不同的键
-
(4) 不应该使hashCode()依赖于具有唯一型的对象信息，尤其是使用this值，这只能产生很糟糕的hashCode()，应为这样无法生成一个新的键，使之与put()中源氏键值相同
-
(5) String有个特点：如果程序中有多个String对象，都包含相同的字符串序列，那么这些String对象都映射到同一块内存区域
-
(6) 怎样写出一份像样的hashCode基本指导
-
i.
package Chapter17.Example7; import java.util.*; import static net.mindview.util.Print.*; public class CountedString { private static List<String> created = new ArrayList<String>(); private String s; private int id = 0; public CountedString(String str) { s = str; created.add(s); // id is the total number of instances // of this string in use by CountedString: for(String s2 : created) if(s2.equals(s)) id++; } public String toString() { return "String: " + s + " id: " + id + " hashCode(): " + hashCode(); } 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 + 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<CountedString,Integer> map = new HashMap<CountedString,Integer>(); CountedString[] cs = new CountedString[5]; for(int i = 0; i < cs.length; i++) { cs[i] = new CountedString("hi"); map.put(cs[i], i); // Autobox int -> Integer } print(map); for(CountedString cstring : cs) { print("Looking up " + cstring); print(map.get(cstring)); } } } /* Output: (Sample) {String: hi id: 4 hashCode(): 146450=3, String: hi id: 1 hashCode(): 146447=0, String: hi id: 3 hashCode(): 146449=2, String: hi id: 5 hashCode(): 146451=4, 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 *///:~ -
ii.给int变量result赋予某个非零值常量。例如17
-
iii.为对象内每个有意义的域f计算一个int散列码c：
- boolean
- c=(f?0:1)
- byte,char,short或int
- c=(int)f
- long
- c=(int)(f^(f>>>32))
- float
- c=Float.float.ToIntBits(f)
- double
- long l=Doule.doubleToLongBits(f);c=(int)(l^(l>>>32))
- object,其equals()调用这个域的equals()
- c=f.hashCode()
- 数组
- 对每个元素应用上述规则
- boolean
-
iv.返回result
-
v.检查hashCode()最后生成结果，确保相同的对象有相同的散列码。
-
-
(7) compareTo()方法有一个比较结构，因此它会产生一个排序序列，排序规则首先按照实际类型排序，然后如果有名字按名字排序，最后按创建顺序排序：
package Chapter17.Example7; import typeinfo.pets.Individual; import typeinfo.pets.Pet; import java.util.*; public class IndividualTest { public static void main(String[] args) { Set<Individual> pets = new TreeSet<Individual>(); for(List<? extends Pet> lp : MapOfList.petPeople.values()) for(Pet p : lp) pets.add(p); System.out.println(pets); } } /* Output: [Cat Elsie May, Cat Pinkola, Cat Shackleton, Cat Stanford aka Stinky el Negro, Cymric Molly, Dog Margrett, Mutt Spot, Pug Louie aka Louis Snorkelstein Dupree, Rat Fizzy, Rat Freckly, Rat Fuzzy] *///:~
10.选择接口的不同实现
- (1) ArrayList（底层由数组支持）
- (2) LinkedList（底层由双向链表实现）
- (1) HashSet（查询速度最快）
- (2) LinkedHashSet（保持元素插入顺序）
- (3) TreeSet（基于TreeMap，生成一个总是处于排序状态的Set）
- 性能测试框架
package Chapter17.Example8;
// Framework for performing timed tests of containers.
public abstract class Test<C> {
String name;
public Test(String name) { this.name = name; }
// Override this method for different tests.
// Returns actual number of repetitions of test.
abstract int test(C container, TestParam tp);
} ///:~
package Chapter17.Example8;
// Applies Test objects to lists of different containers.
import java.util.*;
public class Tester<C> {
public static int fieldWidth = 8;
public static TestParam[] defaultParams= TestParam.array(
10, 5000, 100, 5000, 1000, 5000, 10000, 500);
// Override this to modify pre-test initialization:
protected C initialize(int size) { return container; }
protected C container;
private String headline = "";
private List<Test<C>> tests;
private static String stringField() {
return "%" + fieldWidth + "s";
}
private static String numberField() {
return "%" + fieldWidth + "d";
}
private static int sizeWidth = 5;
private static String sizeField = "%" + sizeWidth + "s";
private TestParam[] paramList = defaultParams;
public Tester(C container, List<Test<C>> tests) {
this.container = container;
this.tests = tests;
if(container != null)
headline = container.getClass().getSimpleName();
}
public Tester(C container, List<Test<C>> tests,
TestParam[] paramList) {
this(container, tests);
this.paramList = paramList;
}
public void setHeadline(String newHeadline) {
headline = newHeadline;
}
// Generic methods for convenience :
public static <C> void run(C cntnr, List<Test<C>> tests){
new Tester<C>(cntnr, tests).timedTest();
}
public static <C> void run(C cntnr,
List<Test<C>> tests, TestParam[] paramList) {
new Tester<C>(cntnr, tests, paramList).timedTest();
}
private void displayHeader() {
// Calculate width and pad with '-':
int width = fieldWidth * tests.size() + sizeWidth;
int dashLength = width - headline.length() - 1;
StringBuilder head = new StringBuilder(width);
for(int i = 0; i < dashLength/2; i++)
head.append('-');
head.append(' ');
head.append(headline);
head.append(' ');
for(int i = 0; i < dashLength/2; i++)
head.append('-');
System.out.println(head);
// Print column headers:
System.out.format(sizeField, "size");
for(Test test : tests)
System.out.format(stringField(), test.name);
System.out.println();
}
// Run the tests for this container:
public void timedTest() {
displayHeader();
for(TestParam param : paramList) {
System.out.format(sizeField, param.size);
for(Test<C> test : tests) {
C kontainer = initialize(param.size);
long start = System.nanoTime();
// Call the overriden method:
int reps = test.test(kontainer, param);
long duration = System.nanoTime() - start;
long timePerRep = duration / reps; // Nanoseconds
System.out.format(numberField(), timePerRep);
}
System.out.println();
}
}
} ///:~
package Chapter17.Example8;
// A "data transfer object."
public class TestParam {
public final int size;
public final int loops;
public TestParam(int size, int loops) {
this.size = size;
this.loops = loops;
}
// Create an array of TestParam from a varargs sequence:
public static TestParam[] array(int... values) {
int size = values.length/2;
TestParam[] result = new TestParam[size];
int n = 0;
for(int i = 0; i < size; i++)
result[i] = new TestParam(values[n++], values[n++]);
return result;
}
// Convert a String array to a TestParam array:
public static TestParam[] array(String[] values) {
int[] vals = new int[values.length];
for(int i = 0; i < vals.length; i++)
vals[i] = Integer.decode(values[i]);
return array(vals);
}
} ///:~
package Chapter17.Example9;
// Demonstrates performance differences in Lists.
// {Args: 100 500} Small to keep build testing short
import java.util.*;
import net.mindview.util.*;
public class ListPerformance {
static Random rand = new Random();
static int reps = 1000;
static List<Test<List<Integer>>> tests =
new ArrayList<Test<List<Integer>>>();
static List<Test<LinkedList<Integer>>> qTests =
new ArrayList<Test<LinkedList<Integer>>>();
static {
tests.add(new Test<List<Integer>>("add") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops;
int listSize = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
for(int j = 0; j < listSize; j++)
list.add(j);
}
return loops * listSize;
}
});
tests.add(new Test<List<Integer>>("get") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops * reps;
int listSize = list.size();
for(int i = 0; i < loops; i++)
list.get(rand.nextInt(listSize));
return loops;
}
});
tests.add(new Test<List<Integer>>("set") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops * reps;
int listSize = list.size();
for(int i = 0; i < loops; i++)
list.set(rand.nextInt(listSize), 47);
return loops;
}
});
tests.add(new Test<List<Integer>>("iteradd") {
int test(List<Integer> list, TestParam tp) {
final int LOOPS = 1000000;
int half = list.size() / 2;
ListIterator<Integer> it = list.listIterator(half);
for(int i = 0; i < LOOPS; i++)
it.add(47);
return LOOPS;
}
});
tests.add(new Test<List<Integer>>("insert") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops;
for(int i = 0; i < loops; i++)
list.add(5, 47); // Minimize random-access cost
return loops;
}
});
tests.add(new Test<List<Integer>>("remove") {
int test(List<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
list.addAll(new CountingIntegerList(size));
while(list.size() > 5)
list.remove(5); // Minimize random-access cost
}
return loops * size;
}
});
// Tests for queue behavior:
qTests.add(new Test<LinkedList<Integer>>("addFirst") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
for(int j = 0; j < size; j++)
list.addFirst(47);
}
return loops * size;
}
});
qTests.add(new Test<LinkedList<Integer>>("addLast") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
for(int j = 0; j < size; j++)
list.addLast(47);
}
return loops * size;
}
});
qTests.add(
new Test<LinkedList<Integer>>("rmFirst") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
list.addAll(new CountingIntegerList(size));
while(list.size() > 0)
list.removeFirst();
}
return loops * size;
}
});
qTests.add(new Test<LinkedList<Integer>>("rmLast") {
int test(LinkedList<Integer> list, TestParam tp) {
int loops = tp.loops;
int size = tp.size;
for(int i = 0; i < loops; i++) {
list.clear();
list.addAll(new CountingIntegerList(size));
while(list.size() > 0)
list.removeLast();
}
return loops * size;
}
});
}
static class ListTester extends Tester<List<Integer>> {
public ListTester(List<Integer> container,
List<Test<List<Integer>>> tests) {
super(container, tests);
}
// Fill to the appropriate size before each test:
@Override protected List<Integer> initialize(int size){
container.clear();
container.addAll(new CountingIntegerList(size));
return container;
}
// Convenience method:
public static void run(List<Integer> list,
List<Test<List<Integer>>> tests) {
new ListTester(list, tests).timedTest();
}
}
public static void main(String[] args) {
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
// Can only do these two tests on an array:
Tester<List<Integer>> arrayTest =
new Tester<List<Integer>>(null, tests.subList(1, 3)){
// This will be called before each test. It
// produces a non-resizeable array-backed list:
@Override protected
List<Integer> initialize(int size) {
Integer[] ia = Generated.array(Integer.class,
new CountingGenerator.Integer(), size);
return Arrays.asList(ia);
}
};
arrayTest.setHeadline("Array as List");
arrayTest.timedTest();
Tester.defaultParams= TestParam.array(
10, 5000, 100, 5000, 1000, 1000, 10000, 200);
if(args.length > 0)
Tester.defaultParams = TestParam.array(args);
ListTester.run(new ArrayList<Integer>(), tests);
ListTester.run(new LinkedList<Integer>(), tests);
ListTester.run(new Vector<Integer>(), tests);
Tester.fieldWidth = 12;
Tester<LinkedList<Integer>> qTest =
new Tester<LinkedList<Integer>>(
new LinkedList<Integer>(), qTests);
qTest.setHeadline("Queue tests");
qTest.timedTest();
}
} /* Output: (Sample)
--- Array as List ---
size get set
10 130 183
100 130 164
1000 129 165
10000 129 165
--------------------- ArrayList ---------------------
size add get set iteradd insert remove
10 121 139 191 435 3952 446
100 72 141 191 247 3934 296
1000 98 141 194 839 2202 923
10000 122 144 190 6880 14042 7333
--------------------- LinkedList ---------------------
size add get set iteradd insert remove
10 182 164 198 658 366 262
100 106 202 230 457 108 201
1000 133 1289 1353 430 136 239
10000 172 13648 13187 435 255 239
----------------------- Vector -----------------------
size add get set iteradd insert remove
10 129 145 187 290 3635 253
100 72 144 190 263 3691 292
1000 99 145 193 846 2162 927
10000 108 145 186 6871 14730 7135
-------------------- Queue tests --------------------
size addFirst addLast rmFirst rmLast
10 199 163 251 253
100 98 92 180 179
1000 99 93 216 212
10000 111 109 262 384
*///:~
注：由于篇幅问题，代码中的Test、Tester、TestParam类见：Chapter17\Example9
- (1) 对于背后是数组支撑的List和ArrayList，无论列表大小如何，这些访问都快速一致。而对于LinkedList访问时间对于较大的列表明显增加，如果需要执行大量随机访问，链接链表不会是一种好的选择
- (2) 使用迭代器在列表中间插入新的元素。对于ArrayList，当列表变大时，其开销将变得高昂，但是对于LinkedList，相对来说比较低廉，并且不随列表尺寸而发生变化。这是因为ArrayList在插入时，必须创建空间并将它的所有引用向前移动，这会随ArrayList的尺寸增加而产生高昂的代价。LinkedList自需要链接新的元素，而不必修改列表中剩余的元素，一次你可以认为列表尺寸如果变化，其代价大致相同
- (3) LinkedList对List端点会进行特殊处理——这使得在将LinkedList用作Queue时，速度可以得到提高
- (4) 在LinkedList中的插入和移除代价相当低廉，并且不随列表尺寸发生变化，但是对于ArrayList，插入操作代价很高昂，并且不随列表尺寸的增加而增加
- (5) 从Queue测试中，可以看到LinkedList可以多么快速的从列表的端点插入和移除元素，这正是对Queue行为所做的优化
- (6) 将ArrayList作为默认首选，只有你需要使用额外的功能，或者当程序的性能因为经常从表中间进行插入和删除而变差的时候，才去选择LinkedList。如果使用的是固定数量的元素，那么既可以使用背后有支撑的List，也可以选择真正的数组
- (7) CopyOnWriteArrayList是List的一个特殊实现，专门用于并发编程
- 微基准测试的危险
- Math.random()的输出中的，其范围是[0,1)
- (1) HashSet的性能基本上总是比TreeSet的好，特别是在添加和查询元素时，而这两个操作是最重要的操作。TreeSet存在的唯一原因是它可以维持元素的排序状态
- (2) 对于插入操作，LinkedHashSet比HashSet的代价更高，这是由维护链表所带来额外开销造成的
- (1) 所有的Map实现的插入操作都会随着Map尺寸的变大明显变慢。但是查找的代价比插入小很多。
- (2) Hashtable的性能大体和HashMap相当。因为HashMap是用来替代Hashtable的，因此它们使用了相同的底层存储和查找机制
- (3) TreeMap
- i.TreeMap是一种创建有序列表的方式。树的行为是：总是保证有序，并且不必进行特殊的排序。一旦你填充了一个TreeMap，就可以调用keySet()方法来获取键的Set视图，然后调用toArray()来产生这些键构成的数组。
- ii.可以使用静态方法Arrays.binarySearch()在排序数组中快速查找对象
- iii.只有你要求Map始终保持有序时，才需要使用TreeMap
- (4) LingkedHashMap在插入时比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表。就是因为这个列表，使得其迭代速度更快
- (5) IdentityHashMap则具有完全不同的性能，因为它使用==而不是equals()来比较元素
- (6) HashMap的性能因子，可以通过手工调整HashMap来提高性能，从而满足我们特定应用的需求：
- i.容量：表中的桶位数
- ii.初始容量：表在创建时所拥有的桶位数
- iii.尺寸：表中当前存储的项数
- iv.负载因子：尺寸/容量。负载轻的表产生的可能性小，因此对于插入和查找都是最理想的
- (7) HashMap使用的默认负载因子时0.75，这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需空间，但是会增加查找代价
11.实用方法
- (1) List排序和查询所使用的方法与对象数组所使用的相应方法有相同的名字与语法，只是用Collections的static方法代替Arrays的方法而已
- (2) 如果使用Comparator进行排序，那么binarySearch()必须使用相同的Comparator
- (1) Collections.unmodifiableCollection()用于创建“不可修改”的容器（返回值是容器的只读版本），任何修改容器内的操作（例如add()、put()）都会引起UnsupportedOperationException异常
- (2) 在将容器设为只读之前，必须填入有意义的数据。装在数据后就不可修改了
- (1) 直接将新生成的容器传递给适当的同步方法
- Collections.synchronizedCollection(
new ArrayList()); - Collections.synchronizedList(
new ArrayList()); - Collections.synchronizedSet(
new HashSet()); - Collections.synchronizedSortedSet(
new TreeSet()); - Collections.synchronizedMap(
new HashMap<String,String>()) - Collections.synchronizedSortedMap(
new TreeMap<String,String>())
- Collections.synchronizedCollection(
- (2) 快速报错
- Java容器有一种保护机制，能够防止多个进程同时修改同一个容器的内容
- Java容器类类库采用快速报错机制，它会探查容器上的任何除了你进程所进行的操作以外的所有变化，一旦发现其他进程修改了容器，就会抛出ConcurrentModificationException异常
- ConcurrentHashMap、CopyOnWriteArrayList和CopyOnWriteArrayList都使用了可以避免ConcurrentModificationException异常
12.持有引用
- java.lang.ref类库包含了一组类，这些类为垃圾回收提供了更大的灵活性
- 有三个继承自抽象类Reference的类：SoftReference、WeakReference和PhantomReference。当垃圾回收器正在考察的对象只能通过某个Reference对象才“可获得”时，上述这些不同的派生类为垃圾回收器提供了不同级别的间接性指示
- 使用Renference对象，可以继续使用该对象，而在内存消耗殆尽的时候由允许释放该对象
- Soft reference：用以实现内存敏感的高速缓存
- Weak reference：是为实现“规范映射”而设计的，它不妨碍垃圾回收映射的“键”（或“值”）
- Phantom reference：用以调用回收前的清理工作，它比Java终止机制更灵活
- WeakHashMap：容器类中有一种特殊的Map，即WeakHashMap，它被用来保存WeakReference
13.Java 1.0/1.1 的容器
- Vector是唯一可以自我扩展的序列
- Enumeration只是接口而不是实现
- boolean hasMoreElement():如果此枚举包含更多元素，该方法就返回true
- Object nextElement():该方法返回此枚举中的下一个元素（如果该有下一个元素），否则抛出异常
- Collection.emumeration()：从Collection生成一个Enumeration
- Hashtable
- 在新程序中，应使用HashMap
- Stack
- Stack继承了Vector。它拥有Vector所有的特点和行为，在加上一些额外的Stack行为
- BitSet
- 如果想要高效率地存储大量“开/关”信息，BitSet是很好的选择。不过它的效率仅是对空间而言；如果需要高效的访问时间，BitSet比本地数组稍微慢一点
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
27
0- 0
已为社区贡献3条内容
所有评论(0)