第一次发博客,纪念纪念......
作为一个初学者,发博客仅以记录自己的学习的知识点。
一。JAVA集合框架有两个基本接口:Collection和Map。·
二。队列(Queue extends Collection)
队列的实现方式通常有两种:
1.循环数组:高效,能随机访问,但是容量有限,如果对数组中随机删除或者添加会付出很大 代价。
2.链表:容量无限,不能随机访问,删除或者添加开销小,但是不能随机访问,只能遍历。
3.也可以扩展包中的abstractQueue类实现自己的队列。
4.双端队列:可以在头部或者尾部进行插入,删除的队列。不允许在中间插入数据。引入了Deque接口,由ArrayDeque类和LinkedList类实现。
5.优先级队列:使用堆的数据结构,对是一个可以自我调节的二叉树。将对象以任意顺序插入,但是总将优先级最小的对象移动到根。典型例子是任务调度。
三。迭代器(Iterator)
1. 迭代器用来遍历集合,next()用来遍历,在末尾调用next()会NosuchEllementException错误,Hasnext()可以用来判断是否到集合最后一个元素。
2.编译器会将for each循环翻译为带有迭代器的循环。
3.for each可以和所有实现了Iterable接口的对象一起工作,而Collection扩展了iterable接口,所以for each可以和所有标准库中的集合一起工作。
4.迭代器被认为是出于集合中两个元素之间,next()执行一次是返回它越过的哪一个元素。
5.remove()和next()具有互相依赖性,remove()删除的是next()返回的元素,所以必须一起使用,否则将抛出IllegalStateException错误。
6.ListIterator接口是Iterator接口的子接口,它提供了一个在迭代器前面添加一个元素的add()。
四。链表(List)
链表是一个有序集合,实现方式:
1.动态的ArrayList类,可以自由扩展容量,也可以在构造器指定容量,最大的缺点是删除或者添加需要付出很大代价。ArrayList类不是线程安全的,需要线程安全可以使用Vector类。
2.LinkedList<E>类,在JAVA里面,所有链表其实都是双向链表,在类中,提供了反向遍历链表的方法previous()和HasPrevious()。类中实现了一个方法listIterator()返回一个实现了ListIterator接口的迭代器对象。还有一个set(String)方法可以取代next()或者previous()返回的那一个元素。
2-1.在迭代器对链表进行遍历时,如果对這个链表申请了多个迭代器,当一个迭代器对链表进行了修改,那么调用其它迭代器时,会抛出一个Concurrent ModificcationException异常。
2-2.有一种快要简单的检测并发的方法:每个迭代器维护一个独立计数器,改变一次链表,计数+1,每次迭代器开始自己的方法之前将迭代器与集合计数对比,不匹配则抛出Concurrent ModificcationException异常
2-3.但是在对并发修改链表的检测中,set(String)方法并不会抛出异常。
2-4.LiskedList<E>类提供了一个随机访问方法get(),但是并不建议使用它,因为它的实现还是通过遍历实现访问。虽然经过优化:当索引大于size/2,从尾部开始遍历。
2-5.有整数索引n,listIterator(n)将返回一个指向索引为n的元素之前的迭代器。
五.散列表(哈希表,hashtable)
1.散列表依据散列码存放对象,散列表用链表数组实现,每个列表被称为桶(bucket)
2.每个桶中存放散列码相同的对象,由对象散列码除以桶数得到的余数就是存放该对象的桶号。如果這个桶满了,称为散列冲突。这时候要将该对象与桶中的对象对比,查看是否该对象是否在桶中。
3.当散列表太满了,会发生再散列,创建一个更大的散列表,再将所有元素插入到新表,再散列跟装填因子有关,比如装填因子是0.75,那么在表超过75%时发生再散列。在java se8中,当桶满时会把链表变为平衡二叉树。
4.在标准库中,桶的个数是2的幂,提供的任何大小都会变为2的下一个幂。
5.java集合类库提供了一个hashset,它是基于hashtable的无序无重复的集合,它的add()先检查集中是否有相同的元素。并且用迭代器对其访问的顺序也是随机的。
六。树集(treeset)
1.树集与散列集十分相似,但是它是一个有序集合,在将对象放入其中时,树集就会将其排序。它的排序是用树结构完成的(红黑树)。
2.但是在需要对一些特殊的对象排序比较中,需要提供一个comparator<>。当对数据存放不要求有序,就不必使用树集,没必要付出u排序的时间花销。u
3.树集实现了NavigableSet接口,增加了几个定位元素和反向遍历的方法。
七.映射(Map,数据结构)
Map,键值对(<k,v>) java类库提供了两个Map接口的通用实现:
1.HashMap:对键值对的键进行散列,、。
2.TreeMap:对键值对的键进行排序,类似树集,会对元素进行排序。
3.映射接口的方法中,get()用来检索对象,get()必须使用一个键->get(Key),但是当没有這个对象时,会返回null,可以使用getOrDefault(Key,Default)方法没有检索到对象时返回默认值。
4.最高效遍历映射的方法:
5.映射put()方法添加元素,在映射中,键是唯一的,当对一个键再次执行put()方法时,第二个value会取代前一个value,并且方法返回前一个value。
6.映射视图:java集合框架不认为映射是一个集合,不过可以得到其视图
7.弱散列映射:当程序中对映射中一个键的最后一个引用已经消亡,那么這个键对程序是无用的,然而java的回收机制并不会回收它,因为只要映射对象是活动的,那么整个映射所有桶也是活动的。有一个WeakHashMap类就是为此设计。
8.链接散列集和链接散列映射:LinkedHashSet,LinkedHashMap可以用来记住元素的插入顺序,在散列集与散列映射中,元素排列是无序的。链接散列集和链接散列映射是在散列集与散列映射的基础上实现为一个按照散列方式存放元素的双向链表,对其进行迭代是按照插入顺序遍历的。
9.LinkedHashSet,LinkedHashMap是由插入顺序进行迭代的,但是如果想按照访问顺序迭代,则可以创建LinkedHashMap<K,V>(initallapacity,loadFactor,true)。
10.标识散列映射:类identityHashMap有特殊作用,键的散列码不是用HashCode计算,而是用System.identityHashCode拉计算,這是Object.hashcode方法根据对象内存来计算散列码的方式,也就是内容相同,但是被认为是不同的对象,其中对象比较是用==,而不是equals。适用于对象遍历算法。
八:视图
通过视图可以获得其他实现了Collection和Map接口的对象,对原映射进行操作。
1.轻量级集合包装器:arrays.asList(Object array[])返回一个列表或者集合的视图,带有对底层数组的get和set方法,但是改变数组大小的任何方法都会抛出一个Unsupported OperationException异常。Collection.nCopies(n,anObject)返回一个实现了List接口的对象。
2.子视图:
List group=staff.subList(10,20)将得到一个列表的子视图,包括第一个参数,小于第二个参数,可以修改,删除视图的对象,并将反映到列表。集和映射也有相应的操作。
3.同步视图:集合必须保证线程安全,但是java类库并不实现线程安全的集合类,而是使用视图机制来保证线程安全。例如,Collections类的synchronizedMap静态方法 ,可以将任何一个映射表转换成具有线程安全的Map:Map<string,int>=Collections.synchronizedMap(new HahMap<string,int>())。
4.受查视图:用来对泛型类型发生问题是调试:List<string> checked=Collections.CheckedList(string,string.class)。