06.集合

12a2024/10/3大约 30 分钟

06.集合

6.1 集合框架

在Java最初版本只提供了少部分数据结构接口,随着Java1.2版本问世,设计人员开始考虑推出功能完善的数据结构,他们希望类库小而易于学习,不希望像C++的STL一样复杂,又希望融入泛型算法
与数据结构类库常见做法一样,java把接口和实现分离,在接口中并没有写明实现方法,一个个类拓展了接口,完成了不同的目标(例如:链式队列和循环队列),他们可以通过接口直接引用并使用,在Java中还设计了如AbstractQueue这样的类供设计者更方便地实现自己的对应数据结构
Collection接口:集合最基本的接口是Collection接口,他有两个基本方法:boolean add(E element)向集合中添加元素,成功改变集合返回true和Iterator<E> iterator()返回实现了迭代器的对象,通过它可依次访问集合中的元素
Iterator接口:迭代器中有四个方法:E next()反复调用可以逐个访问所有元素,如果没有下一个抛出NoSuchElementException异常,boolean hasNext()判断有没有下一个元素,void remove()删除上一个访问(使用next())的元素,如果没有使用next()会抛出IllegalStateException异常,default void forEachRemaining(Consumer<? super E> action)如果不希望写foreach,可以使用这个传入一个需要执行的lambda表达式,它会对每个元素不断调用直到没有元素为止
- 在使用next()时,应该进行判断,如果有下一个,则继续,实际上,foreach循环在编译器中被简单转换为这样的循环(例:Iterator<String> iter = str.iterator(); while(iter.hasNext()){ String element = iter.next; //and do something with element}),只要该对象扩展了Iterator接口就可以使用foreach循环,而Collection就扩展了,因此集合都可以使用foreach循环
- Java的迭代器处理方式:C++是根据数组索引建模完成迭代器的,而java不是这样,查找和位置紧密结合,查找元素唯一的方法是通过next()方法,在执行时,迭代器会随next()调用向前移动,可以认为迭代器在两个元素之间,使用next()方法会使迭代器越过一个元素,并返回越过的元素,这和InputSteam.read读取数据流类似

其实Iterator接口的next方法和hasNext方法和Enumeration接口的方法功能一致,本来设计者准备继续使用Enumeration接口实现,但它的方法名太长了,于是使用了新接口

泛型的实用方法:由于上面介绍的都是泛型接口,意味着你可以编写能够处理任何集合类型的方法,例如:检测任意集合是否包含指定元素的方法,Java的设计者认为,如果这些方法很有用,应该提供给用户使用,这样使用者就不用自己定义了,contains就是这样的方法,Collection有很多这种样子的方法,如果希望创建自己的数据结构,可以使用AbstractCollection类,许多工具方法已经实现

//Collection的有用的方法
//返回用于访问集合的迭代器
Iterator<E> iterator();
//返回存储元素的个数
int size();
//判断有没有元素
boolean isEmpty();
//是否包含一个元素,包含返回true
boolean contains(Object);
//包含集合所有元素返回true
boolean containsAll(Collection<E>);
//添加元素,成功改变集合返回true
boolean add(E);
//添加集合所有元素,集合改变返回true
boolean addAll(Collection<? extends E>);
//删除满足条件的元素,如果改变集合返回true
default boolean removeIf(Predicate<? super E>);
//删除所有元素(比新创建快)
void clear();
//删除不在给定集合中的元素,改变集合返回true
boolean retainAll(Collection<?> other);
//返回集合中的对象数组(Object类型存储)
Object[] toArray();
//返回这个集合中的对象数组(给定类型存储),如果给定数组够大,就用给定数组存储
<T> T[] toArray(T[]);

6.2 集合框架接口

集合接口继承图:
集合有两个基本的接口Collection(单值)和Map(键值对),对Map迭代,得到的都是key,如果希望从中得到值,应该使用get(Key)
List是一个有序集合,它增加的元素会到特定位置,可以随机访问(存取对应位置的值),ListIterator继承了Iterator接口,提供了在迭代器前增加一个元素的方法add(E),在这方面,设计地不太好,由于有两种有序的数据结构(数组和链表)能够支持集合,数组很适合随机访问,但链表随机访问很慢,最好声音使用迭代器,如果提供两个不同接口会容易些
Set接口相当于更严谨定义的Collection接口,它的方法更为严谨,add方法不能添加重复元素,定义完善的equal方法,如果两集合元素相同,不论位置,返回true,如果equal方法返回真,hashCode()的值也应该保持一致,Set可允许编写只接受集的方法
SortedSet和SortedMap接口会提供用于排版的比较器对象,这两个接口提供可以得到子集视图的方法
在Java6中引入了NavigableSet和NavigableMap包含一些用于搜索和遍历有序集合和映射的方法,TreeSet和TreeMap实现了这些接口

RandomAccess接口是一个标记接口,不包含任何方法,但可用来测试,集合是否支持高效的随机访问(根据索引直接读取)

6.3 具体集合

java类库的集合和用途简述:
ArrayList:在之前已经介绍了ArrayList,它是可变长度数组,这里对方法不再说明
- 如果希望这个可变数组列表能够胜任多线程任务,应该使用Vector,它的所有方法都是同步的,可以安全地从多个线程中访问对象,而ArrayList是不同步的,如果不需要使用同步线程,不希望在同步上浪费大量时间,就使用ArrayList,否则使用Vector
LinkList链表:可以高效增减数组元素的序列,在Java中,所有的链表实际上都是双向链接的,删除元素和修改元素都只需修改元素周围的链接(java会自动回收),链表绕来绕去的指针给人留下了极坏的印象,在Java中提供了LinkedList类用于存放链表,它是有序集合,每个位置都很重要
- LinkList.add方法将对象添加到链表尾部,LinkList类将元素添加特定位置的方法依赖于ListIterator接口,通过迭代器负责实现
- 如果需要在中间添加元素,可以转换使用迭代器LinkIterator遍历,然后遍历完要添加位置的前一个元素,使用迭代器.add(E)的方法添加元素到刚访问的元素之后,而set方法会修改刚访问的元素,如果在生成迭代器之后,直接调用add方法,会将元素添加到表头
- ListIterator接口还有反向next的方法previous()和判断方法hasPrevious(),可以往回遍历
- 请勿一边修改一边遍历集合,如果在另一个迭代器修改了,这个迭代器检测出从外部修改了,会对next()调用抛出ConcurrentModificationException异常,因为迭代器会记录自己的修改次数,迭代器会检查单独修改次数和总集合修改次数一致,如果不一致,会抛出该异常
- java还给LinkList提供了访问特定位置的方法,虽然一般需要访问特定位置的时候,链表效率不高,会选择数组类型,但java还是提供了get(int)得到对应位置对象(它有个小优化,如果位置在中位数之后使用逆向遍历),LinkIterator中还有nextIndex和previousIndex方法获取下一次迭代的位置信息
- 如果数据长度很小,不必为get和set带来的开销而烦恼,完全可以使用ArrayList,如果需要随机访问,就使用ArrayList或数组
- LinkedList实现了removeFirst和removeLast移除首尾的双端队列Deque接口的方法
HashSet散列集:链表和数组的元素次序是根据你的意愿确定的,如果想要知道某一元素的位置,但不知道其位置只能遍历整个集合,但散列集不一样,它是根据元素的散列码得到的位置,不同数据将产生不同的散列码,散列码可通过hashCode()方法得到,字符串的散列码根据内容决定,而从Object继承的散列码计算方式是根据存储地址来的,如果你希望自己实现,这个实现应该和equals函数结果一致
- 散列表数据结构就可以快速查找对象,在java中散列表(HashSet就基于此)是通过桶列表实现的,一个链表头构成的数组,每个桶存储散列码在一个区间内的元素,如果桶足够多,链表中的元素足够散(不根据散列码),查找的时间会很短
- 如果插入到表里的元素过多,就会增加桶中元素的冲突,降低检索性能,如果知道预计存入元素应该设定初始桶数目,一般设定为预计元素的75%-150%
- 当然,如果估计的桶数目过低,或者没法估计(默认为16),散列表太满时,会再散列,创建更多桶的表存储,而装填因子会确定何时重新,如果装填因子为0.75(默认值),说明填满了75%,就会重新分配,新的表容量是之前的两倍,对于大多数情况,这是合理的
- HashSet使用随机分散(似乎只是append添加到末尾)的方式将元素分散在链表中,所以会以看起来随机的顺序访问元素,只有不关心次序的情况下,才能使用它,如果希望遍历集合,可以将其转换为iterator进行处理,它实现了Collection系接口的方法
TreeSet树集:它和散列集类似,但是它是有序集合,可以以任意顺序将元素插入集合中,在遍历时自动按排序后的顺序呈现,当前排序使用的是红黑树,如果树中有n个元素,查找元素正确位置平均经过 $log_{2}n$ $l o g_{2} n$ 次比较
- 要使用树集必须保证元素类型提供了Comparable接口(实现为只有两个元素完全相同时,结果才为0),或者在初始化时传入一个Comparator比较器,如果不需要保证它是有序的,请使用散列集
- 从java6开始,TreeSet实现了NavigableSet接口,增加了几个查找元素以及反向遍历的便利方法,例如:得到比给定元素大的最小元素higher(),返回大于等于给定元素的最小元素ceiling(),删除并返回集合中的最大值pollFirst()等
Queue队列和Deque双端队列:队列允许在尾部添加元素,头部删除元素,而双端队列允许在头尾都增减元素,而ArrayDeque和LinkedList类都实现了Deque接口

//一些java.util.Queue方法的描述:
boolean add(E);
boolean offer(E);
//add和offer都是添加元素的方法,如果队列满了,add会抛出异常,而第二个方法只会返回false
E remove();
E poll();
//如果队列不空,抛出头部元素,如果队列是空的,第一个抛出异常,第二个返回null
E element();
E peek();
//如果队列不空,返回队列头元素,但不删除,如果队列为空,element抛出异常,peek返回null

//一些java.util.Deque方法
void addFirst();
void addLast();
void offerFirst();
void offerLast();
//将给定的元素添加到特定位置,在空间满时,add抛出异常,offer返回false
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
//如果队列不为空,删除对应位置的元素,如果队列为空,remove抛出异常,poll返回null
E getFirst();
E getLast();
E peekFirst();
E peekLast();
//如果队列不为空,返回对应位置的元素,不删除,如果为空,get抛出异常,peek返回null

PriorityQueue优先队列:优先队列可以按照任何顺序插入,但会按照有序的规则进行检测,无论何时调用remove方法,会得到按规则得到的最小元素,其实优先队列没有对所有元素排序,而是使用堆来存放数据,使用add和remove操作,都会使最小元素位于堆顶
- 拓展了Iterable <E>,Collection <E>,Queue <E>接口,一般使用add和remove方法
- 初始化时,允许使用指定的比较器排序,可传入比较器方法,或者使用已拓展Comparable接口的对象,在不使用时,被称为小顶堆,而使用了反的比较方法,得到的最大元素位于堆顶的称为大顶堆,PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
- 初始化时允许给定初始容量
- 对于寻找一棵树的第K小值,就可以使用堆和队列,在堆中存放k个极小值,队列当栈用存放遍历的元素,当堆满时,如果想进堆元素大于堆顶,则不处理,不然抛出堆顶,存放新元素

6.4 映射

和集合不同,映射(map)是一种用于查找相关元素的数据结构,如果提供了键就能找到值
映射库的两个基本实现(HashMap,TreeMap):这两个都实现了Map接口,散列映射对键进行散列,树映射将元素根据键的顺序组织为一棵搜索树,散列或比较函数都只应用于键,不会对值进行散列或比较,如果需要取值,请记住键名(唯一的)
- 如果需要对整个映射的所有键值对进行处理,可以使用foreach方法传入需要做的操作的lambda表达式或直接使用for-each循环
如果有相同的键想要存入一个映射,会覆盖之前的值
映射扩展了Map接口,其中的方法和collection接口名称不同,下面是方法列举:

//java.util.Map<K,V>
V get(Object);
//获得与键关联的值,如果映射没有这个键对象,会返回null
default V getOrDefault(Object,V);
//获得与键关联的值,如果映射没有这个键对象,返回设定值
V put(K,V);
//将值放入映射中,如果之前有这个键,返回之前的值,否则返回null
void putAll(Map<? extends K,? extends V>);
//将其它映射中所有值加入
boolean containsKey(Object);
//判断映射是否有这个键,如果有返回true
boolean containsValue(Object);
//判断映射是否有这个值,如果有返回true
default void foreach(BiConsumer<? super K,? super V>);
//对所有键值对执行给定的lambda表达式

//java.util.HashMap<K,V>初始化函数
HashMap();
HashMap(int);
HashMap(int,float);
//初始化函数中，int指定初始容量，float给定最大装填因子(当达到散列到更大的散列中)

//java.util.TreeMap<K,V>初始化函数
TreeMap();
TreeMap(Comparator<? super K>);
TreeMap(Map<? extends K,? extends V>);
TreeMap(SortedMap<? extends K,? extends V>);
//初始化树映射,使用比较器Comparator,Map和SortedMap是其它映射条目,会添加到该映射中

//java.util.SortedMap<K,V>初始化函数
Comparator<? super K> comparator();
//返回使用的比较器,如果使用的是CompareTo方法,返回null
K firstKey();
K lastKey();
//返回比较的最大值键或最小值键

更新映射条目:处理映射的一个难点是更新映射条目,正常情况下,要更新键对应的值,可以使用getOrDefault取出值,然后进行处理,再使用put放入,,这可以连在一起,比如对于词数统计值加1:counts.put(word,counts.getOrDefault(word) + 1);,不过也可以使用merge方法简化这个操作
- 在Map接口里有default V merge(K key,V value,BiFunction<? super V,? super V,? extends V> remappingFuncton);方法,这个方法中的Key如果和非null值关联,将函数remappingFuncton应用到value和当前对应值上,返回函数结果作为新的值,如果键不存在,则放入key和value
- 在Map接口里还有default V compute(K key,BiFunction<? super K,? super V,? extends V> remappingFuncton);方法,直接将键对应的值取出和键一起作为函数参数,将结果作为值存入,如果结果为null删除这个键
- Map中还有很多类似的处理函数,像上面的例子就可以使用counts.merge(word,1,Integer::sum)
映射视图:像Python一样可以使用键集,值集合(不是一个集),以及键值对集,键和键值对可以构成一个集合,因为键是唯一的,他们是返回Set集合(使用的方法是KeySet和entrySet),而值集合返回的是Collection对象(使用的方法是values),值得说明的是键集是一种非HashSet和TreeSet的一种另外一个实现的对象,Set集合扩展了Collection接口,一般使用其中方法像使用其它集合一样使用keySet
- 使用for-each枚举映射条目,对于单一键或者值而言,可以使用存储的类型进行枚举,如:Set<String> keys = map.KeySet(); for(String key:keys){ //do something with key },使用String就可以了,但是对于键值对集,这样不行,在Map中定义了内部类Entry,可以使用Map.Entry<K,V>获取每一映射,当然也可以使用var避免笨拙的声明,然后使用内部类对应的方法getKey获取键,getValue获取值
- 对键集视图中使用remove方法事实上会删除这个键值对,但是不能对键集视图添加元素,如果使用add方法,会抛出UnsupportedOperationException异常,这对映射条目视图(键值对集)同样有效,尽管对它而言,添加键值对似乎有意义,而Entry类也提供了修改值的方法setValue()

6.5 重要集和映射

弱散列映射:集合库中还有专用的映射类,他们用来解决某些问题,例如:WeakHashMap类是为了解决键值对中某一键的所有引用都已失去,但由于这个键依旧存储在集合中,虽然任何部分都不会再使用这个键了,但他不会被垃圾回收的问题,因此,在程序中需要经常删除已确定不会再使用的键,或者也可以选择使用WeakHashMap,当只有在映射内存在对应引用时,会将这个键删除
- 工作原理:WeakHashMap使用弱引用保存键,这是WeakReference对象,这种对象包含另一个对象的引用,对于这种类型的对象,垃圾回收机制在对象只由WeakReference对象引用的时候,也会将对象回收,这里会将已回收的弱引用放到一个队列里,WeakHashMap将会周期性检查队列,以便找出新增加的弱引用,将其从映射中删除

链接散列集与映射:LinkedHashSet和LinkedHashMap会记住插入元素的顺序,这样可以避免存储项位置看起来是随机的,它的实现原理是通过和HashSet一样的桶和双向链表储存,在存储元素时,不但要把元素存储进去,还要把上一个和下一个元素的引用添加到双向链表,在使用iterator转换时,顺序会和添加顺序一致
- 变种:使用LinkedHashMap<K,V>(initialCapacity,loadFactor,true)创建的链接散列映射,它在调用元素或放置元素时,都会将元素放在链表末尾(散列表桶中位置不变),这是为了处理"最近最少使用"的问题,如果一个元素最近最少使用,那它就会出现在迭代器前面,一般经常使用的会保存在内存中,而少使用的才会只放在数据库中,当在表中找不到元素项或表满时,就可以通过迭代器删除前面的元素,它们就是最少使用的元素,这个删除最少使用的元素可以自动化,只需要构造LinkedHashMap的子类(匿名子类,覆盖方法就够了),覆盖protected boolean removeEldestEntry(Map.Entry<K,V> eldest)方法,当你的这个方法返回true时,,添加的条目就会覆盖最老的条目,或者可以考虑最老元素,来决定是否删除

枚举集:EnumSet是枚举类型元素集的高效实现,由于枚举类型只有有限个实例,因此,它使用位序列实现,如果对应的值在集中,相应的位置为1,EnumSet没有公共的类构造器,使用工厂方法构造,可以使用Set接口的方法修改,而对应的EnumMap是键为枚举类型的映射,需要在构造函数中传入键的类型,例如:有枚举Weekday,可使用new EnumMap<Weekday,Employee>(Weekday.class)构造

标识散列映射:IdentityHashMap的键的散列值,不是使用HashCode计算的,而是使用System.identityHashCode计算,这是hashCode根据对象内存地址得到散列码时使用的方法,在进行比较时,IdentityHashMap使用==而不是equals,不同的对象哪怕内容一样,也是不同的,这可以用来查看哪些对象已经遍历过了,数据结构很简单,实际就是一个Object数组，但是在存储上并没有使用链表来存储，而是将K和V都直接存放在Object数组上,使用散列值存储,到一定程度会扩容

6.6 视图和包装器

你可能会认为用这么多接口和类来实现数量不多的具体集合类没太大必要,但前面展示的不是全部,可以使用视图获得其他实现了Collection接口或Map接口的对象,比如使用KeySet方法得到的特殊集合,看起来好像就是创建了一个新的集合,填入所有的键,然后返回就结束了,但是情况不是这样,实际上,它返回了一个Set对象,通过Set操纵原映射,这种集合就是视图

视图的应用

小集合:在java9中引入了一些静态方法,可以生成给定元素的集或列表,以及给定的键值对映射of方法,这个方法一共有12个重载,从0-10个参数到一个参数可变的方法(Map无法提供可变参数的方法,可以使用ofEntries能接受任意个Entry对象),提供特定性可以提高效率,这些集合对象是不可修改的,如果试图改变集合对象会导致UnsupportedOperationException异常,如果需要它可更改,可传递给ArrayList<>构造器,在Collections类(与Collection接口不同)中,还有重复性小集合的方法nCopies(n,anObject)将anObject重复存放n次,返回的结果也是实现list接口的不可变对象
```
List<String> name = List.of("Peter","Paul","Marry");
Set<Integer> name = Set.of(2,3,5);
Map<String，Integer> name = Set.of("Peter",2,"Paul",3,"Marry",5);
//传给ArrayList,得到可变集合
var name = ArrayList<>(List.of("Peter","Paul","Marry"));
```
子范围:可以为很多集合建立子范围视图,假如有一个列表staff,如果想要取出其中第10-19号元素,可以使用staff.subList(10,20)获得子范围视图,与String的subString基本相同,对子视图执行任何操作,操作都会自动反映到整个列表,Set和Map也有类似的方法,会返回在两键/元素之间的Map/Set子视图,在Java6引入的NavigableSet接口允许更多的控制子视图的范围的操作,比如视图是否包括边界
不可修改的视图:Collections类中还有几个方法用于生成不可修改的视图,如果你需要你的代码查看不修改一个集合内容,就可以使用这些方法,如果修改会抛出异常,集合仍保持不变,不可更改的视图不是集合本身不可修改，这些集合依旧可以通过其原始引用修改,只是不能通过该视图修,由于返回的是对应的接口,而不是类,有的定义在类中的方法无法使用,下面是可使用的不可修改视图生成方法,都需要传入可转换的接口类型,每个方法都用于处理一个接口
同步视图:如果从多个线程访问集合,就必须确保集合不被意外地破坏,例如:一个进程在插入元素,另一个进程在散列集合,这是灾难性的,可以使用视图保证集合是线程安全的,而没有实现线程安全的集合类,可以将任何一个映射转换成有同步访问方法的Map,使用var map = Collections.synchronizedMap(new HashMap<String,Employee>);这样就可以线程安全地使用map了,每个方法使用结束后才会执行下一个方法
检查型视图:检查型视图对泛型可能出现的问题提供调试分析,比如:将错误的元素类型放入这个集合中,在使用add()方法时,检查不到,只有在使用get()方法将它的值给一个应该使用类型的对象时,会出现强制类型转换异常,检查型视图可以检查这种问题,可以使用List<String> safeString = Collections.checkedList(strings,String.class)定义一个安全的列表,strings是一个列表
检查型视图受限于虚拟机,如果在集合中存入的是泛型,无法阻止其他类型化的泛型插入
可选操作说明:通常情况下,视图都有一定的限制,可能只读,可能无法更改大小,可能只能删除不能插入(键视图),如果试图执行不恰当的操作,视图就会抛出UnsupportedOperationException异常,在集合和迭代器接口中有很多被作为可选操作的方法,从理论上来讲,这种安排不令人满意,但是更好的解决方案会使接口数量增加数倍,让类库设计者无法接受,虽然可选操作被认为不应该出现在自己的设计中,但集合却不适合这种看法,集合设计者需要解决一组极其严格的而且相互冲突的需求,在你自己的编程问题中,很少会遇到这种问题,能够找到不使用可选这种极端做法

6.7 算法

为什么要使用泛型算法:泛型集合接口有一个很大的优点,即算法只要实现一次,编写一些算法很繁琐,很容易出错,人们不可能次次调试这些算法,在集合中,使用泛型解决一些问题,首先考虑执行这个算法所需要的最小集合接口,然后以此为参数类型的限定,然后就可以实现这个方法了,在java类库中,虽然不如标准C++类库一样丰富,但也有一些基础算法,包括二分查找、排序和一些其它实用算法
排序与混排:排序算法已经成为大多数编程标准语言库中的一个组成部分,java程序设计语言也不例外,Collections类中的sort方法可以对实现了List接口的集合(可修改的,即支持set方法)进行排序,这个方法假定元素实现了Comparator接口,当然也可以传入一个比较器,如果希望结果降序,可以使用Collections.reverseOrder(),这个方法会返回一个比较器,相当于b.compareTo(a)即反过来比较(在Comparator接口中有一模一样作用的同名方法),在java集合中,sort使用的是归并排序,虽然比快速排序慢,但是稳定,对于链表,是先存入数组,对数组排序,再复制回去
二分查找:如果在数组中查找对象,通常要依次遍历整个数组,但如果是有序的就可以使用二分查找,Collections.binarySearch方法就实现了这个算法,要查找元素,就必须提供集合和要查找的元素,如果集合没有采用CompareTo方法排序,还需要提供比较器对象,它会返回对应元素的索引,如果返回为负值,说明其中没有这个元素,不过这个返回值也是有意义的,可以通过返回值i来判断,这个元素应该存放在哪个位置,能保证数组的有序,插入位置应该为- i - 1,使用add.(- i - 1,element)就可以插入正确的位置,这个方法首先会查看对应数组是否实现了RandomAccess接口(链表就没有),否则会转而使用线性搜索
其他简单算法:包括复制元素到另一个列表;用常量值填充容器;逆置列表元素顺序等,下面就是部分实现函数,如果不满意,也可以使用Collection接口中的removeIf(删除满足条件的元素)和replaceAll(对每个元素进行处理)方法传入lambda表达式:
批操作:像Collection.replaceAll一样的方法就是批操作,在Collections中也有removeAll,retainAll(得到交集的操作)是成批复制或删除元素的,像这种批操作可以更进一步,利用到键视图或子范围视图这样的视图上,完成更改操作
集合和数组的转换:java的API大部分内容集合都是在集合框架前设计的,有的时候需要在集合和数组之间转换,如果需要把数组转换为集合,使用List.of方法可以达到目的,而将集合转换成数组就没那么容易了,可以使用toArray方法,得到的是Object数组,哪怕你知道其中存储的类型,也无法强制类型转换,不过你可以提供一个指定存储的类型的数组,会根据你传入的数组,创建正确类型的数组,如果提供的数组足够大,就直接使用这个数组存放
编写自己的算法:如果编写自己的算法,应该尽可能使用集合接口,而不是其具体实现,就如开头说的一样,接收一个通用的集合接口,处理所有相关问题,如果顺序重要,使用List接口,如果顺序不重要就使用接收任意类型的集合Collections,而返回值最好也如此设计(返回接口类型)

6.8 遗留的集合

从java1问世以来,集合框架中存在大量遗留的容器类
Hashtable类:经典的Hashable类和HashMap类作用一样,实际上,使用的接口也相同,与Vector类一样,它的方法是同步的,但现在可以使用HashMap方法,如果需要并发访问,则要使用ConcurrentHashMap
枚举:遗留的集合通过Enumeration接口而不是Iterator接口遍历元素序列,也就是前面说过的被替代的接口,如果发现遗留类实现了Enumeration接口,就可以使用Collections.list()方法将类转换为ArrayList或者使用Collections.enumeration()方法将一个集合转换为实现了Enumeration接口的对象
属性映射:属性映射是一种特殊的映射结构,它具有3个特点: 1️⃣ 键与值都是字符串 2️⃣ 这个映射很容易保存到文件或从文件加载 3️⃣ 有二级表存放默认值
- 实现属性映射的java类名为Properties,属性映射对于指定程序的配置很有用,可以使用setProperty()方法添加映射,使用store()将映射保存在文件输出流对象中,加载时可使用load()方法从文件输入流对象中加载属性映射,使用getProperty(key)得到对应的值,当然这个方法可以添加另一参数默认值,在没有该映射时,返回默认值,如果嫌麻烦,可以使用二级映射(初始化时从设定好的表中导入默认值,然后再执行添加操作)
- 属性是没有层次结构的简单表格,有的时候需要有类似window.main.color这样的层次结构,Properties类没有方法组织这样的层次结构,如果需要存储复杂的配置信息,应该改为使用Preference类

出于历史方面的原因,Properties实现了Map<Object,Object>,因此可以使用Map的get和put方法存入任何数据,因此最好坚持使用getProperty和setProperty方法

栈:从1.0版开始,标准类库就包含了Stack类,其中有push和pop方法,但Stack类扩展了Vector类,从理论角度来看,Vector类不太令人满意,你甚至能够使用并非栈操作的insert和remove方法在任何地方插入和删除值
位集:BitSet类用于存储一个位序列,把它称为位向量可能更加合适,如果需要高效存储位序列就可以使用位集,由于位集将位包装在字节里,所以使用位集比使用Boolean的ArrayList要高效得多,如果需要得到某个位置的状态(true or false),可以使用get(i)方法,而使用set(i)方法和clear(i)方法分别可以把i位置变成true和false,在位集中,还有与其它位集做与或异或的操作,甚至还有对于另一个位集为1的对应位置都变成0的andNot方法,最终这些操作会直接反映到自身上
- 经典案例:"埃拉托色尼筛选法"算法的实现,这个方法用来批量查找素数,依次删除 $2,3,...,\sqrt{n}$ 的倍数,这不是非常好的寻找素数的方法,但由于某些原因,成为了测试编译器性能的基准(也不是很好的测试基准的方法,因为它主要测试位运算),在java中,可以使用位集实现,一开始,先把所有设置为开(true),然后将已知素数的倍数置为关(false)状态,在java和C++实现执行做时间比较,如果没有改变g++的优化级别,java会比C++快很多,如果运行时间过长,触发Hotspot(java的动态编译器),java只能与C++打成平手