Java核心技术(第8版) – 读书笔记 – 第13章

1、JDK1最早的集合类:Vector、Stack、Hashtable、BitSet、Enumeration

2、JDK1.2后,设计了新的集合接口,并且接口和实现分离。接口如List、Map等
例如链表,可以用循环数组,也可以用传统链表实现:

3、此外还有以Abstract开头的抽象类,如AbstractList,在List基础上实现了基本的方法,如果要自定义新的实现,用它们会更容易。

4、Collection是所有集合对象的父接口,有先看两个方法:

第一个add就是向集合中添加元素,如果成功返回true。

第二个iterator用于迭代元素使用,返回的Iterator也是一个接口:

这个结构在Java中太常见了:
先调用hasNext方法,如果返回true,则表示有元素,访问next()获取下一个元素。否则表示没下一个元素了。
以ArrayList为例:

在JDK5之后,支持了foreach,因此有了更优雅的实现:由for循环隐式处理了iterator:

要注意的是:ArrayList等访问次序是固定的,而HashSet等访问次序是随机的,但一定能保证每个元素被访问到且只被访问到一次。

5、刚才的Iterator接口还有一个remove方法,显然是用于删除的:
在调用一次remove前,必须调用一次next() (才能定位到第一个元素啊,切记!)
因此如果连续删除两个remove(),必须
itr.remove();
itr.next();
itr.remove();
才可以!

6、Collection还有一些可能有用的方法:

7、前面说了,直接实现这些方法可能会很困难,好在我们有AbstractCollection,它已经帮助我们实现了很多无聊的方法。

8、除了以Map结尾的具体集合类来自接口Map,其他都源自于接口Collection。

9、常用的集合类:

ArrayList: 一种可以动态增长和缩减的索引序列(动态数组,类似于C++中的vector);

LinkedList: 一种可以在任何位置进行高效的插入和删除操作的有序序列(类似于C++中list);

ArrayDeque: 一种用循环数组实现的双端队列(类似于C++中的deque);

HashSet:一种没有重复元素的无序集合(C++的标准库中并未提供hashset集合,但是Windows的VC和Linux平台下的gcc均各自提供了hashset容器);

TreeSet: 一种有序集(类似于C++中的set);

EnumSet: 一种包含枚举类型值的集;

LinkedHashSet: 一种可以记住元素插入次序的集,在其内部由LinkedList负责维护插入的次序,HashSet来维护Hash;

PriorityQueue: 优先队列!

HashMap:一种存储键值对关联的数据结构(C++的标准库中并未提供hashmap集合,但是Windows的VC和Linux平台下的gcc均各自提供了hashmap容器);

TreeMap:一种键值有序排列的映射表(类似于C++中的map);

EnumMap:一种键值属于枚举类型的映射表;

LinkedHashMap:一种可以记住键值项插入次序的映射表;

WeakHashMap: 一种当key不被除了map之外的对象持有时,释放对应的key和value(被垃圾回收的Map)??

IdentityHashMap: 一种用==比较而不是用equals比较的HashMap

10、ArrayList相当于可变的数组,在中间插入、删除元素会耗费很大,此时可以用LinkedList实现。它使用纯双向链表结构,在任意位置插入、删除都是O(1)的。

11、ArrayList和LinkedList都继承自List接口。对于LinkedList来说,除了可以直接add添加到尾部之外,还可以调用它的listIterator以获取ListIterator,然后调用它的add()方法,插入到任意位置!

这个Iterator是ListIterator接口,除了add之外还有一对方法:
E previous() ;
boolean hasPrevious();
用于反向遍历链表。

例子:

ListIterator还支持set(E e),将e取代当前itr上的数值。

12、如果某个迭带器对集合进行了修改,另一个迭带器正在遍历,那么会抛出异常ConcurrentModificationException,这是很显然的。

13、链表是不支持随机访问的,即如果要访问第i个,那么要从链表头一直找到第i-1个,这是很低效率的。尽管如此,Java还是实现了LinkedList的get(int i)方法,使用时候要非常的谨慎!

14、链表迭带器ListIterator还可以返回当前、前一个、下一个的index数值:

int previousIndex()

int nextIndex()

下面这个例子将创建一个链表,然后再逐一打印、删除链表中的元素。

15、ArrayList的set和get提供高效的随机访问(都是O(1)),它的内部是一个可重新动态分配的数组。同时,在获取随机访问性能的同时,在任意位置的删除的代价会很昂贵。

16、散列表(Hash Table)用于在一个集合中快速的找到某个元素,Hash桶中的每个元素最多只能出现一次!

17、Java的散列表的散列值一般由类的hashCode()产生。如果要自定义类,就要负责这个类的hashCode()。同时hashCode()需要与equals()保持一致,如果equals返回true,则它们的HashCode必须一样!

18、Java的散列表是桶(Bucket)+数组(Array)实现的。
(1)公有N个桶,每个桶实际是一个链表(例如LinkedList)
(2)元素到来时,计算hashCode,用hashCode % N,即为这个元素应在的桶号
(3) 如果桶为空,直接放到链表中,如果不是空(此时称为冲突),要依次比较这个桶内的所有元素,确定没有重复的,再放入。

19、显然,桶的数量是固定的,当放入元素过多时,就会经常发生碰撞。因此,Java对哈希表引入了装填因子的概念:即桶数/元素数。默认为0.75,当装填因子大于它时(即元素过多),就会把桶数量×2,然后对已经有的元素重新做散列!

20、这个0.75是比较合理的,一般不要改变它。顺便说一句,Java的哈希表得益于散列表,性能是很好的。此外,初始桶的数量是2^4=16.

21、利用散列表的原理,Java提供了很多实现,如HashSet,用于快速检查元素是否存在于集合中。下面的例子,统计stdin输入了多少个不同的单词:

22、TreeSet比HashSet略有改进,它的元素之间是有大小序的(不是add的顺序)。因此它的插入比HashSet慢。可以直接用其他的Collection构造一个TreeSet:

23、TreeSet的大小比较按照Comparable<E>接口的compareTo进行。因此,放到TreeSet中的元素必须实现了Comparable接口。也可以通过Comparator接口实现:

24、从JDK6后,TreeSet额外实现了NavigableSet接口,更好的支持了反向遍历,比较等。

25、JDK6之后,引入了双端队列接口Deque,在头和尾插入、删除元素非常高效。ArrayDeque和LinkedList都实现了双端队列:

下面两个都是在队列尾部插入元素。区别是空间不够时,第一个抛出异常,第二个返回false。

下面两个方法都是从队列头部删除,同理,如果队列为空,第一个抛出异常,第二个返回null。

下面方法是返回队列头部元素,并不删除。当空时,也是第一个异常,第二个null。

26、对于ArrayDeque,是有容量限制的:

如果不指定,用默认构造函数,则容量为16。

27、PriorityQueue是优先级队列(继承自java.util.AbstractQueue类),内部用堆实现,也是通过Comparable接口比较大小。

下面的例子,从System.in中读取若干的树,放到优先队列中,最后输出排序的数组。比起传统的先收集、再排序方法,优点是可以边I/O边计算。

28、映射表(Map)的设计目标:根据一个key(如姓名),快速的找到value(如员工的详细信息)。Java提供了Map接口,两个常用的Map是HashMap和TreeMap。

Map的一个最主要方法是put:

同一个key只能有一个value,如果同一个key调用了两次put,第二次的会替换掉第一次的。

remove方法用于删除key以及对应的value:

remove返回的是被删除的key对应的value。

29、遍历Map中的所有key:

遍历所有的Value:

同时遍历key和value:

注意上面这个Set内部实际是Map.Entry,两个主要方法:

下面的例子添加、删除、替换、遍历Map:

30、弱引用的散列表:WeakHashMap,如果一个value对应的key已经没有其他引用了,WeakHashMap将负责销毁它。而其他的Map是不会自动销毁的(除非你自己去remove它)。他的内部使用了弱引用WeakReference。

31、链接散列表LinkedHashSet和LinkeHashMap,他们让集合内部保持插入的顺序(insert-mode)或者访问顺序(access-mode),这个在构造函数的第三个参数选项,默认是插入顺序。

32、按照访问顺序的模式可以实现LRU等:启用accessOrder后,每次get或者put的元素会被移到队列尾部。再配合initialCapacity和removeEldestEntry,就是一个LRU了。

33、EnumSet是枚举Enum集合的Set类,Set的T类型必须是enum。EnumMap的Key的T类型必须是enum,Value类型随意。

34、IdentityHashMap是特殊的Map,它的key散列值不是来自hashCode(),而是System.identityHashCode,方法是内存地址。因此在比较两个IdentityHashMap时,应当使用==而不是equals。

35、框架(Framework)包含了一系列可以完成高级功能的超类。Collection的基础方法:add(E elem),Map接口的基本方法:V put(K key, V value)和V get (K key)。

36、List接口在Collection的基础上额外添加了:add(index, elem)、E get(index)和void remove(index),主要是为了数组的随机访问操作。

37、为了防止使用LinkedList的随机访问操作带来的低效率,可以用RandomAccess接口进行instanceof判断:

ArrayList和Vector都实现了上述接口,而相反,LinkedList就没有实现RA接口。

38、ListIterator接口具有add方法,即在List只添加到尾部的add方法基础上,可以再任意可iter的位置上进行add。

39、Java中的具体类如HashMap等都是根据AbstractXXX抽象类实现的。具体集合接口和类结构见书592页。

40、JDK1还遗留了一些集合类:Vector、Stack、Hashtable、Properties。他们也被集成到了现有的集合类结构中。如Vector继承自AbstractList。

41、视图(views),如Map的keySet()方法,获得其他实现了集合接口和操作的对象。

42、java.util.Arrays/java.util.Collections提供了一系列static方法:

(1)将数组转化为List:

在JDK5之后,asList还可以接受可变参数:

(2)创建N个重复的实例:

43、子范围,其实Java也支持类似Python的slice,只不过需要调用函数:

对于SortedMap和SortedSet等,可以根据大小(equals)选择子集:

44、Collections还可以创建不可修改的视图(不可变的List、Map等):

传入一个List,返回一个不可变的List:

类似的还有Map、Set、SortedSet、SorteMap、Collection等。

45、多线程视图:如果多线程使用,可以用Collections包装成同步Map、List等:

如Map:

包装好后的Map在内部确保了外部多线程get和set没有问题。

类似的还可以包装List、Set等。

46、上述创建的这些视图,当发生无法完成的操作时,会抛出UnsupportedOperationException,如只读的,你却set了。

47、集合的交:可用retainsAll实现。

48、集合到数组的转换:用toArray:

49、集合的接口方式,可以方便的根据不同集合类型的特性,高效的实现各种算法如:ArrayList可以随机访问,而LinkedList就最好不要随机访问。

50、Collections.sort提供了排序算法,数之间的比较可以通过Comparable实现,也可以单独的Compator类来传入(反向排序也可以这么搞):

51、Java中排序算法是归并排序,缺点是反复拷贝可能略微耗空间、有点是排序是稳定的。

52、Collections.shuffle可以讲List中的元素随机化,原来不止是Python有。

下面的例子讲元素随机化再排序:

53、如果List是有序的,我们可以利用Collections.binarySearch(c, elem),这个要求实现了Comparable,也可以自己传入compartor。

注意,二分查找返回的是index,如果index<0,表示没有找到,但是可以用返回的负值计算如果插入这个e,应该插入的位置:

insertPos = -i – 1,还是比较先进的。。

54、Collections还提供了一些简单的算法:

Collections.min

Collections.max

Collections.copy(List to , List from)

Collections.fill(List l, T value)

Collections.replaceAll(List l, T old, T new) // 将list中所有的old替换为new

Collections.indexOfSubList(List l, List s)

Collections.swap(List l, int i, int j)  //交换

Collections.reverse(List l) // 翻转List

Collections.rotate(List l,  int d) //将i移动到 (i+d) % .lsize()

Collections.frequency(Collection c, Oject c) // 返回c中与o相同的对象数量

Collections.disjoint(Collection c1, Collection c2) // 如果两个集合完全没有交集,返回true

55、JDK1遗留了很多集合类:

Hashtable:和HashMap类一样,但它直接是线程安全的。

Vector:也是同步的,类似LinkedList

56、Eumeration也是遗留的类,对元素进行遍历。有时候JDK的其他类也用到了他们。主要是hasMoreElements和nextElement.

57、Properties:键、值表,实际上也可以用于配置文件!

Properties()

Properties(Properties default) // 提供属性的默认值

String getProterty(String key, String defaultVal) // 返回键对应的

void load(InputStream in)

void store(OutputStream out, String commentString)

58、Properties内部使用的是类似ini的格式。

59、JDK1提供的Stack完成的栈的功能,Stack。方法:

E push(E item)

E pop()

E peek() //返回栈顶但不弹出,空返null

60、Java也有BitSet类,get(i),set(i)、clear、xor等和C++的基本相同。

61 、据说用Java的BitSet类做筛法求素数,200万内,Java以105毫秒秒杀C++的360毫秒。

有时候不要对Java的速度有偏见,都到了JDK7的时代了,很多优化已经远领先于C++了。

本章完毕。

 

 

Leave a Reply

Your email address will not be published.