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

Leave a reply

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

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

List<String> lst = new ArrayList<String>();
List<String> lst = new LinkedList<String>();

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

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

public Interface Collection<E>
{
    boolean add(E element);
    Iterator<E> iterator();
}

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

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

public Interface Iterator<E>
{
    E next();
    boolean hasNext();
    void remove();
}

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

import java.util.*;

public class AA
{
    public static void main(String [] args)
    {
        ArrayList<String> lst = new ArrayList<String>();
        lst.add("1");
        lst.add("2");
        lst.add("3");
        Iterator<String> itr = lst.iterator();
        while(itr.hasNext())
        {
            System.out.println(itr.next());
        }
    }
}

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

ArrayList<String> lst = new ArrayList<String>();
lst.add("1");
lst.add("2");
lst.add("3");
for(String e: lst)
{
    System.out.println(e);
}

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

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

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

public Interface Collection
{
    //判断是否含元素？
    boolean contains(Object o);
    //集合是否为空
    boolean isEmpty();
    // 是否等于另外一个集合
    boolean equals(Object o);
    // 删除所有与集合c中不同的元素，如果集合有改变，返回true
    boolean retainAll(Collection<?> c)
    //转化为数组
    <T> T[] toArray(T[] a);
    ......
}

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();
用于反向遍历链表。

例子：

        List<String> lst = new LinkedList<String>();
        lst.add("1");
        lst.add("2");
        lst.add("3");
        ListIterator<String> itr = lst.listIterator(1);
        itr.add("100");
        for(String e: lst)
        {
            System.out.println(e);
        }

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

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

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

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

int previousIndex()

和

int nextIndex()

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

import java.util.*;

public class LL
{
    public static void main(String [] args)
    {
        List<String> lst = new LinkedList<String>();
        lst.add("1");
        lst.add("2");
        lst.add("3");
        ListIterator<String> itr = lst.listIterator();
        while(itr.hasNext())
        {
            System.out.println("current value:"+itr.next());
            itr.remove();
        }
        System.out.println(lst.size());
    }
}

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输入了多少个不同的单词：

import java.util.*;

public class WordCount
{
    public static void main(String [] args)
    {
        Set<String> words_set = new HashSet<String>();
        // Input from System.in, read al words
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext())
        {
            // Unique words using HashSet
            String word = scan.next();
            words_set.add(word);
        }
        // Print all words and total number of words
        for(String word: words_set)
        {
            System.out.print(word);
            System.out.print(" ");
        }
        System.out.println();
        System.out.println(words_set.size());
    }
}

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

public TreeSet(Collection<? extends E> c)

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

public Interface Comparator<T>
{
    int compare(T o1, T o2);
}

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

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

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

boolean add(E element)
boolean offer(E element)

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

E remove()
E pool()

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

E element()
E peek()

26、对于ArrayDeque，是有容量限制的：

public ArrayDeque(int numElements)

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

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

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

import java.util.*;
public class PriorityQueueTest
{
    public static void main(String [] args)
    {
        //Input and put into PriorityQueue
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextInt())
        {
            pq.add(scan.nextInt());
        }
        //Output
        System.out.println("Result:");
        for(Integer e: pq)
        {
            System.out.println(e);
        }
    }
}

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

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

public Interface Map
{
    V put(K key, V value);
}

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

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

public InterfaceMap<K, V>
{
    V remove(Object key);
}

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

29、遍历Map中的所有key：

Set<K> keySet()

遍历所有的Value：

Collection<V> values()

同时遍历key和value：

Set<Map.Entry<K,V>> entrySet()

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

K getKey()
//和
V getValue()

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

import java.util.*;

public class MapTest
{
    public static void main(String [] args)
    {
        // Put into map
        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("li", 1);
        map.put("liu", 2);
        map.put("wang", 3);
        // Remove
        map.remove("wang");
        // Replace
        map.put("li", 10);
        // Iterator
        for(Map.Entry<String, Integer> entry: map.entrySet())
        {
            System.out.print(entry.getKey());
            System.out.print(":");
            System.out.println(entry.getValue());
        }
    }
}

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

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

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);

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判断：

if (c instanceof RandomAcces)
{
    //use random access
}
else
{
    //don't use random access, may be very slow
}

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：

Card [] cards = new Card[50];
List<Card> cardList = Arrays.asList(cards);

在JDK5之后，asList还可以接受可变参数：

List<String> cardList = Arrays.asList("Li", "Ao", "an");

（2）创建N个重复的实例：

List<String> lst = Collections.nCopies(100, "STRING");

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

public Interface List
{
    List<E> 	subList(int fromIndex, int toIndex);
}

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

public class SortedSet
{
    SortedSet<E> subSet(E fromElement, E toElement);
}

44、Collections还可以创建不可修改的视图（不可变的List、Map等）：

传入一个List，返回一个不可变的List：

public Class Collections
{
    public static <T> List<T> unmodifiableList(List<? extends T> list);
}

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

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

如Map：

public Class Collections
{
    public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
}

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

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

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

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

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

Object[] toArray();

<T> T[] toArray(T[] a);

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

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

public class Collections
{
    //要求元素实现了Comparable接口
    public static <T extends Comparable<? super T>> void sort(List<T> list);
    //也可以单独传入比较器Comparator
    public static <T> void sort(List<T> list, Comparator<? super T> c);
}

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

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

class Collections
{
    public static void shuffle(List<?> list);
}

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

import java.util.*;
public class SortTest
{
    public static void main(String [] args)
    {
        // Add
        List<Integer> lst = new ArrayList<Integer>();
        for(int i=0; i< 20; i++)
        {
            lst.add(i);
        }
        // Random and print
        Collections.shuffle(lst);
        for(Integer e: lst)
        {
            System.out.print(e);
            System.out.print(" ");
        }
        System.out.println();
        // Sort and Pring
        Collections.sort(lst);
        for(Integer e: lst)
        {
            System.out.print(e);
            System.out.print(" ");
        }
        System.out.println();
    }
};

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

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

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

// Collections
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key);

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++了。

本章完毕。

 

 

您可能也喜欢如下文章:

  1. Java核心技术(第8版) - 读书笔记 - 第3章
  2. Java核心技术(第8版) – 读书笔记 – 第12章
  3. Java核心技术(第8版) – 读书笔记 – 第5章
  4. Java核心技术(第8版) – 读书笔记 – 第6章
  5. Java核心技术(第8版) – 读书笔记 – 第10章

Leave a Reply

Your email address will not be published. Required fields are marked *