Java核心技术读书笔记9-3 Java集合相关算法与遗留集合

5.算法

由于泛型机制的支持，对于集合可以实现很多通用算法。（泛型，迭代器，接口如Collection完成通用算法的编写）

5.1 排序与混排
Collection.sort对实现了List接口的集合进行排序，元素实现Comparable或调用时传入比较器，默认升序排列。
其内部调用了List接口实现类对象的sort方法。而这个sort方法又会对list构造一个数组，然后对这个数组调用Arrays.sort方法，再将结果设置回list。
仅当传入参数的列表是可修改的才可以进行排序。
如果列表支持set方法，则是可修改的。
如果列表支持add和remove方法，则是可改变大小的。
Collections还支持通过shuffle方法将元素打乱顺序。

5.2 二分查找
Collections的binarySearch方法实现了对List接口实现类的二分查找。同时参数列表必须是排好序的（且最好支持随机访问否则将变为线性查找），否则将返回不正确的结果。若还没有排好序，则可以提供一个比较器作为第三个参数。
若找到目标元素，将返回一个大于等于0的数值，该数值即为匹配元素的下标。
若返回的是一个负值，则可以根据该值找到正确的插入位置，如返回i，其插入位置即-i - 1。

5.2 其它简单算法

5.4 批操作
差集（coll1 = coll1 - coll2）：coll1.removeAll(coll2)
交集（coll1 = coll1 ∩ coll2）：coll1.retainAll(coll2)

5.5 集合与数组的转换
数组->集合：Arrays.asList(array); 返回不可变长的集合视图
集合->数组：
Object[] = coll.toArray(); //返回Object数组且不可以转换类型。
T[] = coll.toArray(new T[n]); //返回一个参数类型的数组，器类型为T，其长度为coll.size()与n的最大值，空位用null填充。

6.遗留集合

Java最初的集合类库，如vector、Hashtable，现在已经被集成到集合框架中List、Map。

6.1 Hashtable
Vector与Hashtable都是同步的，但如果对同步和遗留代码兼容性没有任何要求，则应该使用HashMap，若要并发访问，也应该使用ConcurrentHashMap。

6.2 枚举
遗留集合使用Enumeration接口对元素遍历。使用的是hashMoreElements和nextElement方法，在使用方式上与迭代器的相应方法类似。
Enumeration e1 = hahsTable().elements(); // 返回Key-Value中值组成的枚举集合
Enumeration e2 = Collections.enumeration(aCollectionObj); // 返回集合对象中元素组成的枚举集合

6.3 属性映射
属性映射是一种很特殊的数据结构，它的三个特性:
· 键与值都是字符串
· 表可以保存到一个文件中，也可以从文件中加载
· 使用一个默认的辅助表
Java使用Properties类可对其进行支持。

6.4 栈
Stack类，扩展了Vector类。不过对于栈最好还是用双端队列Deque来实现。

6.5 位集
BitSet类可以用于存放一个位序列（位向量）。
若果需要高效的存储位序列就可以使用位集。使用位集比Boolean和ArrayList更高效。同时也可以更方便的处理各个位，相比于int或long变量更加方便。