java集合概述

SPPan 2019-03-26 Java基础 45人已围观

Java集合是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、数组、映射等。Java集合工具包位置是java.util.*。

Java集合主要可以划分为4个部分:List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections)。

1. 继承结构

1.1 Collection继承结构

Collection继承结构图

Collection是一个接口,是高度抽象出来的集合,它包含了集合的基本操作和属性。

Collection包含了List和Set两个子接口。

List是一个有序的队列,每一个元素都有它的索引。第一个元素的索引值是0。List的实现类有LinkedList, ArrayList, Vector, Stack。

Set是一个不允许有重复元素的集合。Set的实现类有HashSet和TreeSet。HashSet依赖于HashMap,它实际上是通过HashMap实现的;TreeSet依赖于TreeMap,它实际上是通过TreeMap实现的。

1.2 Map继承结构

Map继承结构图

Map是一个映射接口,即key-value键值对。Map中的每一个元素包含“一个key”和“key对应的value”。

AbstractMap是个抽象类,它实现了Map接口中的大部分API。而HashMap,TreeMap,WeakHashMap都是继承于AbstractMap。

Hashtable虽然继承于Dictionary,但它实现了Map接口。

2. 集合实现类

2.1 List接口

2.1.1 ArrayList类

ArrayList实现了可变大小的数组。它允许所有元素,包括null。

ArrayList没有同步。size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量(Capacity),用于表示存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加。

2.1.2 LinkedList类

LinkedList实现了List接口,允许null元素。

此外LinkedList提供额外的get,remove,insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。

2.1.3 Vector类

Vector非常类似ArrayList,但是Vector是同步的。

2.1.4 Stack类

Stack继承自Vector,实现一个后进先出的堆栈。

2.2 Set接口

2.2.1 HashSet类

Java.util.HashSet类实现了Java.util.Set接口。

它不允许出现重复元素。不保证集合中元素的顺序。允许包含值为null的元素,但最多只能有一个null元素。

2.2.2 TreeSet类

可以实现排序等功能的集合,它在将对象元素添加到集合中时会自动按照某种比较规则将其插入到有序的对象序列中。

2.3 Map接口

2.3.1 Hashtable类

Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。添加数据使用put(key, value),取出数据使用get(key),这两个基本操作的时间开销为常数。Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。

2.3.2 HashMap类

HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。

2.3.3 WeakHashMap类

WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。

吐槽(0)

相关文章

文章评论

    共有0条评论

文章目录