0%

Java中的Map List Set等集合类

一、概述

  在JAVA的util包中有两个所有集合的父接口Collection和Map,它们的父子关系:

+Collection (接口 这个接口extends自Iterable接口)
 ├+List (接口 代表有序,可重复的集合。列表)
 │├ ArreyList            (Class 数组,随机访问,没有同步,线程不安全)
 │├ Vector               (Class  数组                   同步        线程全)
 │├ LinkedList           (Class  链表   插入删除   没有同步   线程不安全)
 │└ Stack                (Class)
 └+Set(接口 不能含重复的元素。仅接收一次并做内部排序,集)
  ├ HashSet              (Class)
  ├ LinkedHashSet        (Class)
  └ TreeSet              (Class)

+Map (接口)
 └+Map(接口 映射集合)
  ├ HashMap             (Class 不同步,线程不安全。除了不同和允许使用null 键值之外,与Hashtable大致相同)
  ├ Hashtable           (Class 同步   ,线程安全    。不允许实施null 键值)
  ├ +SortedMap 接口
  │   ├ TreeMap         (Class)
  └ WeakHashMap         (Class)

  集合框架图: 集合框架图

  以下对众多接口和类的简单说明:首先不能不先说一下数组(Array)

1、效率高,但容量固定且无法动态改变。array还有一个缺点是,无法判断其中实际存有多少元素,length只是告诉我们array的容量。
2、Java中有一个Arrays类,专门用来操作array。
      arrays中拥有一组static函数,
      equals():比较两个array是否相等。array拥有相同元素个数,且所有对应元素两两相等。
      fill():将值填入array中。
      sort():用来对array进行排序。
      binarySearch():在排好序的array中寻找元素。
      System.arraycopy():array的复制。

二、数组和集合的区别:

  1. 数组是大小固定的,并且同一个数组只能存放类型一样的数据(基本类型/引用类型)
  2. JAVA集合可以存储和操作数目不固定的一组数据。
  3. 若程序时不知道究竟需要多少对象,需要在空间不足时自动扩增容量,则需要使用容器类库,array不适用。

三、Set/Map/List的区别

  首先,都是集合接口

Set     其中的值不允许重复,无序的数据结构 
List    其中的值允许重复,因为其为有序的数据结构 
Map     成对的数据结构,健值必须具有唯一性(键不能同,否则值替换) 

List

  按对象进入的顺序保存对象,不做排序或编辑操作。

Set

  对每个对象只接受一次,并使用自己内部的排序方法(通常,你只关心某个元素是否属于Set,而不关心它的顺序--否则应该使用List)。

Map

  同样对每个元素保存一份,但这是基于"键"的,Map也有内置的排序,因而不关心元素添加的顺序。如果添加元素的顺序对你很重要,应该使用 LinkedHashSet或者LinkedHashMap.

HashTable 和 HashMap 是 Map 的实现类 
HashTable 是线程安全的,不能存储 null 值
HashMap 不是线程安全的,可以存储 null 值

四、 List接口:有序可重复的集合

  实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素,另一种是更强大的LinkedList,它并不是为快速随机访问设计的,而是具有一套更通用的方法。

  List : 次序是List最重要的特点:它保证维护元素特定的顺序。List为Collection添加了许多方法,使得能够向List中间插入与移除元素(这只推荐LinkedList使用。)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。

1. ArrayList

  1. ArrayList实现了可变大小的数组。它允许所有元素,包括null。ArrayList没有同步。
  2. size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
  3. 每个ArrayList实例都有一个容量(Capacity),即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加,但是增长算法 并没有定义。当需要插入大量元素时,在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
  4. 和LinkedList一样,ArrayList也是非同步的(unsynchronized)。
  5. 由数组实现的List。允许对元素进行快速随机访问,但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。

2. Vector

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

3. LinkedList

  LinkedList实现了List接口,允许null元素。此外LinkedList提供额外的get,remove,insert方法在 LinkedList的首部或尾部。如下列方法:addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。

  注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:

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

4. Stack

  Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

用法:

package Test;  
  
import java.util.ArrayList;  
import java.util.Iterator;  
import java.util.List;  
public class TestList {  
    public static void main(String dd[]) {  
        // new了一个存储list  
        List l = new ArrayList();  
        // 因为Collection framework只能存储对象所以new封装类  
        l.add(new Integer(1));  
        l.add(new Integer(2));  
        l.add(new Integer(3));  
        l.add(new Integer(4));  
  
        Iterator it = l.iterator();  
        //使用 迭代器(Iterator):  
        // hasNext是取值取的是当前值.他的运算过程是判断下个是否有值如果有继续.  
        while (it.hasNext()) {  
            System.out.println("iterator:Element in list is :   " + it.next());  
        }  
        //用for循环和get()方法:  
        for (int i = 0; i < l.size(); i++) {  
            System.out.println("for:Element in list is :   " + l.get(i));  
        }  
    }  
}  

LinkedList:

package Test;  
  
import java.util.Iterator;  
import java.util.LinkedList;  
  
public class TestLinkedList {  
    public static void main(String arg[]) {  
        LinkedList ll = new LinkedList();// 声明LinkedList并实例化  
        // 使用add()方法添加元素  
        ll.add("a");  
        ll.add("b");  
        ll.add("c");  
        // 使用Iterator迭代器遍历出集合的元素并打印  
        Iterator it = ll.iterator();  
        while (it.hasNext()) {  
            System.out.println(it.next());  
        }  
        System.out.println("------------------");  
        // 向链表头和尾分别添加x和z  
        ll.addFirst("z");  
        ll.addLast("x");  
        // 遍历查看添加后的结果  
        for (Iterator i = ll.iterator(); i.hasNext();) {  
            System.out.println(i.next());  
        }  
    }  
}  

ArrayList和LinkedList的区别。

  1. ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
  2. 对于随机访问get和set,ArrayList觉得优于LinkedList,因为LinkedList要移动指针。
  3. 对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。

如果熟悉数据结构的同学,就会一下明白,ArrayList就是线性表的顺序表示,LinkedList就是线性表的链表表示。

五、 Set接口:代表无序,不可重复的集合

  Set具有与Collection完全一样的接口,因此没有任何额外的功能,不像前面有两个不同的List。实际上Set就是Collection,只是行为不同。(这是继承与多态思想的典型应用:表现不同的行为。)Set不保存重复的元素(至于如何判断元素相同则较为负责)

  Set : 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。

1. HashSet

  为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。

2. TreeSet

  保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。

3. LinkedHashSet

  具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。

用法:

Set set=new HashSet();  
    String s1=new String("hello");  
    String s2=s1;  
    String s3=new String("world");  
    set.add(s1);  
    set.add(s2);  
    set.add(s3);  
    System.out.println(set.size());//打印集合中对象的数目 为 2。  
    Set 的 add()方法是如何判断对象是否已经存放在集合中?  
    boolean isExists=false;  
    Iterator iterator=set.iterator();  
    while(it.hasNext())  {  
        String oldStr=it.next();  
        if(newStr.equals(oldStr)){  
           isExists=true;  
        }  
    }  

六、 Map接口:映射

  Map没有继承Collection接口, Map 提供 key 到 value 的映射,你可以通过“键”查找“值”。一个 Map 中不能包含相同的 key ,每个 key 只能映射一个 value 。 Map 接口提供3种集合的视图, Map 的内容可以被当作一组 key 集合,一组 value 集合,或者一组 key-value 映射。

  方法 put(Object key, Object value) 添加一个“值” ( 想要得东西 ) 和与“值”相关联的“键” (key) ( 使用它来查找 ) 。方法get(Object key) 返回与给定“键”相关联的“值”。可以用 containsKey() 和 containsValue() 测试 Map 中是否包含某个“键”或“值”。 标准的 Java 类库中包含了几种不同的 Map : HashMap, TreeMap, LinkedHashMap, WeakHashMap, IdentityHashMap 。它们都有同样的基本接口 Map ,但是行为、效率、排序策略、保存对象的生命周期和判定“键”等价的策略等各不相同。

  Map 同样对每个元素保存一份,但这是基于"键"的, Map 也有内置的排序,因而不关心元素添加的顺序。如果添加元素的顺序对你很重要,应该使用 LinkedHashSet 或者 LinkedHashMap.

  执行效率是 Map 的一个大问题。看看 get() 要做哪些事,就会明白为什么在 ArrayList 中搜索“键”是相当慢的。而这正是 HashMap 提高速度的地方。 HashMap 使用了特殊的值,称为“散列码” (hash code) ,来取代对键的缓慢搜索。“散列码”是“相对唯一”用以代表对象的int值,它是通过将该对象的某些信息进行转换而生成的(在下面总结二:需要的注意的地方有更进一步探讨)。所有 Java 对象都能产生散列码,因为 hashCode() 是定义在基类 Object 中的方法 。 HashMap 就是使用对象的 hashCode() 进行快速查询的。此方法能够显著提高性能。

1.Hashtable

  Hashtable继承Map接口,实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。Hashtable是同步的。添加数据使用 put(key, value) ,取出数据使用get(key),这两个基本操作的时间开销为常数。

  Hashtable 通过初始化容量 (initial capacity) 和负载因子 (load factor) 两个参数调整性能。通常缺省的 load factor0.75 较好地实现了时间和空间的均衡。增大 load factor 可以节省空间但相应的查找时间将增大,这会影响像 get 和 put 这样的操作。

使用 Hashtable 的简单示例如下,将 1,2,3 放到 Hashtable 中,他们的 key 分别是 ”one” , ”two” , ”three” :

Hashtable numbers =new Hashtable();
numbers.put("one", new Integer(1));
numbers.put("two", new Integer(2));
numbers.put("three", new Integer(3));

要取出一个数,比如 2 ,用相应的 key :

Integer n = (Integer)numbers.get("two");
System.out.println("two=" + n);

   由于作为 key 的对象将通过计算其散列函数来确定与之对应的 value 的位置,因此任何作为 key 的对象都必须实现 hashCode 方法和 equals 方法。 hashCode 方法和 equals 方法继承自根类 Object ,如果你用自定义的类当作 key 的话,要相当小心,按照散列函数的定义,如果两个对象相同,即 obj1.equals(obj2)=true,则它们的 hashCode 必须相同,但如果两个对象不同,则它们的 hashCode 不一定不同,如果两个不同对象的 hashCode 相同,这种现象称为冲突,冲突会导致操作哈希表的时间开