HashMap，HashSet，Hashtable，Vector，ArrayList 的關系

這么幾個比較常用的但是比較容易混淆的概念同出于 java.util 包。本文僅作幾個類的淺度解析。（本文基于JDK1.7，源碼來自openjdk1.7。）

├── Collection
│   ├── List │   │   ├── ArrayList
│   │   ├── Vector
│   │   └── LinkedList and so on;
│   Set
│   ├── HashSet
│   └── LinkedHashSet and so on;
└── Map
    ├── Hashtable
    ├── HashMap
    └── WeakHashMap and so on;

Collection和Map

按理來說和這兩者沒有什么特別關系。然而本文中仍然將這兩個混在一起：

• 第一，HashSet，HashMap，Hashtable長得太像了，沒有理由不寫再一起。
• 第二，HashSet是個Set，其實骨子里是個Map。

List

繼承List的類，泛型為Integer時，注意和其他的類型不同。（因為Index是Integer）

線程安全

簡單來說，List是個一維數組。Vector和ArrayList區別在于：

Vector是個線程安全的，而ArrayList不是。這點看源碼可以看出來，Vector中各種synchronized，甚至連size屬性都喪心病狂地synchronized了。

同樣，Iterator指定Vector和ArrayList，如果中間發生變化則會拋出ConcurrentModificationException異常。不僅僅是List，很多地方的Iterator都有這個異常，

自增大小

ArrayList沒辦法設置自增大小，但是仍然可以自增。Vector可以設置自增大小。

ArrayList的自增函數：

Vector的自增函數：

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                   capacityIncrement : oldCapacity);
  //在這里，如果沒有設置自增大小的話，那么默認自增大小則是原來的Vector大小。
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  elementData = Arrays.copyOf(elementData, newCapacity);
}

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  //新長度則是舊長度的大小加上一個移位運算（一半的大小）。
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  elementData = Arrays.copyOf(elementData, newCapacity);
}

所以可以簡單的認為Vector默認自增一倍的長度，ArrayList則是默認自增一半的長度。

同樣，對他們的源碼分析：Vector可以設置自增大小，而ArrayList則無法設置（沒有這個構造方法）。

public Vector(int initialCapacity, int capacityIncrement)

最后，可以List list=new ArrayList<>();，然后list=new Vector<>();，使用基類List可以實現ArrayList和Vector的快速賦值。

Map

Map可以當成是簡單的“Key-Value”數據庫，例如memcached和redis。

線程安全

Hashtable也是線程安全的，和Vector一樣，連size函數都喪心病狂地同步了。

public synchronized int size() {                                                                                                             
    return count;
}     

HashMap不是線程安全的，當然也可以用其他的黑科技實現同步，例如SynchronizedMap和ConcurrentHashMap。那個以后再說……

空值

HashMap允許在Key和Value中都出現null值。例如：

v.toString()
{null=null, 1=66, 2=null, 3=4d, 4=0f, 5=null}

而Hashtable則不允許K/V的任何一個出現null值，但是允許空字符串。

Hashtable<String,String> v=new Hashtable<String,String>();
v.put("3s",null);

直接報錯：java.lang.NullPointerException。這個和內部實現有關，Hashtable需要用到hashCode，所以必須要確保K/V不為null。

相關代碼寫死在源碼里：

public synchronized V put(K key, V value) {
 // Make sure the value is not null
 if (value == null) {
     throw new NullPointerException();
 }
 //下面對hashCode做點事情。

Set

HashSet本質上是一個Collection，類似于List，是列表/集合，不是K-V的Map，但是它骨子里是一個HashMap……

這么說可能會更易于理解：HashSet對外是“類”的集合，實際上是內部維護了一個HashMap進行實現。

實際上存儲的是兩個：hashCode和類本身（字符串/自定義類等）。

HashSet進行add的時候，會先進行驗證hashCode：(HashSet進行add操作實際上是對Map的put操作)

public V put(K key, V value) {
  if (table == EMPTY_TABLE) {
    inflateTable(threshold);
  }
  if (key == null)
    return putForNullKey(value);
  int hash = hash(key);//本函數里有hashCode
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  modCount++;
  addEntry(hash, key, value, i);
  return null;
}

一個對HashSet的自定義類的操作：

 class Name  
{  
  private String first;   
  private String last;   
  public Name(String first, String last)   
  {   
    this.first = first;   
    this.last = last;   
  }   
  public boolean equals(Object o)   
  {   
    if (this == o)   
    {   
      return true;   
    }   
  if (o.getClass() == Name.class)   
    {   
      Name n = (Name)o;   
      return n.first.equals(first)   
        && n.last.equals(last);   
    }   
    return false;   
  }   
}  
public class HashSetTest  
{  
  public static void main(String[] args)  
  {   
    Set<Name> s = new HashSet<Name>();  
    s.add(new Name("abc", "123"));  
    System.out.println(  
      s.contains(new Name("abc", "123")));  
  }  
}   

代碼來自 java中HashSet詳解

集合操作

Set其實做集合操作更加簡單。例如：

import java.util.*;
public class SetOperation {
       public static void main(String[] args) {
  Set<Integer> result = new HashSet<Integer>();
  Set<Integer> set1 = new HashSet<Integer>(){{
      add(1);
      add(3);
      add(5);
  }};
  Set<Integer> set2 = new HashSet<Integer>(){{
      add(1);
      add(2);
      add(3);
  }};
  result.clear();
  result.addAll(set1);
  result.retainAll(set2);
  System.out.println("交集："+result);
  result.clear();
  result.addAll(set1);
  result.removeAll(set2);
  System.out.println("差集："+result);
  result.clear();
  result.addAll(set1);
  result.addAll(set2);
  System.out.println("并集："+result);
        }
}

輸出：

交集：[1, 3] 差集：[5] 并集：[1, 2, 3, 5] 

參考文檔

hashSet中的equals方法和hashCode方法