java中的容器

List

ArrayList

linkedList

Map

HashTable

HashMap

LinkedHashMap

Treemap

WeekHashMap

ConcurrentHashMap

IdentityHashMap

Set

HashSet

LinkedHashSet

TreeSet

Queue

Deque

1.1 ArrayList

ArrayList实现了可变大小的数组,相当于动态数组,存储在连续的地址空间。它允许所有元素，包括null。ArrayList没有同步。

ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。

ArrayList 函数clone()，能被克隆。

ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

现在基本上不怎么用vector了，大部分的性质和ArrayList一样，但是vector是线程安全的。

方法：

// Collection中定义的API
boolean             add(E object)
boolean             addAll(Collection<? extends E> collection)
void                clear()
boolean             contains(Object object)
boolean             containsAll(Collection<?> collection)
boolean             equals(Object object)
int                 hashCode()
boolean             isEmpty()
Iterator<E>         iterator()
boolean             remove(Object object)
boolean             removeAll(Collection<?> collection)
boolean             retainAll(Collection<?> collection)
int                 size()
<T> T[]             toArray(T[] array)
Object[]            toArray()
// AbstractCollection中定义的API
void                add(int location, E object)
boolean             addAll(int location, Collection<? extends E> collection)
E                   get(int location)
int                 indexOf(Object object)
int                 lastIndexOf(Object object)
ListIterator<E>     listIterator(int location)
ListIterator<E>     listIterator()
E                   remove(int location)
E                   set(int location, E object)
List<E>             subList(int start, int end)
// ArrayList新增的API
Object               clone()
void                 ensureCapacity(int minimumCapacity)
void                 trimToSize()
void                 removeRange(int fromIndex, int toIndex)

每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

特性

(1) ArrayList 通过一个数组去保存数据的。当我们构造ArrayList时，若使用默认构造函数，设置默认的大小，当容量不足时再设置新的容量。

(2) java.io.Serializable的方式。当写入到输出流时，先写入“容量”，再依次写入“每一个元素”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。

遍历方式

（1）Iterater （2）随机访问，get(i) （3）循环 for(m:list)

1.2 linkedList

linkedList是双向循环链表，继承AbstractSequentialList 抽象类，实现了List，Deque，Cloneable，Serializable 几个接口。

方法：

boolean             add(E object)
void                add(int location, E object)
public void addFirst(E e)   VS   public boolean offerFirst(E e)
public void addLast(E e)   VS  public boolean offerLast(E e)
public void clear()
public boolean contains(Object o)
public int indexOf(Object o)
public E element()等于public E getFirst()
public E get(int index)  
public E set(int index, E element)
public E getLast()
public int lastIndexOf(Object o)
public boolean offer(E e)
public E peek()  VS getfirst()  VS  peekFirst()
public E peekLast()  VS getlast()
public E poll() VS pollFirst()  VS  removeFirst()
public E pollLast()  VS   removeLast()
public E pop() 等于 removeFirst()
public void push(E e)  等于 addFirst()
public E remove() 等于 removeFirst()
public E remove(int index)
public boolean remove(Object o)
public boolean removeFirstOccurrence(Object o)
public boolean removeLastOccurrence(Object o)

public Object clone()
public Object[] toArray()

迭代器

ListIterator<String> itr = list.listIterator();
          while (itr.hasNext()) {
              System.out.println(itr.next());
          }

还有一个反向的迭代器叫做DescendingIterator

2.1 HashTable

（1）hashTable存储的是键值对。

（2）通过单链表解决冲突问题，容量不足时，自动增长。

（3）线程安全的

（4）实现了Serializable,Cloneable接口.

方法：

public synchronized V put(K key, V value)
public synchronized V get(Object key) 
public synchronized V remove(Object key)
\\函数很多省略

HashTable的迭代器：

Map<Integer,String> m=new HashMap<>();
    m.put(3, "Value3");
    for(Iterator t=m.keySet().iterator();t.hasNext();){
        String   key   =   (String)   t.next();
        Object   value   =   m.get(key);
    }

2.2 HashMap

HashMap默认的initialCapacity为16，loadFactor为0.75：

HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap允许存放null键和null值。key值只允许有一个null，value则可以允许有多个null。当key为null时，键值对永远都放在以table[0]为头结点的链表中。
每次根据hashCode()计算键值对存放的位置，还会用equals判断key是否一样，如果一样的化，新的值将会覆盖旧的值，如果不一样的话，新的键值对会插入到相应位置的头部。
是动态的链表，会根据threshold扩容，当数据量超过threshold就会扩容，容量增大一倍。
hashMap不是线程安全的
因为包含空值，所以不能通过get函数的返回值来判断是非包含某个key或者value，应该使用containKey或者是containValue.
clear()方法，清空Map

2.3 LinkedHashMap

LinkedHashMap是HashMap的子类，LinkedHashMap维护一个双向链表来保存插入数据或者访问数据的顺序，HashMap遍历的时候，顺序是未知的。同样可以有null的key和value。也不是线程安全的。

注意

LinkedHashMap默认根据插入的顺序来维护这个双向链表，但是它也支持访问的顺序。网上看到一个例子：

例子如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：

public LinkedHashMap(int initialCapacity,  
         float loadFactor,  
                     boolean accessOrder) {  
    super(initialCapacity, loadFactor);  
    this.accessOrder = accessOrder;  
}

LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。

private static final int MAX_ENTRIES = 100;  
protected boolean removeEldestEntry(Map.Entry eldest) {  
    return size() > MAX_ENTRIES;  
}  

2.4 Treemap

Treemap实际上就是用红黑树实现的Map。红黑树的原理可以参考：

Treemap中的插入删除等操作都是遵循红黑树的插入删除算法。

2.5 WeakHashMap

WeakHashMap的键是“弱键”。也就是说weakHashMap的键没有其他地方的引用的时候，就会被回收。WeakHashMap中所有的值都是保存在一个table中的，当某“弱键”不再被其它对象引用，会被回收，这个“弱键”会被添加到ReferenceQueue(queue)队列中，下一次同步这个table和队列就可以了。

2.6 ConcurrentHashMap

实际上HashMap是线程不安全的，因此在多线程的情况下使用hashMap的put操作时，会引发死循环。而HashTable因为锁机制使得它效率比较低，不允许同时进行put操作。ConcurrentHashMap就是介于这两者之间，采用分段锁机制，使其可以被并行使用。把数据分成多段，给每一段数据都分配一把锁，同一段数据内部不允许同时操作，不同段的数据可以同时操作，因此提高了它的效率。

2.7 IdentityHashMap

IdentityHashMap会允许Key值重复。个人理解是IdentityHashMap认为key和value都相等的话，才认为是重复的，不然不认为是重复的。

3.1 HashSet

HashSet是基于HashMap实现的，底层采用HashMap来存储元素。也就是说HashSet中的元素都是存在HashMap的Key中的。

注意：

HashSet 中判断两个对象相等需要满足两个要求：

（1）通过 equals() 方法判断比较返回 true

（2）两个对象的 hashCode() 返回值相等

所以当使用某个类的对象作为key值存入hashMap中时，需要注意重写equals()方法和hashCode() 方法。

3.2 LinkedHashSet

LinkedHashSet以元素插入的顺序来维护集合的链接表，允许以插入的顺序在集合中迭代。其实LinkedHashSet是对LinkedHashMap的简单包装。

3.3 TreeSet

提供一个使用树结构存储Set接口的实现，对象以升序顺序存储，访问和遍历的时间很快。

TreeSet中的元素支持2种排序方式：

自然排序根据Comparator 进行排序。

TreeSet是非同步的。

TreeSet不支持快速随机遍历，只能通过迭代器进行遍历。有Iterator和descendingIterator。

Queue

在java里面，Queue是借口，有很多种实现，以下是实现了Queue的一些类。AbstractQueue, ArrayBlockingQueue, ConcurrentLinkedQueue, LinkedBlockingQueue, DelayQueue, LinkedList, PriorityBlockingQueue, PriorityQueue和ArrayDqueue。

其中用的最多的是linkedList实现的。

方法：

boolean add(E e);  
boolean add(E e);  
boolean offer(E e);  
void addFirst(E e);    
void addLast(E e);    
boolean offerFirst(E e);    
boolean offerLast(E e);
E removeFirst();    
E removeLast();    
E pollFirst();    
E pollLast();    
E remove();    
E poll(); 
E getFirst();   
E getLast();    
E peekFirst();    
E peekLast();    
E element();    
E peek(); 

PriorityQueue:

Deque

Deque是双向队列，继承自queue。区别在于Deque可以实现stack的功能，也就是先进后出的功能。

public interface Deque<E> extends Queue<E> {//继承自Queue接口并进行扩展，支持双端操作  
    void addFirst(E e);//将指定元素插入此双端队列的开头。如果此队列有容量限制且当前没有可用空间，则抛出异常  
    void addLast(E e);//将指定元素插入此双端队列的末尾。如果此队列有容量限制且当前没有可用空间，则抛出异常  
    boolean offerFirst(E e);//将指定的元素插入此双端队列的开头。如果此队列有容量限制且当前没有可用空间，false  
    boolean offerLast(E e);//将指定的元素插入此双端队列的末尾。如果此队列有容量限制且当前没有可用空间，false  
    E removeFirst();//获取并移除此双端队列第一个元素;如果此队列为空，则抛出异常。  
    E removeLast();//获取并移除此双端队列最后一个元素;如果此队列为空，则抛出异常。  
    E pollFirst();//获取并移除此双端队列第一个元素;如果此队列为空，则返回 null。  
    E pollLast();//获取并移除此双端队列最后一个元素;如果此队列为空，则返回 null。  
    E getFirst();//获取但不移除此队列的头；如果此队列为空，则抛出异常。  
    E getLast();//获取但不移除此双端队列最后一个元素；如果此队列为空，则抛出异常  
    E peekFirst();//获取但不移除此队列的头；如果此队列为空，则返回 null。  
    E peekLast();//获取但不移除此队列的头；如果此队列为空，则返回 null。  
    boolean removeFirstOccurrence(Object o);//从此双端队列移除第一次出现的指定元素。如果此双端队列不包含该元素，则不作更改  
    boolean removeLastOccurrence(Object o);//从此双端队列移除最后一次出现的指定元素。如果此双端队列不包含该元素，则不作更改  
    boolean add(E e);//等效于addLast  
    boolean offer(E e);//等效于offerLast  
    E remove();//等效于 removeFirst()。   
    E poll();//此方法等效于 pollFirst()。   
    E element();//此方法等效于 getFirst()。  
    E peek();//此方法等效于 peekFirst()。  
    void push(E e);//此方法等效于 addFirst(E)。  
    E pop();//此方法等效于 removeFirst()。  
    boolean remove(Object o);//此方法等效于 removeFirstOccurrence(java.lang.Object)。  
    boolean contains(Object o);//如果此双端队列包含指定元素，则返回 true  
    public int size();//返回此双端队列的元素数。  
    Iterator<E> iterator();//返回以恰当顺序在此双端队列的元素上进行迭代的迭代器  
    Iterator<E> descendingIterator();//返回以逆向顺序在此双端队列的元素上进行迭代的迭代器  
  
} 

参考链接：

http://www.cnblogs.com/skywang12345/p/3308556.html http://blog.csdn.net/hla199106/article/details/46912615 http://blog.csdn.net/hello_zihan/article/details/52997816

Chenlini

Stay hundry stay foolish.

javaNote