To Solve：
- 什么時候會使用HashMap？有什么特點？
- HashMap的工作原理？
- get和put的原理？equals()和hashCode()的都有什么作用？
- hashing的概念, 如何實現(xiàn)的？為什么要這樣實現(xiàn)？
- HashMap中解決碰撞的方法
- equals()和hashCode()的應(yīng)用，以及它們在HashMap中的重要性
- 如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量，怎么辦？
- 重新調(diào)整HashMap的大?。≧ehashing/Resize）
- 不可變對象的好處
- HashMap多線程的條件競爭
- Java8 HashMap的性能優(yōu)化
- HashMap和HashTable的區(qū)別
- HashMap和HashSet的區(qū)別
概念及原理
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
幾個關(guān)鍵的信息：基于Map接口實現(xiàn)、允許null鍵/值、非同步、不保證有序(比如插入的順序)、也不保證序不隨時間變化。
Capacity, Load Factor
在HashMap中有兩個很重要的參數(shù)，容量(Capacity)和負(fù)載因子(Load factor)
Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
簡單的說，Capacity就是buckets的數(shù)目，Load factor就是buckets填滿程度的最大比例。如果對迭代性能要求很高的話不要把capacity設(shè)置過大，也不要把load factor設(shè)置過小。當(dāng)bucket填充的數(shù)目（即hashmap中元素的個數(shù)）大于capacity*load factor時就需要調(diào)整buckets的數(shù)目為當(dāng)前的2倍。
Put原理
- 對key的hashCode()做hash，然后再計算index;
- 如果沒碰撞直接放到bucket里；
- 如果碰撞了，以鏈表的形式存在buckets后；
- 如果碰撞導(dǎo)致鏈表過長(大于等于TREEIFY_THRESHOLD)，就把鏈表轉(zhuǎn)換成紅黑樹；
- 如果節(jié)點已經(jīng)存在就替換old value(保證key的唯一性)
- 如果bucket滿了(超過load factor*current capacity)，就要resize。
public V put(K key, V value) {
// 對key的hashCode()做hash
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;
// tab為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算index，并對null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 節(jié)點存在
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;
// 超過load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Get 原理
- bucket里的第一個節(jié)點，直接命中；
- 如果有沖突，則通過key.equals(k)去查找對應(yīng)的entry
若為樹，則在樹中通過key.equals(k)查找，O(logn)；
若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。
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) {
// 在樹中g(shù)et
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中g(shù)et
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
Hash function
在get和put的過程中，計算下標(biāo)時，先對hashCode進(jìn)行hash操作，然后再通過hash值進(jìn)一步計算下標(biāo)。如圖所示：
在對hashCode()計算hash時具體實現(xiàn)是這樣的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到這個函數(shù)大概的作用就是：高16bit不變，低16bit和高16bit做了一個異或。其中代碼注釋是這樣寫的：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
在設(shè)計hash函數(shù)時，因為目前的table長度n為2的冪，而計算下標(biāo)的時候，是這樣實現(xiàn)的(使用&位操作，而非%求余)：
(n - 1) & hash
設(shè)計者認(rèn)為這方法很容易發(fā)生碰撞。為什么這么說呢？不妨思考一下，在n - 1為15(0x1111)時，其實散列真正生效的只是低4bit的有效位，當(dāng)然容易碰撞了。
因此，設(shè)計者想了一個顧全大局的方法(綜合考慮了速度、作用、質(zhì)量)，就是把高16bit和低16bit異或了一下。設(shè)計者還解釋到因為現(xiàn)在大多數(shù)的hashCode的分布已經(jīng)很不錯了，就算是發(fā)生了碰撞也用O(logn)的tree去做了。僅僅異或一下，既減少了系統(tǒng)的開銷，也不會造成的因為高位沒有參與下標(biāo)的計算(table長度比較小時)，從而引起的碰撞。
如果hashcode發(fā)生碰撞
在Java 8之前，如果發(fā)生碰撞的時候，Hashmap通過鏈表將產(chǎn)生碰撞沖突的元素組織起來，在產(chǎn)生碰撞的情況下，進(jìn)行g(shù)et時，兩步的時間復(fù)雜度是O(1)+O(n)。因此，當(dāng)碰撞很厲害的時候n很大，O(n)的速度顯然是影響速度的。
因此在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認(rèn)是8)，則使用紅黑樹來替換鏈表，這樣復(fù)雜度就變成了O(1)+O(logn)了，這樣在n很大的時候，能夠比較理想的解決這個問題
Rehashing / Resize
當(dāng)put時，如果發(fā)現(xiàn)目前的bucket占用程度已經(jīng)超過了Load Factor所希望的比例，那么就會發(fā)生resize。在resize的過程，簡單的說就是把bucket擴(kuò)充為2倍，之后重新計算index，把節(jié)點再放到新的bucket中。resize的注釋是這樣描述的：
Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是說，當(dāng)超過限制的時候會resize，然而又因為我們使用的是2次冪的擴(kuò)展(指長度擴(kuò)為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置。
例如我們從16擴(kuò)展為32時，具體的變化如下所示：
因此元素在重新計算hash之后，因為n變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：
因此，我們在擴(kuò)充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”?？梢钥纯聪聢D為16擴(kuò)充為32的resize示意圖：
這個設(shè)計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過程，均勻的把之前的沖突的節(jié)點分散到新的bucket了。
下面是代碼的具體實現(xiàn)：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過最大值就不再擴(kuò)充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，就擴(kuò)充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Interview Questions
“你用過HashMap嗎？” “什么是HashMap？你為什么用到它？”
幾乎每個人都會回答“是的”，然后回答HashMap的一些特性，譬如HashMap可以接受null鍵值和值，而Hashtable則不能；HashMap是非synchronized; HashMap很快；以及HashMap儲存的是鍵值對等等。這顯示出你已經(jīng)用過HashMap，而且對它相當(dāng)?shù)氖煜?。但是面試官來個急轉(zhuǎn)直下，從此刻開始問出一些刁鉆的問題，關(guān)于HashMap的更多基礎(chǔ)的細(xì)節(jié)。面試官可能會問出下面的問題：
“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？”
HashMap是基于hashing的原理，使用put(key, value)存儲對象，使用get(key)從HashMap中獲取對象。
- 當(dāng)我們給put()方法傳遞鍵和值時，它調(diào)用key對象的hashCode()方法用于計算HashCode，返回HashCode用于找到bucket位置來儲存Entry對象。HashMap會根據(jù)當(dāng)前bucket的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)。
- 當(dāng)獲取對象時，將key傳給get，它調(diào)用HashCode計算hash從而得到bucket位置，進(jìn)一步通過key對象的equals()方法找到正確的鍵值對，然后返回值對象。如果發(fā)生碰撞，HashMap使用鏈表將對象會儲存在鏈表的下一個節(jié)點中。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象。 在Java8種，如果一個bucket中碰撞沖突的元素超過某個限制(默認(rèn)是8)，則使用紅黑樹來替換鏈表，從而提高速度。
這里關(guān)鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認(rèn)為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。
HashMap中的碰撞探測(collision detection)以及碰撞的解決方法：
“當(dāng)兩個（不同建）對象的hashcode相同會發(fā)生什么？”
因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發(fā)生。因為HashMap使用鏈表存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找鍵值對?！边@個答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡單的，也正是HashMap的處理方法。
“如果兩個鍵的hashcode相同，你如何獲取值對象？”
當(dāng)我們調(diào)用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，找到bucket位置之后，會調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點，最終找到要找的值對象。
許多情況下，面試者會在這個環(huán)節(jié)中出錯，因為他們混淆了hashCode()和equals()方法。因為在此之前hashCode()屢屢出現(xiàn)，而equals()方法僅僅在獲取值對象的時候才出現(xiàn)。
一些優(yōu)秀的開發(fā)者會指出使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發(fā)生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。
如果HashMap的大小超過了負(fù)載因子(load factor)定義的容量，怎么辦？
Load Factor默認(rèn)大小為0.75，也就是說，當(dāng)一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組，來重新調(diào)整map的大小，并將原來的對象放入新的bucket數(shù)組中。這個過程叫作rehashing，因為它調(diào)用hash方法找到新的bucket位置。
你了解重新調(diào)整HashMap大小存在什么問題嗎？
你可能回答不上來，這時面試官會提醒你當(dāng)多線程的情況下，可能產(chǎn)生條件競爭(race condition)。
當(dāng)重新調(diào)整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會同時試著調(diào)整大小。在調(diào)整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了，那么就死循環(huán)了。這個時候，你可以質(zhì)問面試官，為什么這么奇怪，要在多線程的環(huán)境下使用HashMap呢？：）
為什么String, Interger這樣的wrapper類適合作為鍵？
String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。
不可變性是必要的：
- 因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。
- 不可變性還有其他的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。
我們可以使用自定義的對象作為鍵嗎？
這是前一個問題的延伸。當(dāng)然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規(guī)則，并且當(dāng)對象插入到Map中之后將不會再改變了。如果這個自定義對象是不可變的，那么它已經(jīng)滿足了作為鍵的條件，因為當(dāng)它創(chuàng)建之后就已經(jīng)不能改變了。
我們可以使用CocurrentHashMap來代替Hashtable嗎？
這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據(jù)同步級別對map的一部分進(jìn)行上鎖。ConcurrentHashMap當(dāng)然可以代替HashTable，但是HashTable提供更強(qiáng)的線程安全性。看看這篇博客查看Hashtable和ConcurrentHashMap的區(qū)別。
Java8 HashMap有什么性能提升？
Source
HashMap使用key的hashCode()和equals()方法來將值劃分到不同的桶里。桶的數(shù)量通常要比map中的記錄的數(shù)量要稍大，這樣每個桶包括的值會比較少（最好是一個）。當(dāng)通過key進(jìn)行查找時，我們可以在常數(shù)時間內(nèi)迅速定位到某個桶（使用hashCode()對桶的數(shù)量進(jìn)行取模）以及要找的對象。
你可能還知道哈希碰撞會對hashMap的性能帶來災(zāi)難性的影響。如果多個hashCode()的值落到同一個桶內(nèi)的時候，這些值是存儲到一個鏈表中的。最壞的情況下，所有的key都映射到同一個桶中，這樣hashmap就退化成了一個鏈表——查找時間從O(1)到O(n)。
Java 7的結(jié)果是預(yù)料中的。隨著HashMap的大小的增長，get()方法的開銷也越來越大。由于所有的記錄都在同一個桶里的超長鏈表內(nèi)，平均查詢一條記錄就需要遍歷一半的列表，時間復(fù)雜度是O(n)。
不過Java 8的表現(xiàn)要好許多！它是一個log的曲線，因此它的性能要好上好幾個數(shù)量級。盡管有嚴(yán)重的哈希碰撞，已是最壞的情況了，但這個同樣的基準(zhǔn)測試在JDK8中的時間復(fù)雜度是O(logn)。
HashMap會動態(tài)的使用一個專門的treemap實現(xiàn)來替換掉它。這樣做的結(jié)果會更好，是O(logn)，而不是糟糕的O(n)。它是如何工作的？前面產(chǎn)生沖突的那些KEY對應(yīng)的記錄只是簡單的追加到一個鏈表后面，這些記錄只能通過遍歷來進(jìn)行查找。但是超過這個閾值后HashMap開始將列表升級成一個二叉樹，使用哈希值作為樹的分支變量，如果兩個哈希值不等，但指向同一個桶的話，較大的那個會插入到右子樹里。如果哈希值相等，HashMap希望key值最好是實現(xiàn)了Comparable接口的，這樣它可以按照順序來進(jìn)行插入。這對HashMap的key來說并不是必須的，不過如果實現(xiàn)了當(dāng)然最好。如果沒有實現(xiàn)這個接口，在出現(xiàn)嚴(yán)重的哈希碰撞的時候，你就并別指望能獲得性能提升了。
這個性能提升有什么用處？比方說惡意的程序，如果它知道我們用的是哈希算法，它可能會發(fā)送大量的請求，導(dǎo)致產(chǎn)生嚴(yán)重的哈希碰撞。然后不停的訪問這些key就能顯著的影響服務(wù)器的性能，這樣就形成了一次拒絕服務(wù)攻擊（DoS）。JDK 8中從O(n)到O(logn)的飛躍，可以有效地防止類似的攻擊，同時也讓HashMap性能的可預(yù)測性稍微增強(qiáng)了一些。我希望這個提升能最終說服你的老大同意升級到JDK 8來。
HashMap vs HashTable
Source
HashMap和Hashtable的比較是Java面試中的常見問題，用來考驗程序員是否能夠正確使用集合類以及是否可以隨機(jī)應(yīng)變使用多種思路解決問題。HashMap的工作原理、ArrayList與Vector的比較以及這個問題是有關(guān)Java 集合框架的最經(jīng)典的問題。Hashtable是個過時的集合類，存在于Java API中很久了。在Java 4中被重寫了，實現(xiàn)了Map接口，所以自此以后也成了Java集合框架中的一部分。Hashtable和HashMap在Java面試中相當(dāng)容易被問到，甚至成為了集合框架面試題中最常被考的問題，所以在參加任何Java面試之前，都不要忘了準(zhǔn)備這一題。
HashMap和Hashtable都實現(xiàn)了Map接口，主要的區(qū)別有：
- 線程安全
- 同步(synchronization)
- 速度。
- HashMap幾乎可以等價于Hashtable，除了HashMap是非synchronized的，并可以接受null (HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)。
- HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個線程可以共享一個Hashtable；而如果沒有正確的同步的話，多個線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴(kuò)展性更好。
- 另一個區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常。但這并不是一個一定發(fā)生的行為，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別。
- 由于Hashtable是線程安全的也是synchronized，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過Hashtable。
- HashMap不能保證隨著時間的推移Map中的元素次序是不變的。
要注意的一些重要術(shù)語：
- sychronized意味著在一次僅有一個線程能夠更改Hashtable。就是說任何線程要更新Hashtable時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable。
- Fail-safe和iterator迭代器相關(guān)。如果某個集合對象創(chuàng)建了Iterator或者ListIterator，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對象，將會拋出ConcurrentModificationException異常。但其它線程可以通過set()方法更改集合對象是允許的，因為這并沒有從“結(jié)構(gòu)上”更改集合。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改，再調(diào)用set()方法，將會拋出IllegalArgumentException異常。
- 結(jié)構(gòu)上的更改指的是刪除或者插入一個元素，這樣會影響到map的結(jié)構(gòu)。
我們能否讓HashMap同步？
HashMap可以通過下面的語句進(jìn)行同步：
Map m = Collections.synchronizeMap(hashMap);
結(jié)論
Hashtable和HashMap有幾個主要的不同：線程安全以及速度。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用Java 5或以上的話，請使用ConcurrentHashMap吧。
HashMap vs HashSet
Source
HashMap和HashSet都是collection框架的一部分，它們讓我們能夠使用對象的集合。collection框架有自己的接口和實現(xiàn)，主要分為Set接口，List接口和Queue接口。它們有各自的特點，Set的集合里不允許對象有重復(fù)的值，List允許有重復(fù)，它對集合中的對象進(jìn)行索引，Queue的工作原理是FCFS算法(First Come, First Serve)。
首先讓我們來看看什么是HashMap和HashSet，然后再來比較它們之間的分別。
什么是HashSet
HashSet實現(xiàn)了Set接口，它不允許集合中有重復(fù)的值，當(dāng)我們提到HashSet時，第一件事情就是在將對象存儲在HashSet之前，要先確保對象重寫equals()和hashCode()方法，這樣才能比較對象的值是否相等，以確保set中沒有儲存相等的對象。如果我們沒有重寫這兩個方法，將會使用這個方法的默認(rèn)實現(xiàn)。
public boolean add(Object o)方法用來在Set中添加元素，當(dāng)元素值重復(fù)時則會立即返回false，如果成功添加的話會返回true。
什么是HashMap
HashMap實現(xiàn)了Map接口，Map接口對鍵值對進(jìn)行映射。Map中不允許重復(fù)的鍵。Map接口有兩個基本的實現(xiàn)，HashMap和TreeMap。TreeMap保存了對象的排列次序，而HashMap則不能。HashMap允許鍵和值為null。HashMap是非synchronized的，但collection框架提供方法能保證HashMap synchronized，這樣多個線程同時訪問HashMap時，能保證只有一個線程更改Map。
public Object put(Object Key,Object value)方法用來將元素添加到map中。
| HashMap | HashSet |
|---|---|
| HashMap實現(xiàn)了Map接口 | HashSet實現(xiàn)了Set接口 |
| HashMap儲存鍵值對 | HashSet僅僅存儲對象 |
| 使用put()方法將元素放入map中 | 使用add()方法將元素放入set中 |
| HashMap中使用鍵對象來計算hashcode值 | HashSet使用成員對象來計算hashcode值，對于兩個對象來說hashcode可能相同，所以equals()方法用來判斷對象的相等性，如果兩個對象不同的話，那么返回false |
| HashMap比較快，因為是使用唯一的鍵來獲取對象 | HashSet較HashMap來說比較慢 |
因為HashMap的好處非常多，我曾經(jīng)在電子商務(wù)的應(yīng)用中使用HashMap作為緩存。因為金融領(lǐng)域非常多的運用Java，也出于性能的考慮，我們會經(jīng)常用到HashMap和ConcurrentHashMap。
Reference:
Java HashMap工作原理及實現(xiàn)
HashMap的工作原理
Java 8：HashMap的性能提升
HashMap和Hashtable的區(qū)別
HashMap和HashSet的區(qū)別
