Java中的集合类Collection,List, Set, Map; Array, Stack,Queue等

Published: 01 Sep 2015 Category: java

Java中的主要数据结构(整体图)

首先,要对这堆数据结构有一个大致的认识:

Java Data Structure

或者下列的树结构:

	Collection  
	├List  
	│├LinkedList   
	│├ArrayList  
	│└Vector  
	│ └Stack  
	└Set  

	Map  
	├Hashtable  
	├HashMap  
	├WeakHashMap  
	└TreeMap

经验总结

  • 如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。
  • 如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高,如果多个线程可能同时操作一个类,应该使用同步的类。
  • 要特别注意对哈希表的操作,作为key的对象要正确复写equals和hashCode方法。
  • 尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。

Collection

List和Set的父类。
注意:Java SDK不提供直接继承自Collection的类,Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

内置函数(工具类collections)

工具类collections用于操作集合类(collections在java中的常见用法),如List,Set,常用方法有:

  1. 排序(Sort)
    使用sort方法可以根据元素的自然顺序,对指定列表按升序进行排序。

    列表中的所有元素都必须实现 Comparable 接口。此列表内的所有元素都必须是使用指定比较器可相互比较的。如:

     List<Double> list = new ArrayList<>();
     double array[] = {112, 111, 23, 456, 231};
     for (int i = 0; i < array.length; i++) {
         list.add(new Double(array[i]));
     }
    
     Collections.sort(list);
    
     for (int i = 0; i < array.length; i++) {
         System.out.print(list.get(i) + " ");
     }
     // 结果:23.0 111.0 112.0 231.0 456.0
    
  2. 混排(Shuffling)
    混排算法所做的正好与 sort 相反: 它打乱在一个 List 中可能有的任何排列的踪迹。也就是说,基于随机源的输入重排该 List,这样的排列具有相同的可能性(假设随机源是公正的)。

     List<Double> list = new ArrayList<>();
     double array[] = {112, 111, 23, 456, 231};
     for (int i = 0; i < array.length; i++) {
         list.add(new Double(array[i]));
     }
    
     Collections.shuffle(list);
    
     for (int i = 0; i < array.length; i++) {
         System.out.print(list.get(i) + " ");
     }
     // 结果:23.0 231.0 112.0 456.0 111.0
    
  3. 反转(Reverse)
    使用Reverse方法可以根据元素的自然顺序 对指定列表按降序进行排序。

     List<Double> list = new ArrayList<>();
     double array[] = {112, 111, 23, 456, 231};
     for (int i = 0; i < array.length; i++) {
         list.add(new Double(array[i]));
     }
    
     Collections.reverse(list);
    
     for (int i = 0; i < array.length; i++) {
         System.out.print(list.get(i) + " ");
     }
     // 结果:231.0 456.0 23.0 111.0 112.0
    
  4. 替换所有的元素(Fill)
    使用指定元素替换指定列表中的所有元素。

     List<String> list = new ArrayList<>();
     String str[] = {"dd", "aa", "bb", "cc", "ee"};
     for (int j = 0; j < str.length; j++) {
         list.add(new String(str[j]));
     }
    
     Collections.fill(list, "aaa");
    
     for (int i = 0; i < list.size(); i++) {
         System.out.print(list.get(i) + " ");
     }
     //结果:aaa aaa aaa aaa aaa
    
  5. 拷贝(Copy)
    用两个参数,一个目标 List 和一个源 List, 将源的元素拷贝到目标,并覆盖它的内容。目标 List 至少与源一样长。如果它更长,则在目标 List 中的剩余元素不受影响。

    Collections.copy(list,li); //后面一个参数是目标列表 ,前一个是源列表

  6. 返回Collections中最小元素(min)和最大元素

    Collections.min(list);
    Collections.max(list);

  7. Rotate
    根据指定的距离循环移动指定列表中的元素 Collections.rotate(list,-1); 如果是负数,则正向移动,正数则方向移动

  8. static int binarySearch(List list,Object key)
    使用二分搜索查找key对象的索引值,因为使用的二分查找,所以前提是必须有序。

  9. static int frequency(Collection c,Object o)
    返回指定元素在集合中出现在次数


List

基本概念

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

      List<Integer> list = new LinkedList<Integer>();
      ListIterator iter = list.listIterator();
      iter.add(element);
      iter.next();
      iter.hasNext();
      iter.previous();
      iter.hasPrevious();
      iter.remove();
      iter.set(element);
    

实现类:

  1. LinkedList:
    • 允许null元素。
    • 此外LinkedList提供额外的get,remove,insert(list.add(index, element);list.set(index, element);)方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈(stack),队列(queue)或双向队列(deque)。
    • 注意LinkedList没有同步方法。如果多个线程同时访问一个List,则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List:

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

  2. ArrayList
    • ArrayList实现了可变大小的数组。
    • 它允许所有元素,包括null。
    • ArrayList没有同步。
    • size,isEmpty,get,set方法运行时间为常数。但是add方法开销为分摊的常数,添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
  3. Vector
    • Vector非常类似ArrayList,但是Vector是同步的。
  4. Stack
    • Stack继承自Vector,实现一个后进先出的堆栈。
    • Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素,empty方法测试堆栈是否为空,search方法检测一个元素在堆栈中的位置。

相互区别

  • Vector和ArrayList
    1. Vector是线程同步的,所以它也是线程安全的,而ArrayList是线程异步的,是不安全的。如果不考虑到线程的安全因素,一般用ArrayList效率比较高。
    2. 如果集合中的元素的数目大于目前集合数组的长度时,Vector增长率为目前数组长度的100%,而ArrayList增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据,用Vector有一定的优势。
    3. Vector由于使用了synchronized方法(线程安全)所以性能上比ArrayList要差,LinkedList使用双向链表实现存储,按序号索引数据需要进行向前或向后遍历,但是插入数据时只需要记录本项的前后项即可,所以插入数度较快。
  • Arraylist和Linkedlist
    1. ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
    2. 对于随机访问get和set,ArrayList得优于LinkedList,因为LinkedList要移动指针。
    3. 对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。

Set

基本概念

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

实现类型:

  1. TreeSet - 是Set的一种变体——可以实现排序等功能的集合。(TreeSet类实现了SortedSet接口,能够对集合中的对象进行排序。)

         treeSet.higher(element);//	Returns the least element in this set strictly greater than the given element, or null if there is no such element.  
    
         treeSet.lower(element);
    
         treeSet.floor(element);//<=element的最大数字
    
         treeSet.descendingSet();//Returns a reverse order view of the elements contained in this set.
    
  2. HashSet

    • 允许包含值为null的元素,但最多只能有一个null元素。

常用方法

	set.add(element);
	set.remove(element);
	set.size();
	set.isEmpty();

遍历

	Set<String> set = new HashSet<String>();
	//iteration
	Iterator<String> it = set.iterator();  
	while (it.hasNext()) {  
	  String str = it.next();  
	  System.out.println(str);  
	}  

	//for循环遍历:  
	for (String str : set) {  
	      System.out.println(str);  
	}  

Map

基本概念

Map没有继承Collection接口,Map提供key到value的映射。

实现类型

  1. HashMap
    • HashMap和Hashtable类似,不同之处在于HashMap是非同步的;
    • 允许null,即null value和null key。(只有HashMap可以让你将空值作为一个表的条目的key或value)
    • 但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap 的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。
  2. WeakHashMap
    • WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。
  3. Hashtable
    • 实现一个key-value映射的哈希表。任何非空(non-null)的对象都可作为key或者value。
    • Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大,这会影响像get和put这样的操作。
    • 由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。
    • Hashtable是同步的。
  4. TreeMap

相互区别

  • HashMap与TreeMap
    1. HashMap通过hashcode对其内容进行快速查找,而TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的)。
    2. 在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 equals()的实现。  
    3. TreeMap没有调优选项,因为该树总处于平衡状态。

常用操作:

map.put(key, value);
map.isEmpty();
map.get(key);
map.isEmpty();
map.clear();
map.containsKey(key);
map.containsValue(value);
map.remove(key);
map.size();

遍历方式:

Map<String, String> map = new HashMap<String, String>();
map.put("1", "a");
map.put("2", "b");
map.put("3", "c");

//最简洁、最通用的遍历方式
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

//方式2
for (Iterator<Map.Entry<String, String>> it = map.entrySet().iterator(); it.hasNext();) {
    Map.Entry<String, String> entry = it.next();
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

//方式3
for (Iterator<String> it = map.keySet().iterator(); it.hasNext();) {
    String key = it.next();
    System.out.println(key + " = " + map.get(key));
}

Queue

实现类型:

  1. PriorityQueue <T>
  2. LinkedList
  3. LinkedBlockingQueue <T>
    LinkedBlockingQueue实现是线程安全的,实现了先进先出等特性,是作为生产者消费者的首选,LinkedBlockingQueue 可以指定容量,也可以不指定,不指定的话,默认最大是Integer.MAX_VALUE,其中主要用到put和take方法,put方法在队列满的时候会阻塞直到有队列成员被消费,take方法在队列空的时候会阻塞,直到有队列成员被放进来。
  4. ConcurrentLinkedQueue
    ConcurrentLinkedQueue是Queue的一个安全实现.Queue中元素按FIFO原则进行排序.采用CAS操作,来保证元素的一致性。

普通的LinkedList实现并没有定义特殊的排序算法,所以输出元素时会按照插入的顺序.

PriorityQueue的内部是一个min heap,会按照从上至下,从左至右的输出。

并发队列ConcurrentLinkedQueue和阻塞队列LinkedBlockingQueue用法

Queue Interface Structure

Operation Throws exception Returns special value
Insert add(e) offer(e)
Remove remove() poll()
Examine element() peek()

remove和poll方法都删除并返回Queue中的头元素(注意,并不是插入的第一个元素,因为有的Queue实现是排序的)。当Queue为空时,remove抛出NoSuchElementException异常,而poll返回null。

element和peek返回但不删除Queue中的头元素,它们的区别类似remove与poll。

常用方法

queue.add(element); //注意:没有push方法或put方法
queue.offer(element);///与add的区别:
//1. add属于interface Collection<E>,而offer属于interface Deque<E>;
//2. When using a capacity-restricted queue, this method is generally preferable to add, 
// which can fail to insert an element only by throwing an exception.(如果队列满了,add会抛异常,而offer返回false)

queue.poll();		//注意:没有pop方法
queue.peek();
queue.clear();
queue.containsAll(collection); //是否包含集合中的所有元素
queue.retainAll(collection); //保留集合中的元素
queue.removeAll(collection); //删除集合中的元素
queue.toArray();

遍历

//集合方式遍历,元素不会被移除
for (Integer element : queue) {
    System.out.println(element);
}

//队列方式遍历,元素逐个被移除
while (queue.peek() != null) {
    System.out.println(queue.poll());
}

Stack

初始化类型:

Stack

常用方法:

stack.push(element);
stack.peek();
stack.pop();
stack.containsAll(collection); //是否包含集合中的所有元素
stack.retainAll(collection); //保留集合中的元素
stack.removeAll(collection); //删除集合中的元素
stack.toArray();
stack.copyInto(anArray);

Java中的stack都不是严格意义上的stack了,例如可以:

stack.add(index, element);
stack.get(index);
stack.lastElement();
stack.firstElement();
stack.set(index, element);
stack.setElementAt(element, index);
stack.elementAt(index);    //返回element类型

遍历方法:

Stack<Integer> s = new Stack<Integer>();
for (int i = 0; i < 10; i++) {
    s.push(i);
}
//集合遍历方式
for (Integer element : s) {
    System.out.println(element);
}

//栈弹出遍历方式
//while (s.peek()!=null) {
//不健壮的判断方式,容易抛异常,正确写法是下面的
while (!s.empty()) {
    System.out.println(s.pop());
}

Arrays

Java 2 在 java.util 中新增加了一个叫做 Arrays 的类。这个类提供了各种在进行数组运算 时很有用的方法。尽管这些方法在技术上不属于类集框架,但它们提供了跨越类集和数组的桥梁。

常见方法

  • static List asList(Object[ ] array) //视为list
  • binarySearch()方法使用二分法搜索寻找指定的值。该方法必须应用于排序数组。如:

      static int binarySearch(int[ ] array, int value)
    

Enumeration

Enumeration(更像是数据类型) 接口定义了可以对一个对象的类集中的元素进行枚举(一次获得一个)的 方法。这个接口尽管没有被摈弃,但已经被 Iterator 所替代。

Enumeration 指定下面的两个方法:

  • boolean hasMoreElements()
  • Object nextElement()

执行后,当仍有更多的元素可提取时,hasMoreElements()方法一定返回 true。当所有元素都被枚举了,则返回 false。

nextElement()方法将枚举中的下一个对象做为一个类属 Object 的引用而返回。也就是每次调用 nextElement()方法获得枚举中的下一个对象。调用例程必须 将那个对象转换为包含在枚举内的对象类型.


Properties

属性(Properties)是 Hashtable 的一个子类。它用来保持值的列表,在其中关键字和值 都是字符串(String)。

Properties 类被许多其他的Java 类所使用。例如,当获得系统环境 值时,System.getProperties()返回对象的类型。

Properties 类的一个有用的功能是可以指定一个默认属性,如果没有值与特定的关键字 相关联,则返回这个默认属性。例如,默认值可以与关键字一起在 getProperty()方法中被指 定——如 getProperty(“name”,“default value”)。如果“name”值没有找到,则返回“default value”。


Dictionary

Dictionary 类是一个抽象类,用来存储键/值对,作用和Map类相似。

给出键和值,你就可以将值存储在Dictionary对象中。一旦该值被存储,就可以通过它的键来获取它。所以和Map一样, Dictionary 也可以作为一个键/值对列表.

Dictionary类已经过时了。在实际开发中,你可以实现Map接口来获取键/值的存储功能。


BitSet(位集合)

位集合类实现了一组可以单独设置和清除的位或标志。

该类在处理一组布尔值的时候非常有用,你只需要给每个值赋值一”位”,然后对位进行适当的设置或清除,就可以对布尔值进行操作了。

一个Bitset类创建一种特殊类型的数组来保存位值。BitSet中数组大小会随需要增加。这和位向量(vector of bits)比较类似。

详细点击:http://www.runoob.com/java/java-bitset-class.html


常见面试题

  1. ArrayList和Vector有什么区别?HashMap和HashTable有什么区别?
    A: Vector和HashTable是线程同步的(synchronized)。性能上,ArrayList和HashMap分别比Vector和Hashtable要好。

  2. 大致讲解java集合的体系结构
    List、Set、Map是这个集合体系中最主要的三个接口。
    其中List和Set继承自Collection接口。
    Set不允许元素重复。HashSet和TreeSet是两个主要的实现类 。 List有序且允许元素重复。ArrayList、LinkedList和Vector是三个主要的实现类。
    Map也属于集合系统,但和Collection接口不同。Map是key对value的映射集合,其中key列就是一个集合。key不能重复,但是value可以重复。HashMap、TreeMap和Hashtable是三个主要的实现类。
    SortedSet和SortedMap接口对元素按指定规则排序,SortedMap是对key列进行排序。

  3. Comparable和Comparator区别
    调用java.util.Collections.sort(List list)方法来进行排序的时候,List内的Object都必须实现了Comparable接口。 但如果是用java.util.Collections.sort(List list,Comparator c),可以临时声明一个Comparator 来实现排序。

     Collections.sort(imageList, new Comparator() {
         public int compare(Object a, Object b) {
             int orderA = Integer.parseInt( ( (Image) a).getSequence());
             int orderB = Integer.parseInt( ( (Image) b).getSequence());
             return orderA - orderB;
        }
     });
    
  4. stack和queue的相互实现
    stack实现queue:用两个stack实现,一个管入队(enqueue),一个管出队(dequeue);如果出队为空,将enqueue中的值放到dequeue中。
    queue实现stack:两个queue,一个充当临时的队列,每次top或pop的时候,将存储的queue倒入到tmpqueue中,记录下最后一个,返回或删除,之后再倒回去。

参考

  1. Java集合的Stack、Queue、Map的遍历
  2. JAVA集合小结
  3. Java集合类详解
  4. java_Collection_介绍