java基础——Collection和Map
集合类的作用
- 集合类也叫做容器类,和数组一样,用于存储数据,但数组类型单一,并且长度固定,限制性很大,而集合类可以动态增加长度。
- 集合存储的元素都是对象(引用地址),所以集合可以存储不同的数据类型,但如果是需要比较元素来排序的集合,则需要类型一致。
- 集合中提供了统一的增删改查方法,使用方便。
- 支持泛型,避免数据不一致和转换异常,还对常用的数据结构进行了封装。
集合框架体系的组成
Collection体系中有三种集合:Set、List、Queue
- Set(集): 元素是无序的且不可重复。
- List(列表):元素是有序的且可重复。
- Queue(队列):封装了数据结构中的队列。
Map体系
- Map用于保存具有映射关系的数据,即key-value(键值对)。Map集合的key是唯一的,不可重复,而value可以重复。所以一个value可以对应多个key。
- Map体系除了常用类之外,还有Properties(属性类)也属于Map体系。
Iterator(迭代器)
- 基本功能就是遍历集合中的所有元素,除了List集合有一个独有的迭代器Listiterator,别的集合类都是一样的。
- 每个集合类都有iterator(),调用该方法就能得到迭代器对象。
- 如果List集合使用迭代器,建议使用ListIterator,比原有的迭代器多了一些方法。
- 除了使用迭代器遍历集合元素,也可以使用加强for和Java8的foreach()方法。如果是List集合,使用for循环也能做到。
二、 用法
(一)集合框架涉及的数据结构
1.数据结构分类
1)线性表是在内存中数据的一种组织、存储的方式;一维数组、顺序表、链表、栈、队列,循环队列、散列表等结构是逻辑上的概念,是一种理念与思想,是属于线性表中的一种逻辑实现。
2)Java中数据结构涉及到了数组(一维、多维)、顺序表(ArrayList、Vector)、链表(LinkedArrayList、LinkedSet)、栈(stack)、队列(Queue)、散列表(HashMap)、树(TreeSet、TreeMap)等
(二)集合框架图谱
1.集合框架主要实现类
2.集合框架类图
1)Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements)。一些Collection允许相同的元素而另一些不行,一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。
2)所有实现Collection接口的类都必须提供两个标准的构造函数:无参数的构造函数用于创建一个空的Collection,有一个Collection参数的构造函数用于创建一个新的Collection,这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
3)为什么继承Iterable接口而不继承Iterator?
因为Iterator接口的核心方法next()或者hasNext()是依赖于迭代器的当前迭代位置的。 如果Collection直接实现Iterator接口,势必导致集合对象中包含当前迭代位置的数据(指针),当集合在不同方法间被传递时,由于当前迭代位置不可预置,那么next()方法的结果会变成不可预知。 除非再为Iterator接口添加一个reset()方法,用来重置当前迭代位置。 但即使这样,Collection也只能同时存在一个当前迭代位置,而Iterable则不然,每次调用都会返回一个从头开始计数的迭代器。 多个迭代器是互不干扰的。
不同的Collection接口的子接口的实现类返回的Iterator具体类型可能不同,Array可能返回ArrayIterator,Set可能返回 SetIterator,Tree可能返回TreeIterator,但是它们都实现了Iterator接口。因此,客户端不关心到底是哪种 Iterator,它只需要获得这个Iterator接口即可,这就是面向对象的威力。
- Iterator it = collection.iterator(); // 获得一个迭代子
- while(it.hasNext()){
- Object obj = it.next(); // 得到下一个元素
- }
(三)Collection接口
1.List接口
List是有序的Collection,使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组。和下面要提到的Set不同,List允许有相同的元素。除了具Collection接口必备的iterator()方法外,List还提供一个listIterator()方法,返回一个ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,还能向前或向后遍历。实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。
1)ArrayList
ArrayList实现了可变大小的数组,就像传统的数组一样,它允许所有元素,包括null。size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间,其他的方法运行时间为线性。
每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小,这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。和LinkedList一样,ArrayList也是非同步的(unsynchronized)。
2)LinkedList
LinkedList实现了List接口,用链表来保存数据,允许null元素。此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque),可以认为LinkedList在方法和逻辑上和ArrayList是一样的,只是在性能上有一定的区别,ArrayList适合随机访问LinkedList更适合插入和删除,在对性能没有很大要求是是可以忽略这个差别的。
注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:
List list = Collections.synchronizedList(new LinkedList(...));
3)Vector
Vector非常类似ArrayList,但是Vector是同步的。由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但是,因为Vector是同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常。
ArrayList 和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要设计到数组元素移动等内存操作,所以索引数据快插入数据慢,Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快!
4)Stack
Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。
2.Set接口
Set是一种不包括重复元素的Collection。它维持它自己的内部排序,所以随机访问没有任何意义。与List一样,它同样运行null的存在但是仅有一个。由于Set接口的特殊性,所有传入Set集合中的元素都必须不同,同时要注意任何可变对象,如果在对集合中元素进行操作时,导致e1.equals(e2)==true,则必定会产生某些问题。实现了Set接口的集合有:EnumSet、HashSet、TreeSet。
1)HashSet
HashSet堪称查询速度最快的集合,因为其内部是以HashCode来实现的。它内部元素的顺序是由哈希码来决定的,所以它不保证set 的迭代顺序,特别是它不保证该顺序恒久不变。
2)TreeSet
基于TreeMap,生成一个总是处于排序状态的set,内部以TreeMap来实现。它是使用元素的自然顺序对元素进行排序,或者根据创建Set 时提供的Comparator进行排序,具体取决于使用的构造方法。
3)LinkedHashSet
底层是链表实现的,是set集合中唯一一个能保证怎么存就怎么取的集合对象,因为是HashSet的子类,所以也是保证元素唯一的,与HashSet的原理一样。
3.Queue接口
1)阻塞式队列(BlockingQueue):队列满了以后再插入元素则会抛出异常,主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。
2)双端队列(Deque):支持在头、尾两端插入和移除元素,主要包括:ArrayDeque、LinkedBlockingDeque、LinkedList。
(四)Map接口
Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value,所以它不能存在相同的key值,当然value值可以相同。实现map的有:HashMap、TreeMap、Hashtable、Properties、EnumMap。
1)HashMap
HashMap和Hashtable类似,HashMap使用hash映射来存取数据,这个速度是相当快。不同之处在于HashMap是非同步的,并且允许null,即null value和null key。,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。
2)TreeMap
键以某种排序规则排序,内部以red-black(红-黑)树数据结构实现,实现了SortedMap接口
3)Hashtable
Hashtable继承Dictionary类实现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这样的操作。Hashtable是同步的。
三、总结
(一)集合类型的异同点
1.Vector和ArrayList
1)vector是线程同步的,所以它也是线程安全的,而arraylist是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用arraylist效率比较高。
2)如果集合中的元素的数目大于目前集合数组的长度时,vector增长率为目前数组长度的100%,而arraylist增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据,用vector有一定的优势。
3)如果查找一个指定位置的数据,vector和arraylist使用的时间是相同的,都是0(1),这个时候使用vector和arraylist都可以。而如果移动一个指定位置的数据花费的时间为0(n-i)n为总长度,这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据所花费的时间为0(1),而查询一个指定位置的数据时花费的时间为0(i)。
4)ArrayList 和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,都允许直接序号索引元素,但是插入数据要设计到数组元素移动等内存操作,所以索引数据快插入数据慢,Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快!
2.Aarraylist和Linkedlist
1)ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
2)对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
3)对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。
4)这一点要看实际情况的。若只对单条数据插入或删除,ArrayList的速度反而优于LinkedList。但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据。
3.HashMap与TreeMap
1)HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。HashMap中元素的排列顺序是不固定的)。
2)在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。 这个TreeMap没有调优选项,因为该树总处于平衡状态。
4.Hashtable与HashMap
1)历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现 。
2)同步性:Hashtable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的 。
3)值:只有HashMap可以让你将空值作为一个表的条目的key或value 。
(二)如何选择合适的集合类型
1.对List的选择
1)对于随机查询与迭代遍历操作,数组比所有的容器都要快。所以在随机访问中一般使用ArrayList。
2)LinkedList使用双向链表对元素的增加和删除提供了非常好的支持,而ArrayList执行增加和删除元素需要进行元素位移。
3)对于Vector而已,我们一般都是避免使用。
4)将ArrayList当做首选,毕竟对于集合元素而已我们都是进行遍历,只有当程序的性能因为List的频繁插入和删除而降低时,再考虑LinkedList。
2.对Set的选择
1)HashSet由于使用HashCode实现,所以在某种程度上来说它的性能永远比TreeSet要好,尤其是进行增加和查找操作。
2)虽然TreeSet没有HashSet性能好,但是由于它可以维持元素的排序,所以它还是存在用武之地的。
3.对Map的选择
1)HashMap与HashSet同样,支持快速查询。虽然HashTable速度的速度也不慢,但是在HashMap面前还是稍微慢了些,所以HashMap在查询方面可以取代HashTable。
2)由于TreeMap需要维持内部元素的顺序,所以它通常要比HashMap和HashTable慢。
转载:https://blog.****.net/moHedong/article/details/46442833