HashMap和HashTable的區(qū)別
HashMap和Hashtable都實現(xiàn)了Map接口,主要的區(qū)別有：線程安全性，同步(synchronization)，以及速度
1.從類繼承和接口實現(xiàn)比較，HashTable除了實現(xiàn)Map接口，還繼承了Dictionary
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {}
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {}
- HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)
- Hashtable是synchronized，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴展性更好。
- 另一個區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器
package java.util;
public interface Enumeration<E> {
boolean hasMoreElements();
E nextElement();
}
package java.util;
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
- 由于Hashtable是線程安全的也是synchronized，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過Hashtable
- HashMap進行put操作時，會重新計算key的hashcode，(JDK1.8)將元素放到鏈表的末尾（如果是JDK1.7，新元素會插在頭部）；HashTable進行put操作時，會直接采用Key的hashCode，將元素插到鏈表頭部
// 基于JDK 1.8版本的代碼
// HashTable put方法
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
// HashMap put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- HashMap初始容量默認為16，進行resize的時候，直接將容量擴大一倍
；HashTable初始容量是11，resize時直接將容量擴大一倍再加一
HashMap和HashSet的區(qū)別
HashSet本質上是基于HashMap實現(xiàn)的，HashSet只存儲Key，內(nèi)部使用HashMap的put方法，value是一個Object對象（PRESENT），所以當出現(xiàn)key相同時是不會進行覆蓋操作的
但是HashSet實現(xiàn)的時Set接口，HashMap實現(xiàn)的是Map接口
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
// something....
}
HashMap和ConcurrentHashMap
- HashMap不是線程安全的，concurrentHashMap是線程安全的
- concurrentHashMap采用更細粒度的鎖，它將整個hash桶進行分段segment，也就是將這個大的數(shù)組分成了幾個小的segment，每個小的segment上都有鎖存在，插入數(shù)據(jù)時就需要先找到應該插入那個segment，然后再在這上面插入
HashMap原理
JDK 1.8之前HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結構，即數(shù)組和鏈表的結合體
JDK 1.8 中引入了 紅黑樹（查找時間復雜度為 O(logn)）
hashMap結構
// JDK hashMAp 源碼
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
put
往 HashMap 中 put 元素的時候，先根據(jù) key 的 hashCode 重新計算 hash 值，根據(jù) hash 值得到這個元素在數(shù)組中的位置（即下標），如果數(shù)組該位置上已經(jīng)存放有其他元素了，那么在這個位置上的元素將以鏈表的形式存放，JDK1.8中新加入的放在鏈尾，最先加入的放在鏈頭，1.8之前的相反。如果數(shù)組該位置上沒有元素，就直接將該元素放到此數(shù)組中的該位置上。
// JDK1.6版本源碼，1.8源碼見上文
public V put(K key, V value) {
//其允許存放null的key和null的value，當其key為null時，調(diào)用putForNullKey方法，放入到table[0]的這個位置
if (key == null)
return putForNullKey(value);
//通過調(diào)用hash方法對key進行哈希，得到哈希之后的數(shù)值。該方法實現(xiàn)可以通過看源碼，其目的是為了盡可能的讓鍵值對可以分不到不同的桶中
int hash = hash(key);
//根據(jù)上一步驟中求出的hash得到在數(shù)組中是索引i
int i = indexFor(hash, table.length);
//如果i處的Entry不為null，則通過其next指針不斷遍歷e元素的下一個元素。
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;
}
get
從 HashMap 中 get 元素時，首先計算 key 的 hashCode，找到數(shù)組中對應位置的某一元素，然后通過 key 的 equals 方法在對應位置的鏈表中找到需要的元素。
// JDK 1.8源碼
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashMap 的 resize（rehash）
當 HashMap 中的元素越來越多的時候，hash 沖突的幾率也就越來越高，因為數(shù)組的長度是固定的。所以為了提高查詢的效率，就要對 HashMap 的數(shù)組進行擴容，數(shù)組擴容這個操作也會出現(xiàn)在 ArrayList 中，這是一個常用的操作，而在 HashMap 數(shù)組擴容之后，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置，并放進去，這就是 resize。
那么 HashMap 什么時候進行擴容呢？當 HashMap 中的元素個數(shù)超過數(shù)組大小時，就會進行數(shù)組擴容，loadFactor的默認值為 0.75，這是一個折中的取值。也就是說，默認情況下，數(shù)組大小為 16，那么當 HashMap 中元素個數(shù)超過
的時候，就把數(shù)組的大小擴展為
，即擴大一倍，然后重新計算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經(jīng)預知 HashMap 中元素的個數(shù)，那么預設元素的個數(shù)能夠有效的提高 HashMap 的性能。
HashMap 在 JDK 1.8 中新增的數(shù)據(jù)結構 – 紅黑樹
鏈表長度大于8時轉為紅黑樹
JDK 1.7 ConcurrentHashMap
因為多線程環(huán)境下，使用Hashmap進行put操作會引起死循環(huán)，導致CPU利用率接近100%，所以在并發(fā)情況下不能使用HashMap。
concurrentHashMap結構示意圖
- ConcurrentHashMap是由Segment數(shù)組結構和HashEntry數(shù)組結構組成。
- Segment是一種可重入鎖ReentrantLock，在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲鍵值對數(shù)據(jù)。
- 一個ConcurrentHashMap里包含一個Segment數(shù)組，Segment的結構和HashMap類似，是一種數(shù)組和鏈表結構， 一個Segment里包含一個HashEntry數(shù)組，每個HashEntry是一個鏈表結構的元素， 每個Segment守護著一個HashEntry數(shù)組里的元素,當對HashEntry數(shù)組的數(shù)據(jù)進行修改時，必須首先獲得它對應的Segment鎖。
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
ConcurrentHashMap不允許key或者value為空
if (key == null || value == null) throw new NullPointerException();
JDK 1.8 ConcurrentHashMap
放棄了segment的設計，取而代之的是Node+CAS+Synchronized來保證并發(fā)安全。只有在執(zhí)行第一次put方法時，才會調(diào)用initTable（）初始化Node數(shù)組。
