Java 集合类

 

 

1. 为什么要了解Java 集合类

Java 集合类提供了如线性表，链表和哈希表等基础数据结构的实现，通过它可以实现各种你想要的数据结构，如stack ，queue 等，了解Java 集合类的工作原理可以编出更高效性能的程序，另外了解其工作原理可以更好地使用它，避免因为滥用而出现性能上的问题。事实证明，很多性能上的问题都是因为使用不当引起的。

 

2.Java 集合类的概述

2.1 Java collection 的继承关系

 

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

└SortedSet

└HashSet

└TreeSet

Map   
├Hashtable   
├HashMap 

├SortedMap

  └TreeMap  
└WeakHashMap 

2.2 Java collection 概述

2.2.1 List 的简要概述

Java2 的集合框架，抽其核心，主要有三种： List 、 Set 和 Map

 

1. List 的主要特性

1） 有序的 Collection

2） 使用该接口可以精确定义元素插入的位置。

3） 用户能够通过索引来访问 List 的元素。

4） 元素允许重复，允许有 null 元素，基于 array 的 list 适合查询， linkedList 适合添加删除操作。

 

2. List 的主要方法

boolean contains(Object o);

Iterator<E> iterator();

Object[] toArray();

boolean add(E e)

boolean remove(Object o);

boolean containsAll(Collection<?> c);

boolean addAll(Collection<? extends E> c);

boolean addAll(int index, Collection<? extends E> c);

boolean removeAll(Collection<?> c);

boolean retainAll(Collection<?> c);

void clear();

E get(int index);

E set(int index, E element);

void add(int index, E element);

E remove(int index);

int indexOf(Object o);

int lastIndexOf(Object o);

 

2.Set 是不含重复元素的、无序的 Collection

 

3.Map 是一种以 key 和 value 形成对应关系的容器， key 重复会覆盖 value

 

2.2.2 Java collection 的 fail-fast 机制

在我们软件开发的过程中，当碰到问题了，我们第一步就是重现问题，然后进行 debug ，找出问题的原因，但往往有些 bug 隐藏的比较深，经过 n 次特定的操作的在特定的环境下才会重现，或者出错后，报错的 stack traces的没有指出错误的真正起点。 
所以我们设计一个 Fail Fast 的系统显得很重要了。 
很多人设计的系统，为了增强系统的健壮性，自动的将系统中出现的问题处理掉，并继续运行，但是在未来的某个时间引发奇怪的错误。 
而 fail fast 的系统的做法却是相反的，当有问题发生，立即出错，并将出错信息显示出来。这样 bug 就很容易被发现，而不会进入到最终的产品中。

java.util 包中的集合类都返回 fail-fast 迭代器，这意味着它们假设线程在集合内容中进行迭代时，集合不会更改它的内容。如果 fail-fast 迭代器检测到在迭代过程中进行了更改操作，那么它会抛出ConcurrentModificationException ，这是不可控异常。

 

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

 

public class TestFastFail {

   

    public static void main(String[] args) {

       List<String> list = new ArrayList<String>(20);

       for ( int i = 0; i < 20; i++) {

           list.add( "test" );

       }

      

        // 在迭代器迭代过程中，如果集合被修改被抛出 java.util.ConcurrentModificationException

       // 这就是 fast fail 的意义，早点发现程序的错误，并抛出异常

       Iterator<String> iterator = list.iterator();

       for ( int i = 0; iterator.hasNext(); i++) {

           String string = iterator.next();

           System. out .println(string);

           list.add( "" );

       }

    }

}

评论

4 楼 csdn_zuoqiang 2012-06-07  

CopyOnWriteArrayList工作原理和实例

CopyOnWriteArrayList顾名思义，在写入操作时，copy源数组到新的数组中，而读取时，是从源数组去读的，因为写入操作是在另外一个数组中执行，因此在读取时，不用进行线程同步，但是要注意一点，copy数组的开销在数据量大的情况下，非常耗资源，因此，它的使用场景，适合于读取远大于写入操作的场景。当然，在写入时，是有锁的，JDK中的实现是采用重入显式锁进行锁定的。当写操作完成以后再将源数组的引用指向copy的数组，最后释放锁。

主要方法如下：
public boolean add(E e)
  public void add(int index, E element)
public E get(int index)
public E set(int index, E element)
remove(i);
public int lastIndexOf(Object o)
public boolean addIfAbsent

3 楼 csdn_zuoqiang 2012-06-07  

这段时间好好整理了一下基础，发现很多对我来说新的东西，里面博大精深的东西真的很多，经常使用HashMap，对HashMap的结构和原理非常了解，但是忽略了还有LinkedHashMap这个好东西。
 
先转一篇blog：
 
LinkedHashMap的特性:
Linked内部含有一个private transient Entry header;来记录元素插入的顺序或者是元素被访问的顺序。利用这个线性结构的对象，可以帮助记录entry加入的前后顺序或者记录entry被访问的 频率(最少被访问的entry靠前，最近访问的entry靠后)。大致的过程如下:

new LinkedHashMap(10, 0.75, true);
其中前面两个参数就是HashMap构造函数需要的参数，后面的true表明LinkedHashMap按照访问的次序来排序。
按照访问的次序来排序的含义:当调用LinkedHashMap的get(key)或者put(key, value)时，碰巧key在map中被包含，那么LinkedHashMap会将key对象的entry放在线性结构的最后。
按照插入顺序来排序的含义:调用get(key), 或者put(key, value)并不会对线性结构产生任何的影响。

正是因为LinkedHashMap提供按照访问的次序来排序的功能，所以它才需要改写HashMap的get(key)方法（HashMap不需要排序）和HashMap.Entry的recordAccess(HashMap)方法
public Object get(Object key) {
        Entry e = (Entry)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this); 
        return e.value;
    }

void recordAccess(HashMap m) {
            LinkedHashMap lm = (LinkedHashMap)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
注 意addBefore(lm.header)是将该entry放在header线性表的最后。（参考LinkedHashMap.Entry extends HashMap.Entry 比起HashMap.Entry多了before, after两个域，是双向的）

至于put(key, value)方法， LinkedHashMap不需要去改写，用HashMap的就可以了，因为HashMap在其put(key, value)方法里边已经预留了e.recordAccess(this);

还有一个方法值得关注:
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return false;
    }
当 调用put(key, value)的时候，HashMap判断是否要自动增加map的size的作法是判断是否超过threshold， LinkedHashMap则进行了扩展，如果removeEldestEntry方法return false；（默认的实现），那么LinkedHashMap跟HashMap处理扩容的方式一致；如果removeEldestEntry返回 true，那么LinkedHashMap会自动删掉最不常用的那个entry（也就是header线性表最前面的那个）。
这会造成严重的性能问题吗？答案当然是否定的。因为在这儿的链表操作是常量级的。这也是LinkedHashMap/Set在这儿比TreeMap/Set性能更高的原因。
同样，LinkedHashMap/Set也不是thread-safe的。如果在多线程下访问，是需要进行外部同步，或者使用Collections.synchronizedMap()的方法包装成一个thread-safe的Map/Set。
特别需要注意的是，在使用“访问顺序”时，读取节点操作也是“结构变化”的操作。因为，这会改变元素遍历的顺序。所以，在使用 LinkedHashMap的iterator()方法，遍历元素时，如果其它线程有读取操作，也要进行同步。否则，也会抛出同其它fail-fast一 样的由于删除或增加操作而引起的CurrentModificationException的例外。 
最后，LinkedHashMap缺省是使用插入顺序的，如何构造一个访问顺序的LinkedHashMap呢？很简单： public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) accessOrder = true 即可。
 
回来补充一个利用LinkedHashMap来实现LRU的Cache类，看了上面的特性，实现起来实在太简单了！
 
package lru;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 *
 *<p>Test</p>
 *<p>Description:</P>
 *<p>Company:Cisco CAS</p>
 *<p>Department:CAS</p>
 *@Author: Tommy Zhou
 *@Since: 1.0
 *@Version:Date:2011-5-13
 *
 **/

public class LRUCache<K,V> extends LinkedHashMap<K, V>{
    private LinkedHashMap<K,V>  cache =null ;
    private int cacheSize = 0;
       
    public LRUCache(int cacheSize){
        this.cacheSize = cacheSize;
        int hashTableCapacity = (int) Math.ceil (cacheSize / 0.75f) + 1;
        cache = new LinkedHashMap<K, V>(hashTableCapacity, 0.75f,true)
        {
            // (an anonymous inner class)
            private static final long serialVersionUID = 1;

            @Override
            protected boolean removeEldestEntry (Map.Entry<K, V> eldest)
            {
                System.out.println("size="+size());
                return size () > LRUCache.this.cacheSize;
            }
        };
    }
   
    public V put(K key,V value){
        return cache.put(key, value);
    }

    public V get(Object key){
        return cache.get(key);
    }
    
    public static void main(String[] args) {
        LRUCache<String, String> lruCache = new LRUCache<String, String>(5);
        lruCache.put("1", "1");
        lruCache.put("2", "2");
        lruCache.put("3", "3");
        lruCache.put("4", "4");
        
        System.out.println(lruCache.get("2"));
        lruCache.get("2");
        lruCache.put("6", "6");
        lruCache.put("5", "5");
        System.out.println(lruCache.get("1"));
        
        
        
        
    }

}

2 楼 csdn_zuoqiang 2012-06-07  

4.  Set
Set 是不包含重复元素的集合。可以更加正式地表达为，在 set 里面的元素 e1,e2, 不允许 e1.equals(e2), 而且最多有一个 null 元素。
Set 的主要方法如下，可以看出 List 和 Set 在方法上的区别了， List 能够根据类似于 index ，来找到元素的方法，而 set 只管往集合里面放东西，并不管其插入的顺序， List 有比较严格的插入顺序。
//Set 是否为空
boolean isEmpty();
// 是否包含指定元素
boolean contains(Object o);
// 遍历 Set
Iterator<E> iterator();
// 转化成数组
Object[] toArray();
// 添加元素
boolean add(E e);
// 清空集合
void clear();
// 只保留包含指定集合的元素
boolean retainAll(Collection<?> c);

4.1 HashSet
1 ． HashSet 的数据结构和工作原理
HashSet 的基本数据结构是 HashMap ， HashMap 的基本数据结构是哈希表和链表，在构造函数上可以参见 HashMap 的工作原理，和 HashMap 一样，影响性能的因素包括： set 的初始化容量大小，容量因子，和 HashCode 的构造，其主要方法实现如下：
/**
* 添加元素，注意是将 elment 作为 key 存进 HashupMap ，
* 同时指定所有对应的 element 的 value 都为同一个对象，
* 这样可以防止元素重复，同时可以看出 Hashset 允许
* 空元素
*/
public boolean add(E e) {
       return map.put(e, PRESENT)==null;
}
/**
* 移除元素
*/
public boolean remove(Object o) {
       return map.remove(o)==PRESENT;
}
/**
* 清空 set
*/
public void clear() {
       map.clear();
}
 
/**
*Clone Set
*/
public Object clone() {
       try {
              HashSet<E> newSet = (HashSet<E>) super.clone();
              newSet.map = (HashMap<E, Object>) map.clone();
              return newSet;
       } catch (CloneNotSupportedException e) {
              throw new InternalError();
       }
}
 
public boolean contains(Object o) {
       return map.containsKey(o);
}
 
public boolean isEmpty() {
       return map.isEmpty();
}
public int size() {
       return map.size();
}
 
public Iterator<E> iterator() {
       return map.keySet().iterator();
}

1 楼 csdn_zuoqiang 2012-06-07  

3. List
3.1 Vector
1 ． Vector 的数据结构和工作原理
Vector 是基本数据结构一个可变数组，数组的元素可以是任意对象，当 Vector 初始创建时，会创建一个一定容量（Capacity）的（默认为 10 ）数组对象，当添加的对象超过数组的容量时， Vector 在内部会重新创建一个新的数组，再把原数组元素拷贝到新的数组里面，这样就完成了动态数组的功能。 Vector 的构造器有三种
1） public Vector(int initialCapacity, int capacityIncrement)
initialCapacity 是数组的初始化长度， capacityIncrement 是当数组长度超过原长度时，数组长度增长的步长， capacityIncrement 为 0 时，此种情况当数组长度超过原长度峰值时，此时数组长度变为原来的 2 倍。当数组长度变化，原有的数据和新的数组对象是通过 copy 来完成的。
2） public Vector(int initialCapacity)
3） public Vector()
Vector 默认构造器的数组的长度是 10
 
 
核心方法：
/**
     * 核心方法之一：保证数组的容量，如果没有指定容量的增长的步长，则将原数组容量扩 * 大成原来的两倍，如果指定则按照增长的步长增加容量，并且取 minCapacity 和 *newCapacity 计算出来的最大值进行取值。计算出来的最终容量将作为新数组对象的尺 * 寸，并将原来数组的元素 copy 到新数组里面来。
     *
     * @see #ensureCapacity(int)
     */
    private void ensureCapacityHelper( int minCapacity) {
    int oldCapacity = elementData . length ;
    if (minCapacity > oldCapacity) {
        Object[] oldData = elementData ;
        int newCapacity = ( capacityIncrement > 0) ?
       (oldCapacity + capacityIncrement ) : (oldCapacity * 2);
         if (newCapacity < minCapacity) {
       newCapacity = minCapacity;
        }
            elementData = Arrays.copyOf ( elementData , newCapacity);
    }
    }
 
2.Vector 使用时需要注意的问题
1) Vector 使用时，最好能够预期需要存放元素的个数，这样可以避免数组长度频繁的改变而引起数据的 copy 带来的开销，同时会引起内存大小的增加。
2 ）使用 Vector 需要知道 Vector 是线程安全的。因此，在使用时，最好是考虑这个对象会不会因为多个线程访问该 Vector 对象，如果确认只有单个线程访问，则可以用 ArrayList 来代替 Vector 。
 
 
3.    Stack
有 Vector 可以轻松改造成 Stack ，栈的特点是先进后出，对于一个栈来说，主要方法包括， push(E e), pop, peek,empty 和 search(E e).
public class Stack <E> extends Vector<E> {
   
    public Stack(){
       super (10);
    }
   
    public void push(E e){
       this .add(e);
    }
   
    public E pop(){
       return this .remove( this .size()-1);
    }
   
    public boolean empty(){
       return this .size()==0;
    }
   
    public int search(E e){
        for (int i = 0; i < this.size(); i++) {
            if(this.elementAt(i).equals(e)){
                return i;
            }else{
                continue;
            }
        }
        
        return -1;
    }
}