本文主要是介绍第17章 容器深入研究，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第17章 容器深入研究
完整的容器分类法
容器可以分为四大类：List/SetMap/Queue，常用的具体实现是：ArrayList/HashSet/HashMap。
17.2 填充容器
public static void main(String[] args) {List<StringAddress> list = new ArrayList<>();// 只能替换已有的元素，不能新增元素Collections.fill(list, new StringAddress("b"));System.out.println(list);// []// 新增一个List，元素都指向同一个位置list = Collections.nCopies(3, new StringAddress("a"));System.out.println(list);// [com.container.StringAddress@27c170f0 a, com.container.StringAddress@27c170f0 a, com.container.StringAddress@27c170f0 a]Collections.fill(list, new StringAddress("b"));System.out.println(list);// [com.container.StringAddress@5451c3a8 b, com.container.StringAddress@5451c3a8 b, com.container.StringAddress@5451c3a8 b]}
一种Generator解决方案
class CollectionData<T> extends ArrayList<T>{// 填充进CollectionDatapublic CollectionData(Generator<T> generator,int num) {for (int i = 0; i < num; i++) {add(generator.next());}}// 注意：类泛型不能用于静态方法public static <E>CollectionData<E> list(Generator<E> generator,int num){return new CollectionData<>(generator,num);}
}class Proverb implements Generator<String>{// 日常的单调很容易使人精疲力尽String[] strings = "It’s easy to get burned out by the daily grind".split(" ");int next = 0;@Overridepublic String next() {return strings[next++];}
}public static void main(String[] args) {LinkedHashSet/*维持插入的顺序*/<String> set = new LinkedHashSet<>(new CollectionData<>(new Proverb(),5));System.out.println(set); // [It’s, easy, to, get, burned]set.addAll(CollectionData.list(new Proverb(),5));System.out.println(set); // [It’s, easy, to, get, burned]}
Map生成器
class MapData<K,V> extends LinkedHashMap<K,V>{// 一对值public MapData(Generator<Pair<K,V>> generator,int num){for (int i = 0; i < num; i++) {Pair<K, V> next = generator.next();put(next.k,next.v);}}// key和valuepublic MapData(Generator<K> kGenerator,Generator<V> vGenerator,int num){for (int i = 0; i < num; i++) {put(kGenerator.next(),vGenerator.next());}}// 系列key,单一valuepublic MapData(Iterable<K> iterable,V value){iterable.forEach(key -> put(key,value));}
}class Pair<K,V>{public final K k;public final V v;public Pair(K k, V v) {this.k = k;this.v = v;}
}class Letters implements Generator<Pair<Integer,String>>,Iterable<Integer>{private int number = 65;private char aChar = 'A';@Overridepublic Pair<Integer, String> next() {return new Pair<>(number++,String.valueOf(aChar++));}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {@Overridepublic boolean hasNext() {return number < 70;}@Overridepublic Integer next() {return number++;}};}
}public static void main(String[] args) {Map<Integer, String> map = new HashMap<>(new MapData<>(new Letters(),5));System.out.println(map);// {65=A, 66=B, 67=C, 68=D, 69=E}map.putAll(new MapData<>(new RandomGenerator.Int(),new RandomGenerator.Str(),5));System.out.println(map);// {65=A, 66=B, 67=C, 68=D, 69=E, -151806374=bc, 1239779180=EF, -735006902=cdE, -95006371=cdEF, 118002227=cdE}map.putAll(new MapData<>(new Letters(),"单一"));System.out.println(map);// {65=单一, 66=单一, 67=单一, 68=单一, 69=单一, -151806374=bc, 1239779180=EF, -735006902=cdE, -95006371=cdEF, 118002227=cdE}}
使用Abstract类
实现容器对应的Abstract容器，并仅产生只读的容器，可以使实现的方法最少。
在该实例中同时使用了享元模式，容器中共享元素。享元模式使对象的一部分具体化，减少了占用空间。
注意:Countries类中的关系
Countries内部类：MyMap
MyMap内部类：Entity EntrySet
EntrySet内部类：Iter
capitals()方法：产生包含国家和首都的Map容器
names()方法：产生包含国家的List容器
class Countries {public static final String[][] DATA = {{"中国", "北京"}, {"日本", "东京"},{"泰国", "曼谷"}, {"印度", "新德里"}};// 实现抽象Mapprivate static class MyMap extends AbstractMap<String, String> {// 单个实体类// 仅包含对静态数组的引用，而不包含具体的数据static class Entity implements Map.Entry<String, String> {// 通过index控制对DATA的数据访问int index;public Entity(int index) {this.index = index;}@Overridepublic String getKey() {// 实现共享DATA中的数据return DATA[index][0];}@Overridepublic String getValue() {return DATA[index][1];}@Overridepublic String setValue(String value) {throw new RuntimeException("不允许存入");}}// 实现Set类static class EntrySet extends AbstractSet<Map.Entry<String,String>> {// 控制Map的大小int size;public EntrySet(int size) {// 确定Set的大小if (size < 0)this.size = 0;else if (size > DATA.length)this.size = DATA.length;elsethis.size = size;}// 实现自己的迭代器private class Iter implements Iterator<Map.Entry<String, String>>{// 每个迭代器仅包含一个Entity实体类，其起到视窗的作用，迭代器通过对index的操作，使其指向下一个元素private Entity entity = new Entity(-1);@Overridepublic boolean hasNext() {return entity.index<size-1;}@Overridepublic Entry<String, String> next() {// 移动指针entity.index++;return entity;}}@Overridepublic Iterator<Map.Entry<String,String>> iterator() {return new Iter();}@Overridepublic int size() {return size;}}// 创建静态Setprivate static Set<Map.Entry<String, String>> entrySet = new EntrySet(DATA.length);@Overridepublic Set<Entry<String, String>> entrySet() {return entrySet;}}// 返回指定数量的Mapstatic Map<String,String> select(final int size){return new MyMap(){@Overridepublic Set<Entry<String, String>> entrySet() {return new EntrySet(size);}};}// 所有国家和首都static Map<String, String> map = new MyMap();public static Map<String, String> capitals(){return map;}public static Map<String, String> capitals(int size){return select(size);}// 所有国家名字static List<String> list = new ArrayList<>(map.keySet());public static List<String> names(){return list;}public static List<String> names(int size){return new ArrayList<>(select(size).keySet());}
}public static void main(String[] args) {System.out.println(capitals(3)); // {中国=北京, 日本=东京, 泰国=曼谷}System.out.println(new HashMap<>(capitals(1))); // {中国=北京}System.out.println(names(2)); // [中国, 日本]System.out.println(new ArrayList<>(names(1))); // [中国]System.out.println(capitals().get("中国")); // 北京}
不受尺寸限制的实现
class MyList extends AbstractList<Integer>{private int size;public MyList(int size) {this.size = size;}@Overridepublic Integer get(int index) {return index;}@Overridepublic int size() {return size;}
}class MyMap extends AbstractMap<Integer,String>{private int size;private static char[] chars ={'a','b','c','d'};public MyMap(int size) {this.size = size;}private class MyEntry implements Entry<Integer,String>{private int index;public MyEntry(int index) {this.index = index;}@Overridepublic Integer getKey() {return index;}@Overridepublic String getValue() {return Integer.toString(index)+chars[index%chars.length];}@Overridepublic String setValue(String value) {throw new UnsupportedOperationException();}}@Overridepublic Set<Entry<Integer, String>> entrySet() {Set<Entry<Integer,String>> set = new LinkedHashSet<>();for (int i = 0; i < size; i++) {set.add(new MyEntry(i));}return set;}
}public static void main(String[] args) {System.out.println(new MyList(20));// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]System.out.println(new MyMap(10));// {0=0a, 1=1b, 2=2c, 3=3d, 4=4a, 5=5b, 6=6c, 7=7d, 8=8a, 9=9b}}
17.3 Collection的功能方法
| 方法名 | 说明 |
|---|---|
| boolean add(E e) | 向集合添加元素e，若指定集合元素改变了则返回true |
| boolean addAll(Collection<? extends E> c) | 把集合C中的元素全部添加到集合中，若指定集合元素改变返回true |
| void clear() | 清空所有集合元素 |
| boolean contains(Object o) | 判断指定集合是否包含对象o |
| boolean containsAll(Collection<?> c) | 判断指定集合是否包含集合c的所有元素 |
| boolean isEmpty() | 判断指定集合的元素size是否为0 |
| boolean remove(Object o) | 删除集合中的元素对象o,若集合有多个o元素，则只会删除第一个元素 |
| boolean removeAll(Collection<?> c） | 删除指定集合包含集合c的元素 |
| boolean retainAll(Collection<?> c) | 从指定集合中保留包含集合c的元素,其他元素则删除 |
| int size() | 集合的元素个数 |
| T[] toArray(T[] a) | 将集合转换为T类型的数组 |
public static void main(String[] args) {Collection<String> c1 = new ArrayList<>();Collection<String> c2 = new ArrayList<>(Arrays.asList("e","f","g"));// 添加boolean flag = c1.add("a");System.out.println(flag); // trueSystem.out.println(c1); // [a]flag = c1.addAll(c2);System.out.println(c1); // [a, e, f, g]flag = c1.remove("a"); // trueSystem.out.println(flag); // [e, f, g]System.out.println(c1);flag = c1.removeAll(c2);System.out.println(c1); // []// 包含flag = c1.contains("a");System.out.println(flag); // falseflag = c1.containsAll(c2);System.out.println(flag); // false// 是否为空flag = c1.isEmpty();System.out.println(flag); // true// 长度c1.add("b");int size = c1.size();System.out.println(size); // 1// 转数组String[] strings1 = new String[5];System.out.println(strings1); // [Ljava.lang.String;@27c170f0String[] strings2 = c1.toArray(strings1);System.out.println(strings2); // [Ljava.lang.String;@27c170f0 指向同一个地址System.out.println(Arrays.toString(strings1)); // [b, null, null, null, null]// 清除元素c1.clear();System.out.println(c1); // []}
17.4 可选操作
注意： 这里可能有些绕。
在Collection接口中添加和移除的方法都是可选操作；
什么是可选操作：实现类并没有提供对应方法的功能定义，就Collection接口而言，就是在实现中抛出UnsupportOperationException异常；而该定义，只是在实现层次的操作，并没有提供语法层次的操作。
为什么会出现可选操作？防止接口爆炸，如容器可能分为只读的，可修改的，可添加的，可删除的等，但是大家除add()和remove()外有很多共同点，现在就需要一个抽象实现类，来实现这些方法，但是在抽象实现类中的add()方法并不能有具体所指，所以就通过抛异常的方式来表现(为什么不使用抽象方法呢？多个子类可能add()方法不能使用，使用抽象方法，就不能代码复用)。
大部分可选操作都发生在抽象实现类中，如AbstractList
public void add(int index, E element) {throw new UnsupportedOperationException();}
最常见的未获支持的操作，都是背后的容器尺寸固定问题。
public static void main(String[] args) {List<String> list = Arrays.asList("a","b");list.set(1,"c");list.add("d"); // Exception in thread "main" java.lang.UnsupportedOperationException}
asList()方法返回的List是Arrays的内部类，该类没有重写add()方法，只能修改，不能添加。
public static void main(String[] args) {List<String> list = Arrays.asList("a","b");list = Collections.unmodifiableList(list);list.set(1,"c"); // Exception in thread "main" java.lang.UnsupportedOperationException}
// 只读的List
17.5 List的功能方法
// List的基本方法public static void basicTest(List<String> list){// 添加元素list.add("a");list.add(1,"b");list.addAll(Arrays.asList("c","d"));list.addAll(4,Arrays.asList("e","f"));// 是否包含boolean contains = list.contains(1);contains = list.containsAll(Arrays.asList("c","d"));// 获得元素String s = list.get(0);int index = list.indexOf("a");// 是否为空boolean isEmpty =list.isEmpty();// 获得迭代器Iterator<String> iterator = list.iterator();// listIterator针对List的迭代器，有更多的功能ListIterator<String> listIterator = list.listIterator();// 从指定索引处迭代集合listIterator = list.listIterator(3);// 前面是否有元素boolean flag = listIterator.hasPrevious();// 下一个索引listIterator.nextIndex();// 前一个元素listIterator.previous();// 前一个索引listIterator.previousIndex();// 删除list.remove(1);list.remove("c");list.removeAll(Arrays.asList("e","f"));// 修改list.set(0,"z");// 移除不在目标集合中的元素list.retainAll(Arrays.asList("c","d"));int size = list.size();list.clear();}// LinkedList的特殊用法public static void testLinkedList(LinkedList<String> linkedList){// 在头部操作元素linkedList.addFirst("a");linkedList.getFirst();linkedList.removeFirst();// 在尾部操作元素linkedList.addLast("b");linkedList.removeLast();}
17.6 Set和存储顺序
| 类型 | 描述 |
|---|---|
| Set(interface) | 存入Set的每个元素都必须是唯一的，因为set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set和Collection有完全一样的接口。Set接口不保证维护元素的次序。 |
| HashSet * | 为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()。 |
| TreeSet | 保持次序的Set，底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口。 |
| LinkedHashSet | 具有HashSet的查询速度,且内部使用链表维护元素顺序（插入顺序）。于是在使用迭代器遍历Set时，结果会按元素插入顺序显示，元素也必须实现hashCode()方法。 |
必须为Set创建equals()方法，只有HashSet和LinkHashSet需要hashCode()方法。但是良好的编程风格应该是重写equals()时跟着重写hashCode()。
class SetType{int i;public SetType(int i) {this.i = i;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;SetType setType = (SetType) o;return i == setType.i;}@Overridepublic String toString() {return Integer.toString(i);}
}class HashSetType extends SetType{public HashSetType(int i) {super(i);}@Overridepublic int hashCode() {return i;}
}class TreeSetType extends SetType implements Comparable<TreeSetType>{public TreeSetType(int i) {super(i);}@Overridepublic int compareTo(TreeSetType o) {// 为什么不使用加减运算？// 因为当正数-负数时可能会超过int的范围return i > o.i?-1:(i == o.i?0:1);}
}// 工具类
class TypesForSet{// 填充setprivate static <T> Set<T> fill(Set<T> set,Class<T> c){try {for (int i = 0; i < 10; i++) {set.add(c.getConstructor(int.class).newInstance(i));}}catch(Exception e){e.printStackTrace();}return set;}public static <T> void test(Set<T> set,Class<T> c){fill(set,c);fill(set,c);System.out.println(set);}public static void main(String[] args) {// 按照hash函数计算后的排序test(new HashSet<>(),HashSetType.class); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]// 按照比较后的排序test(new TreeSet<>(),TreeSetType.class); // [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]// 没有重写hashcode()，可以看到Set认为他们不相等test(new HashSet<>(),SetType.class); // [0, 8, 9, 3, 8, 2, 6, 9, 3, 6, 4, 5, 4, 5, 7, 2, 7, 1, 0, 1]// 没有实现Comparable接口而存入TreeSet会报错test(new TreeSet<>(),SetType.class); // ClassCastException: com.container.SetType cannot be cast to java.lang.Comparable}
}
SortedSet
SortedSet中的元素保证处于排序状态，它是按对象的比较函数排序。
public static void main(String[] args) {SortedSet<String> sortedSet = new TreeSet<>();// 返回SortedSet的比较函数Comparator<? super String> comparator = sortedSet.comparator();Collections.addAll(sortedSet,"one two three four five six".split(" "));System.out.println(sortedSet); // [five, four, one, six, three, two]String first = sortedSet.first();String last = sortedSet.last();System.out.println("first:"+first+" "+"last:"+last); // first:five last:twoIterator<String> iterator = sortedSet.iterator();// 返回子SetSortedSet<String> subSet = sortedSet.subSet("four", "six");// 返回到。。为止的SetSortedSet<String> headSet = sortedSet.headSet("one");// 返回从。。开始的SetSortedSet<String> tailSet = sortedSet.tailSet("one");}
17.7 队列
除了并发应用Queue目前在JDK5中仅有两个实现：LinkedList和PriorityQueue，他们的差异在于排序行为而不是性能。
public class Test1 {public static void main(String[] args) {test(new LinkedList<>()); // one two three four test(new PriorityQueue<>()); // four one three two // 按优先级排序test(new ArrayBlockingQueue<>(5)); // one two three four test(new ConcurrentLinkedQueue<>()); // one two three four}public static void test(Queue<String> queue){for(String s:"one two three four".split(" ")){queue.offer(s);}while (queue.peek() != null){System.out.print(queue.remove()+" ");}System.out.println();}
}
优先级队列
// 待做列表
class ToDoList extends PriorityQueue<ToDoList.ToDoItem>{static class ToDoItem implements Comparable<ToDoItem>{// 做的事private String str;// 主优先级private char priority;// 次优先级private int secondPriority;public ToDoItem(String str, char priority, int secondPriority) {this.str = str;this.priority = priority;this.secondPriority = secondPriority;}@Overridepublic int compareTo(ToDoItem o) {if (priority > o.priority){return 1;}else if (priority == o.priority){if (secondPriority > o.secondPriority){return 1;}else if (secondPriority == o.secondPriority){return 0;}}return -1;}@Overridepublic String toString() {return priority +" "+secondPriority+" "+str;}}// 添加待做事项public boolean add(String str,char priority,int secondPriority) {return super.add(new ToDoItem(str,priority,secondPriority));}public static void main(String[] args) {ToDoList toDoList = new ToDoList();toDoList.add("学英语",'A',3);toDoList.add("敲代码",'A',1);toDoList.add("玩游戏",'B',1);toDoList.add("睡觉",'B',2);while (!toDoList.isEmpty()){System.out.println(toDoList.remove());}}
}
双向队列
双向队列就像是一个队列，但是可以在两端添加或移除元素，LinkedList支持双向队列的方法，在JDK6中引入了Deque接口来表示双向队列，但是该接口并不常用。
17.8 理解Map
映射表的基本思想是维护键-值关联，其有多种实现，实现的行为特性各不相同，表现在效率/键值对的保存/呈现次序/对象的保存周期/在多线程中的工作/如何判定键的等价。
public class AssociativeArray<K,V> {public static void main(String[] args) {AssociativeArray<String, String> map = new AssociativeArray<String, String>(3);map.put("a", "1");map.put("b", "2");System.out.println(map.get("b"));System.out.println(map);}private Object[][] pairs;private int index;public AssociativeArray(int length) {pairs = new Object[length][2];}public void put(K key,V value) {if (index > pairs.length) {throw new RuntimeException("超长");}pairs[index++] = new Object[]{key,value};}public V get(K key) {for(int i = 0;i<pairs.length;i++){if (key.equals(pairs[i][0])) {return (V)pairs[i][1];}}return null;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("[");for(int i = 0;i<pairs.length;i++){sb.append(pairs[i][0]).append(":").append(pairs[i][1]);if (i<pairs.length-1) {sb.append(",");}}sb.append("]");return sb.toString();}
}
性能
当在get()中使用线性搜索时，执行速度会相当地慢，而HashMap使用散列码，来取代对键的缓慢搜索。
public class Test1 {public static void main(String[] args) {test(add(new HashMap<>()));System.out.println("---");test(add(new ConcurrentHashMap<>()));}public static Map<Integer, String> add(Map<Integer, String> map){map.put(0,"a");map.put(1,"b");return map;}public static void test(Map<Integer, String> map){System.out.println(map.getClass().getSimpleName()); // HashMap// 添加集合map.putAll(Collections.singletonMap(2,"c"));// 获得keySystem.out.println(map.keySet()); // [0, 1, 2]// 获得values// 注意：values()返回一个Collection，其中的值有任何变化，也会反映到map中System.out.println(map.values()); // [a, b, c]// 是否包含keySystem.out.println(map.containsKey(1)); // trueSystem.out.println(map.get(1)); // b// 是否包含valueSystem.out.println(map.containsValue("c")); // true// key迭代器Iterator<Integer> iterator = map.keySet().iterator();System.out.println(map.remove(2)); // cmap.clear();System.out.println(map); // {}}
}
SortedMap
SortedMap可以确保键处于排序状态，目前仅有一个实现：TreeMap，其也是Map中可以获得子Map的实现。
public static void main(String[] args) {SortedMap<String,String> sortedMap = new TreeMap<>();sortedMap.put("one","a");sortedMap.put("two","b");sortedMap.put("four","d");// 排序函数Comparator<? super String> comparator = sortedMap.comparator();// 首尾KeyString firstKey = sortedMap.firstKey();String lastKey = sortedMap.lastKey();// 获得子MapsortedMap.subMap("four","one");sortedMap.headMap("two");sortedMap.tailMap("four");}
LinkedHashMap
为了提高速度LinkedHashMap会散列化所有元素，但是在遍历键值对时，却以插入顺序返回；另外，在构造时可以设定基于最少使用算法。
public class Test1 {public static void main(String[] args) {Map<Integer, String> map = add(new LinkedHashMap<>());System.out.println(map); // {3=c, 1=a, 2=b}map = add(new LinkedHashMap<>(16,0.75f,true));System.out.println(map); // {3=c, 1=a, 2=b}map.get(3);// 在使用后，就会被排到后边System.out.println(map); // {1=a, 2=b, 3=c}}public static Map<Integer, String> add(Map<Integer, String> map){map.put(3,"c");map.put(1,"a");map.put(2,"b");return map;}}
17.9 散列和散列码
// 土拨鼠
class Groundhog{private int number;public Groundhog(int number) {this.number = number;}@Overridepublic String toString() {return "土拨鼠"+number+"号";}
}// 天气预报
class Prediction{private Random random = new Random();private boolean flag = random.nextDouble()>0.5;@Overridepublic String toString() {return flag?"温暖的春天":"寒冷的冬天";}
}public static void main(String[] args) {Map<Groundhog,Prediction> map = new HashMap<>();for (int i = 0; i < 5; i++) {map.put(new Groundhog(i),new Prediction());}System.out.println(map);// {土拨鼠0号=温暖的春天, 土拨鼠1号=温暖的春天, 土拨鼠2号=寒冷的冬天, 土拨鼠3号=寒冷的冬天, 土拨鼠4号=寒冷的冬天}System.out.println(map.containsKey(new Groundhog(2))); // false}
注意： 可以看到通过new Groundhog(2)并不能找到对应的value，因为这里使用的是Object的hashChode()生成散列码，默认使用对象的地址计算，这样，当然不会找到。
同时，我们还需要重写equals()方法。
正确的 equals()方法必须满足下列5 个条件：
自反性：对任意 x，x.equals\(x\)一定返回true。
对称性：对任意x 和y，如果y.equals\(x\)返回true，则x.equals\(y\)也返回true。
传递性：对任意x，y，z，如果有x.equals\(y\)返回ture，y.equals\(z\)返回true，则x.equals\(z\)一定返回true。
一致性：对任意 x 和y，如果对象中用于等价比较的信息没有改变，那么无论调用x.equals\(y\)多少次，返回的结果应该保持一致，要么一直是true，要么一直是false。
对任何不是 null 的x，x.equals\(null\)一定返回false。
// 重写equals和hashCode
class Groundhog{private int number;public Groundhog(int number) {this.number = number;}@Overridepublic boolean equals(Object o) {return o instanceof/*隐含检查了o是否为null*/ Groundhog && ((Groundhog) o).number == number;}@Overridepublic int hashCode() {return number;}@Overridepublic String toString() {return "土拨鼠"+number+"号";}
}
17.9.1 理解hashCode()
使用散列的目的：使用一个对象查找另一个对象。
// 使用一对ArrayList实现一个Map
class SlowMap<K,V> extends AbstractMap<K,V>{private List<K> keys = new ArrayList<>();private List<V> values = new ArrayList<>();@Overridepublic V get(Object key) {if (keys.contains(key)) {return values.get(keys.indexOf(key));}else {return null;}}// 返回旧值或null@Overridepublic V put(K key, V value) {V oldValue = get(key);if (!keys.contains(key)){keys.add(key);values.add(value);}else {values.set(keys.indexOf(key),value);}return oldValue;}// 完整的Map实现需要实现entrySet方法，该方法返回值是一个Entry的Set，需要实现Entry接口@Overridepublic Set<Entry<K, V>> entrySet() {Set<Map.Entry<K,V>> set = new HashSet<>();Iterator<K> kIterator = keys.iterator();Iterator<V> vIterator = values.iterator();while (kIterator.hasNext()){set.add(new MapEntry(kIterator.next(),vIterator.next()));}return set;}private class MapEntry implements Map.Entry<K,V>{private K k;private V v;public MapEntry(K k, V v) {this.k = k;this.v = v;}@Overridepublic K getKey() {return k;}@Overridepublic V getValue() {return v;}@Overridepublic V setValue(V value) {v = value;return v;}@Overridepublic boolean equals(Object o) {// 必须检查键和值，o可能不是该类的实例if (!(o instanceof Map.Entry)) {return false;}Entry entry = (Entry) o;return (k == null ? entry.getKey() == null:k.equals(entry.getKey()))&&(v == null ? entry.getValue() == null : v.equals(entry.getValue()));}// 这里提供了一个hashCode简单的实现// 虽然可以使用，但是并不恰当@Overridepublic int hashCode() {return (k == null?0:k.hashCode()) ^ (v == null?0:v.hashCode());}}
}
17.9.2 为速度而散列
SlowMap使用简单的线性查询，而线性查询是最慢的。
散列码： 数组并不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个数字就是散列码。
冲突： 为解决数组容量被固定的问题，不同的键可以产生相同的下标，这可能会产生冲突。
// 简单的散列Map
class SimpleHashMap<K, V> extends AbstractMap<K, V> {// 确定数组大小private final int SIZE = 997;// 底层储存结构，数组+链表private LinkedList<MapEntry>[] buckets/*水桶*/ = new LinkedList[SIZE];@Overridepublic V get(Object key) {// 获得数组下标int index = key.hashCode() % SIZE;// 该位置是否有链表if (buckets[index] == null) {return null;}// 遍历链表for (MapEntry entry : buckets[index]) {if (entry.getKey().equals(key)) {return entry.getValue();}}return null;}// 返回旧值或null@Overridepublic V put(K key, V value) {// 获得数组下标int index = key.hashCode() % SIZE;// 保证该位置有链表if (buckets[index] == null) {buckets[index] = new LinkedList<>();}V oldValue = null;// 修改或添加的标识boolean flag = false;for (MapEntry entry : buckets[index]) {// 如果含有该值if (entry.getKey().equals(key)) {oldValue = entry.getValue();// 修改值并标识为修改entry.setValue(value);flag = true;break;}}// 如果非修改，就添加元素if (!flag){buckets[index].add(new MapEntry(key,value));}// 返回旧值或nullreturn oldValue;}@Overridepublic Set<Entry<K, V>> entrySet() {Set<Map.Entry<K, V>> set = new HashSet<>();// 双重遍历，将实体添加到Setfor (LinkedList<MapEntry> bucket : buckets) {// 如果没有链表，跳过if (bucket == null) {continue;}for (MapEntry entry : bucket) {set.add(entry);}}return set;}private class MapEntry implements Map.Entry<K, V> {private K k;private V v;public MapEntry(K k, V v) {this.k = k;this.v = v;}@Overridepublic K getKey() {return k;}@Overridepublic V getValue() {return v;}@Overridepublic V setValue(V value) {v = value;return v;}@Overridepublic boolean equals(Object o) {if (!(o instanceof Map.Entry)) {return false;}Entry entry = (Entry) o;return (k == null ? entry.getKey() == null : k.equals(entry.getKey())) &&(v == null ? entry.getValue() == null : v.equals(entry.getValue()));}@Overridepublic int hashCode() {return (k == null ? 0 : k.hashCode()) ^ (v == null ? 0 : v.hashCode());}}
}public static void main(String[] args) {Map<String,String> map = new SimpleHashMap<>();// map.put(null,"a"); // 这里有一个bug，既即不能以null作键map.put("one","a");map.put("two","b");System.out.println(map); // {one=a, two=b}System.out.println(map.get("two")); // b}
散列表中的槽位通常称为桶位，因此将底层结构命名为buckets。桶的数量通常使用质数，但近来实验表明，2的整数次方才是最优的选择，对处理器而言除法与求余数是最慢的操作，近来的选择，可用掩码代替除法。
17.9.3 覆盖hashCode()
注意事项：
- 无法控制bucket数组的具体下标值；
- put和get时得到的hashCode必须相同；
- 不能依赖于易变的数据，当数据产生变化时，会产生不同的hash值；
- 不能依赖于唯一的值，否则使用数组+链表就没有什么意义了。
- hashCode应该产生分布均匀的散列码，否则某些区域负载过重。
计算指导
-
给int变量result赋予一个常量；
-
为对象内有意义的域f计算出散列码c;
| 域类型 | 计算 |
| — | — |
| boolean | c = (f?0:1) |
| byte/char/shot/int | c=(int)f |
| long | c=(int)(f^(f>>>32)) |
| float | c =Float.floatToIntBits(f) |
| double | long l = Double.doubleToLongBits(f);c=(int)(f^(f>>>32)) |
| Object | c =f.hashCode() |
| 数组 | 对每个元素用上述方法 |
合并计算：result = 37 \*result +c;
返回result;
//简单示例
class CountedString {// 创建的string对象都存储在这里private static List<String> list = new ArrayList<>();private String s;// 创建的第几个该对象private int id;public CountedString(String s) {this.s = s;list.add(s);for (String s1 : list) {if (s1.equals(s)) {id++;}}}@Overridepublic boolean equals(Object o) {return o instanceof CountedString && ((CountedString) o).s.equals(s) && id == ((CountedString) o).id;}@Overridepublic int hashCode() {int result = 17;result = 37 * result + s.hashCode();result = 37 * result + id;return result;}@Overridepublic String toString() {return "String:" + s + " " + "id:" + " " + id + "hashCode:" + hashCode();}
}public static void main(String[] args) {Map<CountedString, Integer> map = new HashMap<>();CountedString[] countedStrings = new CountedString[3];for (int i = 0; i < 3; i++) {countedStrings[i] = new CountedString(new String("hi"));map.put(countedStrings[i],i);}System.out.println(map);// {String:hi id: 2hashCode:146448=1, String:hi id: 3hashCode:146449=2, String:hi id: 1hashCode:146447=0}for (int i = 0; i < countedStrings.length; i++) {System.out.println(countedStrings[i]);System.out.println(map.get(countedStrings[i]));/*String:hi id: 1hashCode:1464470String:hi id: 2hashCode:1464481String:hi id: 3hashCode:1464492*/}}
/*
可以看到，正因为hashcode不同，在map中所有元素都被存储了
这里存在的问题时，不可能产生相同的对象
*/
// 另外一个示例，重点在比较
class Individual implements Comparable<Individual>{private static int counter;private final int id = counter++;private String name;public Individual(String name) {this.name = name;}@Overridepublic String toString() {return "宠物："+name+id+"号 ";}@Overridepublic boolean equals(Object o) {return o instanceof Individual && id == ((Individual) o).id;}@Overridepublic int hashCode() {int result = 17;if (name != null) {result = result *37+name.hashCode();}result = result*37+id;return result;}// 有一个排序序列，如果name不同则按name排序，name相同就按id排序@Overridepublic int compareTo(Individual o) {if (name != null && o.name != null) {int compare = name.compareTo(o.name);if ( compare != 0) {return compare;}}return id > o.id ? 1 :(id == o.id ? 0:-1);}
}public static void main(String[] args) {Set<Individual> set = new TreeSet<>();set.add(new Individual("cat"));set.add(new Individual("dog"));set.add(new Individual("cat"));System.out.println(set);// [宠物：cat0号 , 宠物：cat2号 , 宠物：dog1号 ]}
17.10 选择接口的不同实现
容器实际上只有四种：Map/List/Set/Queue。
容器之间的区别是背后用什么数据结构实现的。
我们可以根据实际使用的需求选择不同的实现。
17.10.1 性能测试框架
// 测试基类
public abstract class Test<C> {// 测试名字public String name;public Test(String name) {this.name = name;}/*** 每个被测的容器应当覆盖该方法* @param container 测试的容器* @param tp 测试参数* @return 测试的数量*/public abstract int test(C container,TestParam tp);
}// 测试参数
public class TestParam {// 容器大小public final int size;// 迭代次数public final int loops;public TestParam(int size, int loops) {this.size = size;this.loops = loops;}// 产生一个测试参数数组对象public static TestParam[] array(int...values){int size = values.length/2;TestParam[] result = new TestParam[size];int n = 0;for (int i = 0; i < result.length; i++) {// 指定容器的长度和迭代的次数// values偶数位是长度，奇数位是迭代次数result[i] = new TestParam(values[n++],values[n++]);}return result;}public static TestParam[] array(String[] values){int[] ints = new int[values.length];for (int i = 0; i < ints.length; i++) {// 将字符串解码为整数，接收八进制和十六进制ints[i] = Integer.decode(values[i]);}return array(ints);}
}// 测试者
// 核心方法
public class Tester<C> {// 字段宽度public static int fieldWidth = 8;// 被测容器长度宽度private static int sizeWidth = 5;// 长度的格式化private static String sizeField = "%" + sizeWidth + "s";// 测试方法的格式化private static String stringField() {return "%" + fieldWidth + "s";}// 测试数据的格式化private static String numberField() {return "%" + fieldWidth + "d";}// 默认测试参数对象集public static TestParam[] defaultParams = TestParam.array(10, 5000, 100, 5000, 1000, 5000, 10000, 500);// 测试参数集private TestParam[] paramList = defaultParams;// 测试集合private List<Test<C>> tests;// 测试容器protected C container;// 标题private String headline = "";// 初始化函数protected C initialize(int size) {return container;}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 headline) {this.headline = headline;}// 打印头部信息protected void displayHeader() {// 标题总宽度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(" ").append(headline).append(" ");for (int i = 0; i < dashLength / 2; i++) {head.append("-");}// 打印标题System.out.println(head);// 打印类目System.out.format(sizeField, "size");for (Test<C> test : tests) {System.out.format(stringField(), test.name);}System.out.println();}// 核心测试方法protected void timedTest() {// 打印头部displayHeader();// 遍历测试参数集for (TestParam testParam : paramList) {System.out.format(sizeField, testParam.size);// 遍历测试集for (Test<C> test : tests) {// 初始化C c = initialize(testParam.size);// 以纳秒为单位long start = System.nanoTime();int reps = test.test(c, testParam);long duration = System.nanoTime() - start;long timePerRep = duration / reps;System.out.format(numberField(), timePerRep);}// 注意换行位置System.out.println();}}// 对外提供的方法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[] testParams) {new Tester<C>(cntnr, tests, testParams).timedTest();}
}
17.10.2 对List的选择
public class ListPerformance {static Random random = new Random();static int reps = 1000;// ArrayList测试集static List<Test<List<Integer>>> tests = new ArrayList<>();// LinkedList测试集static LinkedList<Test<LinkedList<Integer>>> qtests = new LinkedList<>();static {tests.add(new Test<List<Integer>>("add") {@Overridepublic int test(List<Integer> list, TestParam tp) {for (int i = 0; i < tp.loops; i++) {list.clear();for (int j = 0; j < tp.size; j++) {list.add(j);}}return tp.loops * tp.size;}});tests.add(new Test<List<Integer>>("get") {@Overridepublic int test(List<Integer> list, TestParam tp) {for (int i = 0; i < tp.loops; i++) {list.get(random.nextInt(list.size()));}return tp.loops;}});tests.add(new Test<List<Integer>>("set") {@Overridepublic int test(List<Integer> list, TestParam tp) {for (int i = 0; i < tp.loops; i++) {list.set(random.nextInt(list.size()),i);}return tp.loops;}});tests.add(new Test<List<Integer>>("remove") {@Overridepublic int test(List<Integer> list, TestParam tp) {for (int i = 0; i < list.size(); i++) {if (list.size() >2){list.remove(1);}}return list.size();}});tests.add(new Test<List<Integer>>("insert") {@Overridepublic int test(List<Integer> list, TestParam tp) {for (int i = 0; i < tp.loops; i++) {list.add(8,i);}return tp.loops;}});qtests.add(new Test<LinkedList<Integer>>("addFirst") {@Overridepublic int test(LinkedList<Integer> list, TestParam tp) {for (int i = 0; i < tp.loops; i++) {list.clear();for (int j = 0; j < tp.size; j++) {list.addFirst(i);}}return tp.loops*tp.size;}});qtests.add(new Test<LinkedList<Integer>>("addLast") {@Overridepublic int test(LinkedList<Integer> list, TestParam tp) {for (int i = 0; i < tp.loops; i++) {list.clear();for (int j = 0; j < tp.size; j++) {list.addLast(i);}}return tp.loops*tp.size;}});}
}// List测试
public class ListTester extends Tester<List<Integer>> {public ListTester(List<Integer> container, List<Test<List<Integer>>> tests) {super(container, tests);}// 重写初始化方法// 本方法也很重要，timedTest每次在执行Test.test时都必须初始化，否则，前次执行的结果会影响后执行的结果@Overrideprotected List<Integer> initialize(int size) {container.clear();for (int i = 0; i < size; i++) {container.add(i);}return container;}public static void run(List<Integer> list,List<Test<List<Integer>>> tests){new ListTester(list,tests).timedTest();}public static void main(String[] args) {ListTester.run(new ArrayList<>(),ListPerformance.tests);/*----------------- ArrayList -----------------size add get set remove insert10 63 340 224 3880 392100 16 138 83 516 3411000 10 53 78 467 29310000 7 78 217 917 1034100000 11 392 410 8623 10762*/ListTester.run(new LinkedList<>(),ListPerformance.tests);/*----------------- LinkedList -----------------size add get set remove insert10 81 133 124 2060 199100 37 88 120 266 581000 15 387 405 272 6210000 9 6323 6115 53 39100000 25 105806 75586 29 162*/ListTester.run(new LinkedList<>(),ListPerformance.qtests);/*----- LinkedList -----sizeaddFirst addLast10 59 41100 15 201000 16 1810000 31 16100000 10 10*/}
}
/*
从测试数据看到，随着容器的长度变大，LinkedList查询的性能明显下降，而ArrayList则是插入的性能明显下降；同时也可以看到，其实在万级以内，差距并不明显
*/
17.10.3 微基准测试的危险
微基准测试理解：对一些小的东西，小数据量的测试。
做这类测试时，应当关注点要单一，但是不要从结果中获得太多的结论，这类结果很容易受其他因素的影响。
17.10.4 对Set的选择
public class SetPerformance {static List<Test<Set<Integer>>> list = new ArrayList<>();static {list.add(new Test<Set<Integer>>("add") {@Overridepublic int test(Set<Integer> set, TestParam tp) {for (int i = 0; i < tp.loops; i++) {set.clear();for (int j = 0; j < tp.size; j++) {set.add(j);}}return tp.loops*tp.size;}});list.add(new Test<Set<Integer>>("contains") {@Overridepublic int test(Set<Integer> set, TestParam tp) {for (int i = 0; i < tp.loops; i++) {set.clear();for (int j = 0; j < tp.size; j++) {set.contains(j);}}return tp.loops*tp.size;}});}public static void main(String[] args) {Tester.run(new HashSet<>(),SetPerformance.list);Tester.run(new TreeSet<>(),SetPerformance.list);Tester.run(new LinkedHashSet<>(),SetPerformance.list);}/*------ HashSet ------size addcontains10 92 58100 36 231000 20 710000 18 2100000 22 2------ TreeSet ------size addcontains10 194 57100 53 21000 51 310000 89 4100000 145 3--- LinkedHashSet ---size addcontains10 140 99100 34 91000 14 1310000 31 8100000 15 7*/
}
本地测试的结果和书上的差距比较大；总体而言，一般选择HashSet,需要排序，则选择TreeSet，如果需要按插入排序，则选择LinkedHashSet。
17.10.5 对Map的选择
public class MapPerformance {static List<Test<Map<Integer,Integer>>> tests = new ArrayList<>();static {tests.add(new Test<Map<Integer, Integer>>("put") {@Overridepublic int test(Map<Integer, Integer> map, TestParam tp) {for (int i = 0; i < tp.loops; i++) {for (int j = 0; j < tp.size; j++) {map.put(j,i);}}return tp.loops * tp.size;}});tests.add(new Test<Map<Integer, Integer>>("get") {@Overridepublic int test(Map<Integer, Integer> map, TestParam tp) {for (int i = 0; i < tp.loops; i++) {for (int j = 0; j < tp.size; j++) {map.put(j,i);}}return tp.loops * tp.size;}});}
}public static void main(String[] args) {Tester.run(new HashMap<>(),MapPerformance.tests);/*------ HashMap ------size put get10 119 63100 24 271000 21 1510000 17 12100000 15 19*/Tester.run(new TreeMap<>(),MapPerformance.tests);/*------ TreeMap ------size put get10 222 192100 38 331000 86 9610000 86 79100000 123 112*/Tester.run(new LinkedHashMap<>(),MapPerformance.tests);/*--- LinkedHashMap ---size put get10 75 99100 29 121000 13 1210000 14 13100000 13 12*/}
相关术语
容量：容器中存放元素的最大数；
尺寸：容器中当前存储的项数；
负载因子：尺寸/容量。
17.11 实用方法
Collections工具类中的实用方法
| 方法 | 说明 |
|---|---|
| checkedCollection(Collection,Class) | 检查类型是否符合 |
| max/min(Collection) | 返回最大/最小元素 |
| max/min(Collection,Comparator) | 指定比较器，返回 |
| indexOfSubLsit(List source,List target) | target在source第一次出现的位置 |
| lastIndexOfSubList(List source,List target) | 最后一次位置 |
| replaceAll(List,T oldVal,T newVal) | 新的替换所有旧的元素 |
| reverse(List) | 反转元素次序 |
| reverseOrder() | 返回逆转集合排序的比较器 |
| rotate(List,int distance) | 元素向后移动distance个位置，末尾循环到前面 |
| shuffle(List) | 打乱排序 |
| sort(Lsit) | 排序 |
| copy(Lsit dest,List src) | src中的元素复制到dest |
| swap(List,int i,int j) | 交换指定位置的元素 |
| fill(List,T x) | 用x替换所有 |
| nCopies(int n,T x) | 返回n大小的List，不可改变，元素指向x |
| disjoint(Collection,Collection) | 没有相同的元素，返回true |
| frequency(Collection,Object x) | 包含x的个数 |
| emptyLsit() | 返回不可变空List |
| singleton(T x) | 返回不可变Set，元素是x |
| list(Enumeration) | 转换旧式代码为Array List |
| enumeration(Collection) | 转为旧式代码 |
import static java.util.Collections.*;public class Test1 {static <T> void print(T t) {System.out.println(t);}static List<String> list = Arrays.asList("one Two three Four five six one".split(" "));public static void main(String[] args) {print(list); // [one, Two, three, Four, five, six, one]print(disjoint(list, singletonList("Four"))); // falseprint(max(list)); // threeprint(max(list, String.CASE_INSENSITIVE_ORDER)); // Twoprint(indexOfSubList(list, singletonList("one"))); // 0print(lastIndexOfSubList(list, singletonList("one"))); // 6replaceAll(list, "one", "YO");print(list); // [YO, Two, three, Four, five, six, YO]reverse(list);print(list); // [YO, six, five, Four, three, Two, YO]rotate(list, 2);print(list); // [Two, YO, YO, six, five, Four, three]copy(list, Arrays.asList("1 2".split(" ")));print(list); // [1, 2, YO, six, five, Four, three]swap(list, 0, list.size() - 1);print(list); // [three, 2, YO, six, five, Four, 1]shuffle(list, new Random());print(list); // [Four, YO, five, 1, 2, three, six]fill(list, "X");print(list); // // [X, X, X, X, X, X, X]List<String> nCopies = nCopies(3, "no");print(nCopies); // [no, no, no]Enumeration<String> enumeration = enumeration(nCopies);Vector<String> vector = new Vector<>();// 演示枚举的用法while (enumeration.hasMoreElements()){vector.addElement(enumeration.nextElement());}print(list(vector.elements())); // [no, no, no]}
}
List的排序和查询
public class Test1 {static <T> void print(T t) {System.out.println(t);}// 注意：asList()返回的List不可增删static List<String> list = new ArrayList<>(Arrays.asList("one two three four five six one".split(" ")));public static void main(String[] args) {shuffle(list);print(list); // [two, three, one, one, four, six, five]ListIterator<String> listIterator = list.listIterator(list.size()-3);while (listIterator.hasNext()){listIterator.next();listIterator.remove();}print(list); // [two, three, one, one]sort(list,String.CASE_INSENSITIVE_ORDER);int index = binarySearch(list, list.get(2), String.CASE_INSENSITIVE_ORDER);print(index); // 2}
}
设定collection或Map不可更改
public class Test1 {static <T> void print(T t) {System.out.println(t);}static List<String> list = new ArrayList<>(Arrays.asList("one two three four five six one".split(" ")));public static void main(String[] args) {Collection<String> collection = unmodifiableCollection(list);List<String> unmodifiableList = unmodifiableList(Test1.list);Set<Object> unmodifiableSet = unmodifiableSet(new HashSet<>(list));SortedSet<String> unmodifiableSortedSet = unmodifiableSortedSet(new TreeSet<>(list));Map<Object, Object> unmodifiableMap = unmodifiableMap(new HashMap<>());}
}
Collection或Map的同步控制
public static void main(String[] args) {// 同步容器Collection<Object> synchronizedCollection = Collections.synchronizedCollection(new ArrayList<>());List<Object> synchronizedList = Collections.synchronizedList(new ArrayList<>());Set<Object> synchronizedSet = Collections.synchronizedSet(new HashSet<>());Map<Object, Object> synchronizedMap = Collections.synchronizedMap(new HashMap<>());// 快速报错：当多个进程同时修改同一个容器内容时会报错List<String> list = new ArrayList<>();Iterator<String> it = list.iterator();list.add("a");while (it.hasNext()) {it.next(); // java.util.ConcurrentModificationException}}
17.12 持有引用
对于某些对象，当没有普通引用指向它时，我们希望以后还可以继续使用它，但同时当内存耗尽时，也允许释放该对象；Reference就是解决该问题的类，其有三个实现类SoftReference/WeakReference/PhantomReference,其强度由强到弱。
class VeryBig{private static final int SIZE = 10000;private long[] la = new long[SIZE];private String flag;public VeryBig(String flag){this.flag = flag;}@Overridepublic String toString() {return flag;}@Overrideprotected void finalize() throws Throwable {System.out.println("清理："+flag);}
}class References{private static ReferenceQueue<VeryBig> rq = new ReferenceQueue<>();public static void checkQueue(){Reference<? extends VeryBig> poll = rq.poll();if (poll != null) {System.out.println("在队列中："+poll.get());}}public static void main(String[] args) throws InterruptedException {LinkedList<SoftReference<VeryBig>> sa = new LinkedList<>();for (int i = 0; i < 5; i++) {sa.add(new SoftReference<>(new VeryBig(String.valueOf(i)),rq));System.out.println(sa.getLast());/*java.lang.ref.SoftReference@27c170f0java.lang.ref.SoftReference@5451c3a8java.lang.ref.SoftReference@2626b418java.lang.ref.SoftReference@5a07e868java.lang.ref.SoftReference@76ed5528*/checkQueue();}LinkedList<WeakReference<VeryBig>> wa = new LinkedList<>();for (int i = 0; i < 5; i++) {wa.add(new WeakReference<>(new VeryBig(String.valueOf(i)),rq));System.out.println(sa.getLast());/*java.lang.ref.SoftReference@76ed5528java.lang.ref.SoftReference@76ed5528java.lang.ref.SoftReference@76ed5528java.lang.ref.SoftReference@76ed5528java.lang.ref.SoftReference@76ed5528*/checkQueue();}System.gc();/*清理：4清理：3清理：2清理：1清理：0*/Thread.sleep(1000);LinkedList<PhantomReference<VeryBig>> pa = new LinkedList<>();for (int i = 0; i < 5; i++) {pa.add(new PhantomReference<>(new VeryBig(String.valueOf(i)),rq));System.out.println(sa.getLast());checkQueue();/*java.lang.ref.SoftReference@76ed5528在队列中：nulljava.lang.ref.SoftReference@76ed5528在队列中：nulljava.lang.ref.SoftReference@76ed5528在队列中：nulljava.lang.ref.SoftReference@76ed5528在队列中：nulljava.lang.ref.SoftReference@76ed5528在队列中：null*/}}
}
/*
可以看到，当对象被清理后，仍然可以通过Reference访问到，但是此时对象已为null
*/
WeakHashMap
class Element{private String flag;public Element(String flag) {this.flag = flag;}@Overridepublic String toString() {return flag;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Element element = (Element) o;return flag != null ? flag.equals(element.flag) : element.flag == null;}@Overridepublic int hashCode() {return flag.hashCode();}@Overrideprotected void finalize() throws Throwable {System.out.println(getClass().getSimpleName()+" "+flag);}
}class Key extends Element{public Key(String flag) {super(flag);}
}class Value extends Element{public Value(String flag) {super(flag);}
}public static void main(String[] args) throws InterruptedException {// Key[] keys = new Key[10];List<Key> keys = new ArrayList<>();WeakHashMap<Key,Value> map = new WeakHashMap<>();for (int i = 0; i < 10; i++) {Key k = new Key(Integer.toString(i));Value v = new Value(Integer.toString(i));if (i % 3 == 0) {keys.add(k);}map.put(k, v);}System.gc();/*Key 8Key 7Key 5Key 4Key 2Key 1*/Thread.sleep(1000);}
// 可以看到，没回收三个会跳过一个，因为跳过的被普通引用了。而普通引用的对象，在该方法结束前都不会被清理。
// WeakHashMap用来保存WeakReference,其允许垃圾回收机制在该方法未结束前就清理键和值
17.13 Java1.0/1.1的容器
Vector和Enumeration
public static void main(String[] args) {// 老版本唯一可以自我扩展的序列Vector<String> vector = new Vector<>(Arrays.asList("a","b","c"));// 老版本迭代器Enumeration<String> elements = vector.elements();while (elements.hasMoreElements()){System.out.println(elements.nextElement());/*abc*/}}
HashTable
与HashMap非常相似，直接使用HashMap即可。
Stack
public static void main(String[] args) {Stack<String> stack = new Stack<>();for (String s : "a b c".split(" ")) {// 进栈stack.push(s);}// 继承自Vector，具有其的行为// 这是不合理的，因该是组合，而不是继承System.out.println(stack.elementAt(2)); // cwhile (!stack.empty()) {// 出栈System.out.println(stack.pop());/*cba*/}}
这篇关于第17章 容器深入研究的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
