JCF：Java集合框架

JCF主要数据结构实现类

列表 List，ArrayList，LinkedList

• 有序的Collection
• 允许重复元素

List的主要实现

• ArrayList 非同步的
• LinkedList 非同步的
• Vector 同步

ArrayList

• 以数组实现的列表，不支持同步 List list = Collections.synchronizedList(new ArrayList())
• 利用索引位置可以快速定位访问
• 不适合指定位置的插入、删除操作
• 适合变动不大，主要用于查询的数据
• 和Java数组相比，其容量是可以动态调整的
• ArrayList在元素填满容器时会自动扩充容器大小的50%

LinkdeList

• 以双向链表实现的列表，不支持同步 List list = Collections.synchronizedList(new LinkedList())
• 可被当作堆栈、队列和双端队列进行操作
• 顺序访问高效，随机访问较差，中间插入和删除高效
• 适用经常变化的数据

Vector

• 和ArrayList类似，可变数组实现的列表
• Vector同步，适合在多线程下使用
• 原先不属于JCF框架，属于Java最早的数据结构，性能较差
• 从JDK1.2开始，Vector被重写，并纳入到JCF
• 官方文档建议在非同步情况下，优先适应ArrayList

总结

• 同步采用Vector
• 非同步情况下，根据数据操作特点选取ArrayList/LinkedList

集合 Set，HashSet，TreeSet，LinkedHashSet

Set
确定性：对任意对象都能判定其是否属于某一个集合
互异性：集合内每个元素都是无差异的，注意是内容差异
无序性：集合内的顺序无关

HashSet 基于散列函数的集合，无序，不支持同步
TreeSet 基于树结构的集合，可排序，不支持同步
LinkedHashSet 基于散列函数和双向链表的集合，可排序，不支持同步

HashSet

• 基于HashMap实现的，可以容纳null元素
• 不支持同步Set s = Collections.synchronizedSet(new HashSet());

LinkedHashSet

• 继承HashSet，也是基于HashMap实现的，可以容纳null元素
• 不支持同步Set s = Collections.synchronizedSet(new HashSet())
• 通过一个双向链表维护插入顺序

TreeSet

• 基于TreeMap实现的，不可以容纳null元素，
• 不支持同步SortedSet s = Collections.synchronizedSortedSet(new TreeSet())
• 根据compareTo方法或指定Comparator排序

HashSet和LinkedHashSet判定元素重复的原则

• 判定两个元素的hashCode是否相同，若不同，返回false
• 若两者hashCode相同，判定equals方法，若不同，返回false，否则返回true。

TreeSet判定元素重复的原则

• 需要元素继承自Comparable接口
• 比较两个元素的compareTo方法

映射 Map，HashMap，TreeMap，LinkedHashMap

Map
HashMap
TreeMap
LinkedHashMap

JCF主要算法类

• Arrays
• Collections