15.Java集合类

阅读量：5816 次

发布时间：2019-06-18

本文共 16203 字，大约阅读时间需要 54 分钟。

转载请保留原文链接:

15.Java集合类

Java集合类是java提供的工具包,包含了常用的数据结构:集合、链表、队列、栈、映射等.Java集合类主要可以划分为4个部分:List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections).

① 常用集合类接口

常用集合类继承关系如下所示:

Collection    |-List        |-LinkedList        |-ArrayList        |-Vector    |-Set    |-HashSet    |-QueueMap    |-Hashtable    |-HashMap

1.`Collection`接口

Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素(Elements).由Collection接口派生的两个接口是List和Set.List允许有相同元素, Set不允许有相同元素.

实现Collection接口的类都必须提供两个标准的构造函数:

无参数的构造函数用于创建一个空的Collection.

有一个参数的构造函数用于创建一个新的Collection对象,这个对象传入的Collection有相同的元素. 允许用户复制一个Collection.

2.`List`接口

List是有序的Collection. 使用此接口能够精确的控制每个元素插入的位置.能够使用索引(元素在List中的位置,类似于数组下标)来访问List中的元素,这类似于Java的数组.

除了具有Collection接口必备的iterator()方法外, List还提供一个listIterator()方法, 返回一个ListIterator接口,和标准的Iterator接口相比,ListIterator多了一些add()之类的方法,允许添加,删除,设定元素,还能向前或向后遍历.

实现List接口的常用类有LinkedList,ArrayList,Vector和Stack. 和Set不同, List允许有相同的元素.

3.`Set`接口

Set是一种不包含重复的元素的Collection,即任意的两个元素e1和e2都有e1.equals(e2)=false.

Set的构造函数有一个约束条件,传入的Collection参数不能包含重复的元素.Set最多有一个null元素.

必须小心操作可变对象(Mutable Object)

如果一个`Set`中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题.

4.`Queue`接口

可以实现先进先出的队列.LinkedList同样实现了Queue接口.PriorityQueue用来创建自然排序的优先级队列.

5.`Map`接口

Map提供key到value的映射. 一个Map中不能包含相同的key,每个key只能映射一个value.Map的内容可以被当作一组key集合,一组value集合,或者一组key-value映射.

`Map`没有继承`Collection`接口.

② 常用集合类

1.`LinkedList`类

LinkedList实现了List接口,允许null元素.提供额外的get,remove,insert方法在LinkedList的首部或尾部.这些操作使LinkedList可被用作栈(stack),队列(queue)或双向队列(deque).

`LinkedList`没有同步方法

如果多个线程同时访问一个List, 则必须自己实现访问同步.

一种解决方法是在创建List时构造一个同步的List:

List list = Collections.synchronizedList(new LinkedList(...));.

2.`ArrayList`类

ArrayList实现了变长数组.它允许所有元素,包括null.每个ArrayList实例都有一个容量(Capacity), 即用于存储元素的数组的大小.这个容量可随着不断添加新元素而自动增加,但是增长算法并没有定义.

当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率.

和LinkedList一样,ArrayList也是非同步的(unsynchronized).

ArrayList添加删除对象:

/** ArrayList添加对象*/ArrayList
     
       intList = new ArrayList<>();System.out.println("ArrayList 长度: " + intList.size());for (int i = 0; i < 10; i++) {    intList.add(i);}System.out.println("ArrayList 长度: " + intList.size());/** ArrayList删除对象*/intList.remove(5);System.out.println("ArrayList 长度: " + intList.size());

ArrayList遍历:

ArrayList 遍历方式 1 增强for循环, 获得值, 无法获得索引

for (Integer intNum : arrayList) {    System.out.println(intNum);}

ArrayList 遍历方式 2普通for循环, 索引和值都能获得

for (int i = 0; i < arrayList.size(); i++) {    int num = arrayList.get(i);    System.out.println(num);}

ArrayList 遍历方式 3 迭代器 Itertor, 无法获得索引

Iterator
     
       it = arrayList.iterator();while (it.hasNext()) {    int num = it.next();    System.out.println(num);}

3.`Vector`类

Vector非常类似ArrayList,但Vector是线程同步的.

由Vector创建的Iterator,虽然和ArrayList创建的Iterator是同一接口,但由于Vector是线程同步的,当一个Iterator被创建而且正在被使用,另一个线程改变了Vector的状态(例如,添加或删除了一些元素),这时调用Iterator的方法时将抛出ConcurrentModificationException,因此必须捕获该异常.

代码示例:

/** Vector*/Vector
     
       vector = new Vector<>();System.out.println("Vector 长度: " + vector.size());for (int i = 0; i < 5; i++) {    vector.add(i);}System.out.println("Vector 长度: " + vector.size());/** Vectort 删除对象*/vector.remove(3);System.out.println("Vector 长度: " + vector.size());/** Vectort 遍历方式 1 增强for循环*/for (Integer intNum : vector) {    System.out.println(intNum);}

Vector添加删除对象和遍历方式和ArrayList类似, 参考ArrayList的代码实现.

4.`Stack`类

Stack继承自Vector,实现一个后进先出的堆栈. stack的常用方法:

push: 放入栈

pop: 出栈

peek:得到栈顶的元素

empty:测试堆栈是否为空

search:检测一个元素在堆栈中的位置

代码示例:

/** Stack*/Stack
     
       stack = new Stack<>();System.out.println("Stack 长度: " + stack.size());for (int i = 0; i < 5; i++) {    /** 入栈*/    stack.push(i);}System.out.println("Stack 长度: " + stack.size());/** Stack pop 出栈*/stack.pop();System.out.println("Stack 长度: " + stack.size());/** Stack peek 得到栈顶的元素*/int peekNum = stack.peek();System.out.println("Stack peekNum: " + peekNum);/** Stack search 检测一个元素在堆栈中的位置*/int pos = stack.search(3);System.out.println("Stack search pos: " + pos);/** Stack 遍历方式 1 增强for循环*/for (Integer anIntList : stack) {    int num = anIntList;    System.out.println(num);}

`Stack`遍历方式和`ArrayList`类似, 参考`ArrayList`的代码实现.

5.HashMap类

HashMap是最常用的Map,不是线程安全的.它根据键的HashCode值存储数据,根据键可以直接获取它的值,具有很快的访问速度.遍历时,取得数据的顺序是完全随机的.

由于键对象不可以重复, 所以HashMap最多只允许一条记录的键为空(null),允许多条记录的值为空(null).

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置, 因此任何作为key的对象都必须实现hashCode和equals方法.

`hashCode`和`equals`方法继承自根类`Object`.

用自定义的类当作key

按照`散列函数`的定义,如果两个对象相同,即`obj1.equals(obj2)=true`,则它们的`hashCode`必须相同,但如果两个对象不同,则它们的`hashCode``不一定不同`.

如果两个不同对象的hashCode相同,这种现象称为`冲突`. 冲突会导致操作哈希表的时间开销增大.

所以尽量定义好的`hashCode()`方法,能加快哈希表的操作.如果相同的对象有不同的`hashCode`,对哈希表的操作会出现意想不到的结果(`期待的get方法返回null`).

要避免这种问题,只需要牢记一条:要同时覆写`equals`方法和`hashCode`方法, 而不要只写其中一个.

代码示例: HashMap添加和删除对象:

HashMap
     
       hashMap = new HashMap<>();System.out.println("HashMap 长度: " + hashMap.size());for (int i = 0; i < 5; i++) {    /** HashMap 添加对象*/    hashMap.put(i, 100 + i);}System.out.println("HashMap 长度: " + hashMap.size());/** HashMap 删除对象*/hashMap.remove(2);System.out.println("HashMap 长度: " + hashMap.size());

HashMap遍历:

HashMap 遍历方式 1 增强for循环遍历 Entry

6.`Hashtable`类

Hashtable继承Map接口,实现一个key-value映射的哈希表. 任何非空(non-null)的对象都可作为key或者value.

Hashtable与HashMap类似,是HashMap的线程安全版,是线程同步的,即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢. 它继承自Dictionary类,不同的是它不允许记录的键或者值为null,同时效率较低.

建议使用ConcurrentHashMap替代

如果需要线程同步的map, 建议使用线程同步的ConcurrentHashMap类. 不建议使用这个类, 并没有示例代码.

7.`WeakHashMap`类

WeakHashMap是一种改进的HashMap. 它对key实行弱引用,如果一个key不再被外部所引用,那么该key可以被Java的垃圾回收器(GC)回收.

使用方式同`HashMap`.

8. `HashSet`类

HashSet中元素是无序的(这个无序指的是数据的添加顺序和后来的排列顺序不同),而且元素不可重复.

HashSet的底层是数组,在增加和删除的时候由于运用的hashCode的比较来确定添加元素的位置,不存在元素的偏移, 因此查询和删除和增加元素的效率都非常高.

但是HashSet增删的高效率是通过花费大量的空间换来的, 因为空间越大,取余数相同的情况就越小.HashSet这种算法会建立许多无用的空间.

使用HashSet类时如果发生冲突,就会出现遍历整个数组的情况,这样就使得效率非常的低.

/** 循环两次，放入重复的1-5*/for (int i = 0; i < 5; i++) {    hashSet.add(i);}for (int i = 0; i < 5; i++) {    hashSet.add(i);}System.out.println("HashSet 长度: " + hashSet.size());/** HashSet 遍历方式 1 增强for循环*/for (Integer intNum : hashSet) {    System.out.println(intNum);}

由于HashSet去重功能, 第二次循环插入重复数据时, HashSet中并没有加入新的数据, 长度依然是5. HashSet的遍历方式同ArrayList，参考ArrayList的遍历.

9.`ConcurrentHashMap`类

线程同步的HashMap,线程安全并且锁分离. ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分,每个段其实就是一个小的hash table,它们有自己的锁. 只要多个修改操作发生在不同的段上,它们就可以并发进行.

使用方式同`HashMap`.

10.`LinkedHashMap`类

有序的HashMap, 非线程安全. LinkedHashMap保存了记录的插入顺序,在用Iteraor遍历LinkedHashMap时,先得到的记录肯定是先插入的,在遍历的时候会比HashMap慢,有HashMap的全部特性.

使用方式同`HashMap`.

11.`TreeMap`类

TreeMap实现SortMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序(自然顺序),也可以指定排序的比较器. 当用Iterator遍历TreeMap时, 得到的记录是排过序的.

TreeMap不允许key值为空,非线程同步.

使用方式同`HashMap`.

11.总结

如果涉及到堆栈,队列等操作,应该考虑用List. 对于需要快速插入,删除元素,应该使用LinkedList, 如果需要快速随机访问元素,应该使用ArrayList.

如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高.

如果多个线程可能同时操作一个类,应该使用同步的类.

要特别注意对哈希表的操作,作为key的对象要正确覆写equals和hashCode方法.

尽量返回接口而非实际的类型, 如返回List而非ArrayList, 这样如果以后需要将ArrayList换成LinkedList时, 代码接口不用改变.扩展性强.

③ 常用遍历集合方式

1. 迭代器`Iterator`

不论Collection的实际类型如何,它都支持一个iterator()的方法,该方法返回一个迭代器,使用该迭代器即可逐一访问Collection中每一个元素.典型的用法如下:

// 获得一个迭代器Iterator it = collection.iterator();while(it.hasNext()) {    //获取下一个元素    Object obj = it.next();}

2. foreach

增强for循环, JDK1.5之后提供的新功能, 可以输出数组或集合.

3. for循环

普通for循环遍历

示例代码:

package com.dashidan.lesson13;import java.util.*;/** * 大屎蛋教程网-dashidan.com *  * Java教程基础篇: 13.Java集合类 */public class Demo1 {    public static void main(String[] args) {        testArrayList();        testVector();        testStack();        testHashMap();        testHashSet();    }    /**     * ArrayList基本操作     */    public static void testArrayList() {        System.out.println("---ArrayList---");        /** ArrayList添加对象*/        ArrayList
      
        arrayList = new ArrayList<>();        System.out.println("ArrayList 长度: " + arrayList.size());        for (int i = 0; i < 5; i++) {            arrayList.add(i);        }        System.out.println("ArrayList 长度: " + arrayList.size());        /** ArrayList删除对象*/        arrayList.remove(3);        System.out.println("ArrayList 长度: " + arrayList.size());        /** ArrayList 遍历方式 1 增强for循环, 获得值, 无法获得索引*/        for (Integer intNum : arrayList) {            System.out.println(intNum);        }        /** ArrayList 遍历方式 2普通for循环, 值和索引都能得到*/        for (int i = 0; i < arrayList.size(); i++) {            int num = arrayList.get(i);            System.out.println(num);        }        /** ArrayList 遍历方式 3 迭代器 Itertor, 获得值, 无法获得索引*/        Iterator
       
         it = arrayList.iterator();        while (it.hasNext()) {            int num = it.next();            System.out.println(num);        }    }    /**     * Vector基本操作     */    public static void testVector() {        System.out.println("---Vector---");        /** Vector*/        Vector
        
          vector = new Vector<>();        System.out.println("Vector 长度: " + vector.size());        for (int i = 0; i < 5; i++) {            vector.add(i);        }        System.out.println("Vector 长度: " + vector.size());        /** Vectort 删除对象*/        vector.remove(3);        System.out.println("Vector 长度: " + vector.size());        /** Vectort 遍历方式 1 增强for循环, 获得值, 无法获得索引*/        for (Integer intNum : vector) {            System.out.println(intNum);        }        /** Vectort 遍历方式 2普通for循环, 值和索引都能得到*/        for (int i = 0; i < vector.size(); i++) {            int num = vector.get(i);            System.out.println(num);        }        /** Vectort 遍历方式 3 迭代器 Itertor, 获得值, 无法获得索引*/        Iterator
         
           it = vector.iterator();        while (it.hasNext()) {            int num = it.next();            System.out.println(num);        }    }    /**     * Stack基本操作     */    public static void testStack() {        System.out.println("---Stack---");        /** Stack*/        Stack
          
            stack = new Stack<>();        System.out.println("Stack 长度: " + stack.size());        for (int i = 0; i < 5; i++) {            /** 入栈*/            stack.push(i);        }        System.out.println("Stack 长度: " + stack.size());        /** Stack pop 出栈*/        stack.pop();        System.out.println("Stack 长度: " + stack.size());        /** Stack peek 得到栈顶的元素*/        int peekNum = stack.peek();        System.out.println("Stack peekNum: " + peekNum);        /** Stack search 检测一个元素在堆栈中的位置*/        int pos = stack.search(3);        System.out.println("Stack search pos: " + pos);        /** Stack 遍历方式 1 增强for循环*/        for (Integer intNum : stack) {            System.out.println(intNum);        }    }    /**     * HashMap基本操作     */    public static void testHashMap() {        System.out.println("---HashMap---");        HashMap
           
             hashMap = new HashMap<>();        System.out.println("HashMap 长度: " + hashMap.size());        for (int i = 0; i < 5; i++) {            /** HashMap 添加对象*/            hashMap.put(i, 100 + i);        }        System.out.println("HashMap 长度: " + hashMap.size());        /** HashMap 删除对象*/        hashMap.remove(2);        System.out.println("HashMap 长度: " + hashMap.size());        /** HashMap 遍历方式 1 增强for循环遍历 Entry */        System.out.println("HashMap 遍历方式 1 增强for循环遍历 Entry ");        for (Map.Entry
            
              entry : hashMap.entrySet()) {            System.out.println("hashMap key: " + entry.getKey() + " hashMap value: " + entry.getValue());        }        /** HashMap 遍历方式 2 通过迭代器遍历 key */        System.out.println("HashMap 遍历方式 2 通过迭代器遍历 key *");        Iterator
             
               it0 = hashMap.keySet().iterator();        while (it0.hasNext()) {            int key = it0.next();            int value = hashMap.get(key);            System.out.println("key: " + key + " value: " + value);        }        /** HashMap 遍历方式 3 通过 增强for循环遍历 key*/        System.out.println("HashMap 遍历方式 3 通过 增强for循环遍历 key");        for (Integer key : hashMap.keySet()) {            int value = hashMap.get(key);            System.out.println("key: " + key + " value: " + value);        }        /** HashMap 遍历方式 4 通过迭代器遍历 values, 无法得到 key值 */        System.out.println("HashMap 遍历方式 4 通过迭代器遍历 values, 无法得到 key值 ");        Iterator
              
                it1 = hashMap.values().iterator();        while (it1.hasNext()) {            int value = it1.next();            System.out.println("value: " + value);        }        /** HashMap 遍历方式 5 通过 增强for循环遍历 values, 无法得到 key值 */        System.out.println("HashMap 遍历方式 5 通过 增强for循环遍历 values, 无法得到 key值 ");        for (Integer value : hashMap.values()) {            System.out.println("value: " + value);        }    }    /**     * HashSet基本操作     */    public static void testHashSet() {        System.out.println("---HashSet---");        HashSet
               
                 hashSet = new HashSet<>();        System.out.println("HashSet 长度: " + hashSet.size());        /** 循环两次，放入重复的1-5*/        for (int i = 0; i < 5; i++) {            hashSet.add(i);        }        for (int i = 0; i < 5; i++) {            hashSet.add(i);        }        System.out.println("HashSet 长度: " + hashSet.size());        /** HashSet 遍历方式 1 增强for循环*/        for (Integer intNum : hashSet) {            System.out.println(intNum);        }    }}

输出:

---ArrayList---ArrayList 长度: 0ArrayList 长度: 5ArrayList 长度: 4012401240124---Vector---Vector 长度: 0Vector 长度: 5Vector 长度: 4012401240124---Stack---Stack 长度: 0Stack 长度: 5Stack 长度: 4Stack peekNum: 3Stack search pos: 10123---HashMap---HashMap 长度: 0HashMap 长度: 5HashMap 长度: 4HashMap 遍历方式 1 增强for循环遍历 EntryhashMap key: 0 hashMap value: 100hashMap key: 1 hashMap value: 101hashMap key: 3 hashMap value: 103hashMap key: 4 hashMap value: 104HashMap 遍历方式 2 通过迭代器遍历 key *key: 0 value: 100key: 1 value: 101key: 3 value: 103key: 4 value: 104HashMap 遍历方式 3 通过 增强for循环遍历 keykey: 0 value: 100key: 1 value: 101key: 3 value: 103key: 4 value: 104HashMap 遍历方式 4 通过迭代器遍历 values, 无法得到 key值value: 100value: 101value: 103value: 104HashMap 遍历方式 5 通过 增强for循环遍历 values, 无法得到 key值value: 100value: 101value: 103value: 104---HashSet---HashSet 长度: 0HashSet 长度: 501234

④ FAQ

集合类相关常见问题

1.集合类和数组的区别

数组(可以存储基本数据类型)是用来存现对象的一种容器, 数组的长度固定, 适合在对象数量固定时使用.

集合(只能存储对象,对象类型可以不一样)的长度可变,可在对象数量不固定时使用.

2.`ArrayList`和`LinkedList`区别

ArrayList和LinkedList在用法上没有区别,但是在功能上还是有区别的. LinkedList经常用在增删操作较多而查询操作很少的情况下, 比如队列和堆栈. ArrayList则相反.

ArrayList底层是Object数组,所以ArrayList具有数组的查询速度快的优点以及增删速度慢的缺点. 而在LinkedList的底层是一种双向循环链表.在此链表上每一个数据节点都由三部分组成:前指针(指向前面的节点的位置),数据,后指针(指向后面的节点的位置).最后一个节点的后指针指向第一个节点的前指针,形成一个循环.双向循环链表的查询效率低但是增删效率高.

对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针.

对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据.

ArrayList和LinkedList应用场景

若只对单条数据插入或删除,ArrayList的速度优于LinkedList. 但若是批量随机的插入删除数据,LinkedList的速度大大优于ArrayList. 因为ArrayList每插入一条数据,要移动插入点及之后的所有数据.

队列和栈

队列:先进先出的数据结构.

栈:后进先出的数据结构.

使用栈的时候, 不能提供非末尾元素出栈的方法.

3.`HashTable`与`HashMap`区别

Hashtable是基于陈旧的Dictionary类的, HashMap是Java 1.2引入的Map接口的一个实现

Hashtable是线程安全的,也就是说是同步的, 而HashMap是线程序不安全的,不是同步的

HashMap·允许存在一个为空(null)的key,多个为空(null)的value`.

Hashtable的key和value都不允许为空(null).

4.`ArrayList`和`Vector`区别

Vector是线程同步的,所以它也是线程安全的. 而Arraylist不是线程同步的. 如果不考虑到线程的安全因素,一般用Arraylist效率比较高.

如果集合中的元素的数目大于目前集合数组的长度时, Vector增长率为目前数组长度的100%, 而Arraylist增长率为目前数组长度的50%. 在集合中使用数据量比较大的数据,用Vector有一定的优势.

如果查找一个指定位置的数据, Vector和Arraylist使用的时间是相同的,都是O(1), 这个时候使用Vector和Arraylist都可以.

5.`ArrayList`和`Linklist`区别

ArrayList和Vector是采用数组方式存储数据, 此数组元素数大于实际存储的数据以便增加和插入元素, 都允许直接序号索引元素, 但是插入数据要设计到数组元素移动等内存操作, 所以索引数据快插入数据慢. Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差.