1。简介
JDK1.2引入了Java集合框架,包含一组数据结构。与数组不同,这些数据结构的存储空间会随着元素添加动态增加,其中,一些支持添加重复元素另一些不支持,一些支持空,一些能自动升序打印元素。
所有这些数据结构在Java。util包里,包含了收集、列表,设置,地图,SortedMap接口。这些接口的实现类有LinkedList, TreeSet, ArrayList, HashMap等。除了这些数据结构,java。util包还提供了日期、GregorianCalender StringTokenizer,随机这样的工具类。
2。分类
可以按照接口,实现,算法三个方面对集合框架中的数据结构进行分类:
接口:收集、列表,地图组成了集合框架中所有具体实现类的接口,它们定义了子类必须实现的方法,非常好记。比如向集合添加元素,会用到集合中定义的添加()方法
<李>实现:所有实现了上述3个接口的类,都被称作集合框架,实际上就是数据结构,比如LinkedList, TreeSet等
<李>算法:集合框架提供了很多可以直接调用的算法,比如求最大最小值,排的序,填充等
3。优缺点
有以下4个优点
减少工作量的同时增加了软件的可用性:不需要每个程序员动手实现排序,查找,找出元素在数据结构中出现的次数
<李>执行速度更快更持久:集合框架的底层数据结构分为两类,基于节点的和基于数组的,前者在频繁添加时效率更高,后者在频繁读取时速度更快。一些数据结构是同步线程安全的,但会影响速度有,另一些则不是线程安全的。程序员在选用数据结构前要清楚地了解这些因素
<李>互操作与转换:由于实现了收集接口,数据结构之间是可以相互转换的。可以克隆,可以把现有的结构转成同步版本,还可以在把基于链表的数据结构转为基于数组的结构
有以下2个缺点
当心类型转换:在集合框架类之间进行转换时要大大地小心,尤其要考虑泛型类型的兼容性
<李>运行时类型检查:集合框架在运行时会抛出异常,需要编程时多加注意
4。继承体系
java。util中的数据结构继承体系分为两大类,一类实现了收集接口,一类实现了地图接口。
收集继承体系
地图继承体系(图片来自维基百科)
集合框架核心接口及实现类:
集合:根接口,大部分数据结构都实现了收集接口中的方法
<李>设置:实现设置接口的数据结构不允许重复的元素,例如HashSet, LinkedHashSet
<李>SortedSet:实现SortedSet接口的数据结构默认可按升序打印元素,例如TreeSet
<李>列表:实现列表接口的数据结构允许重复元素,可通过指数访问元素,例如LinkedList, ArrayList,向量
<李>地图:实现地图接口的数据结构存储键值对,不允许重复的关键,例如HashMap, LinkedHashMap,散列表
<李>SortedMap:继承了地图接口,存储键值对,不允许重复的关键,默认可按关键升序打印元素,例如TreeMap
SortedSet与SortedMap默认的排序是自然序,可通过比较器或类似的接口实现自定义排序。
在接口与具体的实现类之间还有一些抽象类,如下图:
这些抽象类为集合增加了很多功能:
HashSet:实现设置接口,不允许重复的元素,底层数据结构哈希表
<李>LinkedHashSet:实现设置接口,不允许重复的元素,底层数据结构哈希表与双链表
<李>TreeSet:实现NavigableSet接口,不允许重复的元素,底层数据结构红黑树
<李>ArrayList:实现列表接口,允许重复元素,底层数据结构可变数组
<李>LinkedList:实现列表接口,允许重复元素,底层数据结构双链表
<李>向量:实现列表接口,允许重复元素,底层数据结构可变数组
<李>HashMap:实现地图接口,不允许重复的关键,底层数据结构哈希表
<李>LinkedHashMap:实现地图接口,不允许重复的关键,底层数据结构哈希表与双链表
