這篇文章主要講解了“Java的HashMap和HashTable有什么用”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Java的HashMap和HashTable有什么用”吧！
在婁星等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站建設(shè)、成都做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需網(wǎng)站制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計(jì),成都全網(wǎng)營銷,外貿(mào)網(wǎng)站建設(shè),婁星網(wǎng)站建設(shè)費(fèi)用合理。
HashMap
HashMap也是我們使用非常多的Collection，它是基于哈希表的 Map 接口的實(shí)現(xiàn)，以key-value的形式存在。在HashMap中，key-value總是會當(dāng)做一個(gè)整體來處理，系統(tǒng)會根據(jù)hash算法來來計(jì)算key-value的存儲位置，我們總是可以通過key快速地存、取value。
定義
HashMap實(shí)現(xiàn)了Map接口，繼承AbstractMap。其中Map接口定義了鍵映射到值的規(guī)則，而AbstractMap類提供 Map 接口的骨干實(shí)現(xiàn)，以最大限度地減少實(shí)現(xiàn)此接口所需的工作，其實(shí)AbstractMap類已經(jīng)實(shí)現(xiàn)了Map，這里標(biāo)注Map LZ覺得應(yīng)該是更加清晰吧！
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable
構(gòu)造函數(shù)
HashMap提供了三個(gè)構(gòu)造函數(shù)：
HashMap()：構(gòu)造一個(gè)具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個(gè)帶指定初始容量和加載因子的空 HashMap。
在這里提到了兩個(gè)參數(shù)：初始容量，加載因子。
這兩個(gè)參數(shù)是影響HashMap性能的重要參數(shù)，其中容量表示哈希表中桶的數(shù)量，初始容量是創(chuàng)建哈希表時(shí)的容量，加載因子是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿的一種尺度，它衡量的是一個(gè)散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。
對于使用鏈表法的散列表來說，查找一個(gè)元素的平均時(shí)間是O(1+a)，因此如果負(fù)載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴(yán)重浪費(fèi)。系統(tǒng)默認(rèn)負(fù)載因子為0.75，一般情況下我們是無需修改的。
HashMap是一種支持快速存取的數(shù)據(jù)結(jié)構(gòu)，要了解它的性能必須要了解它的數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)
我們知道在Java中最常用的兩種結(jié)構(gòu)是數(shù)組和模擬指針(引用)，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來組合實(shí)現(xiàn)，HashMap也是如此。實(shí)際上HashMap是一個(gè)“鏈表散列”，如下是它的數(shù)據(jù)結(jié)構(gòu)：
HashMap數(shù)據(jù)結(jié)構(gòu)圖
下圖的table數(shù)組的每個(gè)格子都是一個(gè)桶。負(fù)載因子就是map中的元素占用的容量百分比。比如負(fù)載因子是0.75，初始容量（桶數(shù)量）為16時(shí)，那么允許裝填的元素最大個(gè)數(shù)就是16*0.75 = 12，這個(gè)最大個(gè)數(shù)也被成為閾值，就是map中定義的threshold。超過這個(gè)閾值時(shí)，map就會自動(dòng)擴(kuò)容。
從上圖我們可以看出HashMap底層實(shí)現(xiàn)還是數(shù)組，只是數(shù)組的每一項(xiàng)都是一條鏈。其中參數(shù)initialCapacity就代表了該數(shù)組的長度。下面為HashMap構(gòu)造函數(shù)的源碼：
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能<0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
//初始容量不能 > 最大容量值，HashMap的最大容量值為2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負(fù)載因子不能 < 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
// 計(jì)算出大于 initialCapacity 的最小的 2 的 n 次方值。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//設(shè)置HashMap的容量極限，當(dāng)HashMap的容量達(dá)到該極限時(shí)就會進(jìn)行擴(kuò)容操作
threshold = (int) (capacity * loadFactor);
//初始化table數(shù)組，也就是桶數(shù)組。
table = new Entry[capacity];
init();
}
從源碼中可以看出，每次新建一個(gè)HashMap時(shí)，都會初始化一個(gè)table數(shù)組。table數(shù)組的元素為Entry節(jié)點(diǎn)。
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
.......
}
其中Entry為HashMap的內(nèi)部類，它包含了鍵key、值value、下一個(gè)節(jié)點(diǎn)next，以及hash值，這是非常重要的，正是由于Entry才構(gòu)成了table數(shù)組的項(xiàng)為鏈表。
上面簡單分析了HashMap的數(shù)據(jù)結(jié)構(gòu)，下面將探討HashMap是如何實(shí)現(xiàn)快速存取的。存儲實(shí)現(xiàn)：put(key,vlaue)
首先我們先看源碼
public V put(K key, V value) {
//當(dāng)key為null，調(diào)用putForNullKey方法，保存null與table第一個(gè)位置中，這是HashMap允許為null的原因
if (key == null)
return putForNullKey(value);
//計(jì)算key的hash值，此處對原來元素的hashcode進(jìn)行了再次hash
int hash = hash(key.hashCode()); ------(1)
//計(jì)算key hash 值在 table 數(shù)組中的位置
int i = indexFor(hash, table.length); ------(2)
//從i出開始迭代 e,找到 key 保存的位置
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鏈上是否有hash值相同的(key相同)
//若存在相同，則直接覆蓋value，返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //舊值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回舊值
}
}
//修改次數(shù)增加1
modCount++;
//將key、value添加至i位置處
addEntry(hash, key, value, i);
return null;
}通過源碼我們可以清晰看到HashMap保存數(shù)據(jù)的過程為：首先判斷key是否為null，若為null，則直接調(diào)用putForNullKey方法。
若不為空則先計(jì)算key的hash值，然后根據(jù)hash值搜索在table數(shù)組中的索引位置，如果table數(shù)組在該位置處有元素，則通過比較是否存在相同的key，若存在則覆蓋原來key的value，==否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）==。
若table在該處沒有元素，則直接保存。這個(gè)過程看似比較簡單，其實(shí)深有內(nèi)幕。有如下幾點(diǎn)：
1、 先看迭代處。此處迭代原因就是為了防止存在相同的key值，若發(fā)現(xiàn)兩個(gè)hash值（key）相同時(shí)，HashMap的處理方式是用新value替換舊value，這里并沒有處理key，這就解釋了HashMap中沒有兩個(gè)相同的key。
2、 在看（1）、（2）處。這里是HashMap的精華所在。首先是hash方法，該方法為一個(gè)純粹的數(shù)學(xué)計(jì)算，就是計(jì)算h的hash值。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}我們知道對于HashMap的table而言，數(shù)據(jù)分布需要均勻（最好每項(xiàng)都只有一個(gè)元素，這樣就可以直接找到），不能太緊也不能太松，太緊會導(dǎo)致查詢速度慢，太松則浪費(fèi)空間。計(jì)算hash值后，怎么才能保證table元素分布均與呢？我們會想到取模，但是由于取模的消耗較大，HashMap是這樣處理的：調(diào)用indexFor方法。
static int indexFor(int h, int length) {
return h & (length-1);
}HashMap的底層數(shù)組長度總是2的n次方，在構(gòu)造函數(shù)中存在：capacity <<= 1;這樣做總是能夠保證HashMap的底層數(shù)組長度為2的n次方。當(dāng)length為2的n次方時(shí)，h&(length - 1)就相當(dāng)于對length取模，而且速度比直接取模快得多，這是HashMap在速度上的一個(gè)優(yōu)化。
這是因?yàn)樗麄冊谂c14進(jìn)行&運(yùn)算時(shí)，得到的結(jié)果最后一位永遠(yuǎn)都是0，即0001、0011、0101、0111、1001、1011、1101、1111位置處是不可能存儲數(shù)據(jù)的，空間減少，進(jìn)一步增加碰撞幾率，這樣就會導(dǎo)致查詢速度慢。
而當(dāng)length = 16時(shí)，length – 1 = 15 即1111，那么進(jìn)行低位&運(yùn)算時(shí)，值總是與原來hash值相同，而進(jìn)行高位運(yùn)算時(shí)，其值等于其低位值。所以說當(dāng)length = 2^n時(shí)，不同的hash值發(fā)生碰撞的概率比較小，這樣就會使得數(shù)據(jù)在table數(shù)組中分布較均勻，查詢速度也較快。
這里我們再來復(fù)習(xí)put的流程：當(dāng)我們想一個(gè)HashMap中添加一對key-value時(shí)，系統(tǒng)首先會計(jì)算key的hash值，然后根據(jù)hash值確認(rèn)在table中存儲的位置。若該位置沒有元素，則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值。
如果兩個(gè)hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來節(jié)點(diǎn)的value。如果兩個(gè)hash值相等但key值不等 ，則將該節(jié)點(diǎn)插入該鏈表的鏈頭。具體的實(shí)現(xiàn)過程見addEntry方法，如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//獲取bucketIndex處的Entry
Entry e = table[bucketIndex];
//將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
table[bucketIndex] = new Entry(hash, key, value, e);
//若HashMap中元素的個(gè)數(shù)超過極限了，則容量擴(kuò)大兩倍
if (size++ >= threshold)
resize(2 * table.length);
}這個(gè)方法中有兩點(diǎn)需要注意：
后面添加的entry反而會接到前面。
一、是鏈的產(chǎn)生。
這是一個(gè)非常優(yōu)雅的設(shè)計(jì)。系統(tǒng)總是將新的Entry對象添加到bucketIndex處。如果bucketIndex處已經(jīng)有了對象，那么新添加的Entry對象將指向原有的Entry對象，形成一條Entry鏈，但是若bucketIndex處沒有Entry對象，也就是e==null,那么新添加的Entry對象指向null，也就不會產(chǎn)生Entry鏈了。
二、擴(kuò)容問題。
隨著HashMap中元素的數(shù)量越來越多，發(fā)生碰撞的概率就越來越大，所產(chǎn)生的鏈表長度就會越來越長，這樣勢必會影響HashMap的速度，為了保證HashMap的效率，系統(tǒng)必須要在某個(gè)臨界點(diǎn)進(jìn)行擴(kuò)容處理。
該臨界點(diǎn)在當(dāng)HashMap中元素的數(shù)量等于table數(shù)組長度*加載因子。但是擴(kuò)容是一個(gè)非常耗時(shí)的過程，因?yàn)樗枰匦掠?jì)算這些數(shù)據(jù)在新table數(shù)組中的位置并進(jìn)行復(fù)制處理。所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。
JDK1.8的hashmap：put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node 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 e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果p是紅黑樹節(jié)點(diǎn)，則用另外的處理方法
else if (p instanceof TreeNode)
e = ((TreeNode)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
//當(dāng)鏈表節(jié)點(diǎn)數(shù)超過8個(gè)，則直接進(jìn)行紅黑樹化。
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;
}JDK1.8在鏈表長度超過8時(shí)會轉(zhuǎn)換為紅黑樹。 轉(zhuǎn)換方法如下：
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//如果節(jié)點(diǎn)數(shù)變小小于紅黑樹的節(jié)點(diǎn)數(shù)閾值時(shí)，調(diào)整空間
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
do {
//該方法直接返回一個(gè)紅黑樹結(jié)點(diǎn)。
TreeNode p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
//從鏈表頭開始依次插入紅黑樹
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
// For treeifyBin
TreeNode replacementTreeNode(Node p, Node next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
擴(kuò)容
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果原容量大于最大空間，則讓閾值為最大值。因?yàn)椴荒茉贁U(kuò)容了，最大容量就是整數(shù)最大值。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//兩倍擴(kuò)容，閾值也跟著變?yōu)閮杀?
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);
}
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[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//當(dāng)后面沒有節(jié)點(diǎn)時(shí)，直接插入即可 //每個(gè)元素重新計(jì)算索引位置，此處的hash值并沒有變，只是改變索引值
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
//否則，就從頭到尾依次將節(jié)點(diǎn)進(jìn)行索引然后插入新數(shù)組，這樣插入后的鏈表順序會和原來的順序相反。
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
讀取實(shí)現(xiàn)：get(key)
相對于HashMap的存而言，取就顯得比較簡單了。通過key的hash值找到在table數(shù)組中的索引處的Entry，然后返回該key對應(yīng)的value即可。
public V get(Object key) {
// 若為null，調(diào)用getForNullKey方法返回相對應(yīng)的value
if (key == null)
return getForNullKey();
// 根據(jù)該 key 的 hashCode 值計(jì)算它的 hash 碼
int hash = hash(key.hashCode());
// 取出 table 數(shù)組中指定索引處的值
for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//若搜索的key與查找的key相同，則返回相對應(yīng)的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}在這里能夠根據(jù)key快速的取到value除了和HashMap的數(shù)據(jù)結(jié)構(gòu)密不可分外，還和Entry有莫大的關(guān)系，在前面就提到過，HashMap在存儲過程中并沒有將key，value分開來存儲，而是當(dāng)做一個(gè)整體key-value來處理的，這個(gè)整體就是Entry對象。
同時(shí)value也只相當(dāng)于key的附屬而已。在存儲的過程中，系統(tǒng)根據(jù)key的hashcode來決定Entry在table數(shù)組中的存儲位置，在取的過程中同樣根據(jù)key的hashcode取出相對應(yīng)的Entry對象。
在java中與有兩個(gè)類都提供了一個(gè)多種用途的hashTable機(jī)制，他們都可以將可以key和value結(jié)合起來構(gòu)成鍵值對通過put(key,value)方法保存起來，然后通過get(key)方法獲取相對應(yīng)的value值。
HashTable
一個(gè)是前面提到的HashMap，還有一個(gè)就是馬上要講解的HashTable。對于HashTable而言，它在很大程度上和HashMap的實(shí)現(xiàn)差不多，如果我們對HashMap比較了解的話，對HashTable的認(rèn)知會提高很大的幫助。他們兩者之間只存在幾點(diǎn)的不同，這個(gè)后面會闡述。
定義
HashTable在Java中的定義如下：
public class Hashtable
extends Dictionary
implements Map, Cloneable, java.io.Serializable
從中可以看出HashTable繼承Dictionary類，實(shí)現(xiàn)Map接口。其中Dictionary類是任何可將鍵映射到相應(yīng)值的類（如 Hashtable）的抽象父類。每個(gè)鍵和每個(gè)值都是一個(gè)對象。在任何一個(gè) Dictionary 對象中，每個(gè)鍵至多與一個(gè)值相關(guān)聯(lián)。Map是"key-value鍵值對"接口。
HashTable采用"拉鏈法"實(shí)現(xiàn)哈希表，它定義了幾個(gè)重要的參數(shù)：table、count、threshold、loadFactor、modCount。
table：為一個(gè)Entry[]數(shù)組類型，Entry代表了“拉鏈”的節(jié)點(diǎn)，每一個(gè)Entry代表了一個(gè)鍵值對，哈希表的"key-value鍵值對"都是存儲在Entry數(shù)組中的。
count：HashTable的大小，注意這個(gè)大小并不是HashTable的容器大小，而是他所包含Entry鍵值對的數(shù)量。
threshold：Hashtable的閾值，用于判斷是否需要調(diào)整Hashtable的容量。threshold的值="容量*加載因子"。
loadFactor：加載因子。
modCount：用來實(shí)現(xiàn)“fail-fast”機(jī)制的（也就是快速失?。Ｋ^快速失敗就是在并發(fā)集合中，其進(jìn)行迭代操作時(shí)，若有其他線程對其進(jìn)行結(jié)構(gòu)性的修改，這時(shí)迭代器會立馬感知到，并且立即拋出ConcurrentModificationException異常，而不是等到迭代完成之后才告訴你（你已經(jīng)出錯(cuò)了）。
構(gòu)造方法
在HashTabel中存在5個(gè)構(gòu)造函數(shù)。通過這5個(gè)構(gòu)造函數(shù)我們構(gòu)建出一個(gè)我想要的HashTable。
public Hashtable() {
this(11, 0.75f);
}
默認(rèn)構(gòu)造函數(shù)，容量為11，加載因子為0.75。
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
用指定初始容量和默認(rèn)的加載因子 (0.75) 構(gòu)造一個(gè)新的空哈希表。
public Hashtable(int initialCapacity, float loadFactor) {
//驗(yàn)證初始容量
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//驗(yàn)證加載因子
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
//初始化table，獲得大小為initialCapacity的table數(shù)組
table = new Entry[initialCapacity];
//計(jì)算閥值
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//初始化HashSeed值
initHashSeedAsNeeded(initialCapacity);
}用指定初始容量和指定加載因子構(gòu)造一個(gè)新的空哈希表。其中initHashSeedAsNeeded方法用于初始化hashSeed參數(shù)，其中hashSeed用于計(jì)算key的hash值，它與key的hashCode進(jìn)行按位異或運(yùn)算。這個(gè)hashSeed是一個(gè)與實(shí)例相關(guān)的隨機(jī)值，主要用于解決hash沖突。
private int hash(Object k) {
return hashSeed ^ k.hashCode();
}構(gòu)造一個(gè)與給定的 Map 具有相同映射關(guān)系的新哈希表。
public Hashtable(Map t) {
//設(shè)置table容器大小，其值==t.size * 2 + 1
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}主要方法
HashTable的API對外提供了許多方法，這些方法能夠很好幫助我們操作HashTable，但是這里我只介紹兩個(gè)最根本的方法：put、get。
首先我們先看put方法：將指定 key 映射到此哈希表中的指定 value。注意這里鍵key和值value都不可為空。
public synchronized V put(K key, V value) {
// 確保value不為null
if (value == null) {
throw new NullPointerException();
}
/*
* 確保key在table[]是不重復(fù)的
* 處理過程：
* 1、計(jì)算key的hash值，確認(rèn)在table[]中的索引位置
* 2、迭代index索引位置，如果該位置處的鏈表中存在一個(gè)一樣的key，則替換其value，返回舊值
*/
Entry tab[] = table;
int hash = hash(key); //計(jì)算key的hash值
int index = (hash & 0x7FFFFFFF) % tab.length; //確認(rèn)該key的索引位置
//迭代，尋找該key，替換
for (Entry e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) { //如果容器中的元素?cái)?shù)量已經(jīng)達(dá)到閥值，則進(jìn)行擴(kuò)容操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 在索引位置處插入一個(gè)新的節(jié)點(diǎn)
Entry e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
//容器中元素+1
count++;
return null;
}put方法的整個(gè)處理流程是：計(jì)算key的hash值，根據(jù)hash值獲得key在table數(shù)組中的索引位置，然后迭代該key處的Entry鏈表（我們暫且理解為鏈表），若該鏈表中存在一個(gè)這個(gè)的key對象，那么就直接替換其value值即可，否則在將改key-value節(jié)點(diǎn)插入該index索引位置處。如下：
首先我們假設(shè)一個(gè)容量為5的table，存在8、10、13、16、17、21。他們在table中位置如下：
然后我們插入一個(gè)數(shù)：put(16,22)，key=16在table的索引位置為1，同時(shí)在1索引位置有兩個(gè)數(shù)，程序?qū)υ摗版湵怼边M(jìn)行迭代，發(fā)現(xiàn)存在一個(gè)key=16,這時(shí)要做的工作就是用newValue=22替換oldValue16，并將oldValue=16返回。
在put(33,33)，key=33所在的索引位置為3，并且在該鏈表中也沒有存在某個(gè)key=33的節(jié)點(diǎn)，所以就將該節(jié)點(diǎn)插入該鏈表的第一個(gè)位置。
在HashTabled的put方法中有兩個(gè)地方需要注意：
1、HashTable的擴(kuò)容操作，在put方法中，如果需要向table[]中添加Entry元素，會首先進(jìn)行容量校驗(yàn)，如果容量已經(jīng)達(dá)到了閥值，HashTable就會進(jìn)行擴(kuò)容處理rehash()，如下:
protected void rehash() {
int oldCapacity = table.length;
//元素
Entry[] oldMap = table;
//新容量=舊容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}
//新建一個(gè)size = newCapacity 的HashTable
Entry[] newMap = new Entry[];
modCount++;
//重新計(jì)算閥值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//重新計(jì)算hashSeed
boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
//將原來的元素拷貝到新的HashTable中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry old = oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}在這個(gè)rehash()方法中我們可以看到容量擴(kuò)大兩倍+1，同時(shí)需要將原來HashTable中的元素一一復(fù)制到新的HashTable中，這個(gè)過程是比較消耗時(shí)間的，同時(shí)還需要重新計(jì)算hashSeed的，畢竟容量已經(jīng)變了。
這里對閥值啰嗦一下：比如初始值11、加載因子默認(rèn)0.75，那么這個(gè)時(shí)候閥值threshold=8，當(dāng)容器中的元素達(dá)到8時(shí)，HashTable進(jìn)行一次擴(kuò)容操作，容量 = 8 * 2 + 1 =17，而閥值threshold=17*0.75 = 13，當(dāng)容器元素再一次達(dá)到閥值時(shí)，HashTable還會進(jìn)行擴(kuò)容操作，依次類推。
下面是計(jì)算key的hash值，這里hashSeed發(fā)揮了作用。
private int hash(Object k) {
return hashSeed ^ k.hashCode();
}相對于put方法，get方法就會比較簡單，處理過程就是計(jì)算key的hash值，判斷在table數(shù)組中的索引位置，然后迭代鏈表，匹配直到找到相對應(yīng)key的value,若沒有找到返回null。
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}四、HashTable與HashMap的區(qū)別
HashTable和HashMap存在很多的相同點(diǎn)，但是他們還是有幾個(gè)比較重要的不同點(diǎn)。
第一：我們從他們的定義就可以看出他們的不同，HashTable基于Dictionary類，而HashMap是基于AbstractMap。Dictionary是什么？它是任何可將鍵映射到相應(yīng)值的類的抽象父類，而AbstractMap是基于Map接口的骨干實(shí)現(xiàn)，它以最大限度地減少實(shí)現(xiàn)此接口所需的工作。
第二：HashMap可以允許存在一個(gè)為null的key和任意個(gè)為null的value，但是HashTable中的key和value都不允許為null。如下：
當(dāng)HashMap遇到為null的key時(shí)，它會調(diào)用putForNullKey方法來進(jìn)行處理。對于value沒有進(jìn)行任何處理，只要是對象都可以。
if (key == null)
return putForNullKey(value);
而當(dāng)HashTable遇到null時(shí)，他會直接拋出NullPointerException異常信息。
if (value == null) {
throw new NullPointerException();
}第三：Hashtable的方法是同步的，而HashMap的方法不是。所以有人一般都建議如果是涉及到多線程同步時(shí)采用HashTable，沒有涉及就采用HashMap，但是在Collections類中存在一個(gè)靜態(tài)方法：synchronizedMap()，該方法創(chuàng)建了一個(gè)線程安全的Map對象，并把它作為一個(gè)封裝的對象來返回，所以通過Collections類的synchronizedMap方法是可以我們你同步訪問潛在的HashMap。
感謝各位的閱讀，以上就是“Java的HashMap和HashTable有什么用”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Java的HashMap和HashTable有什么用這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！
網(wǎng)站名稱：Java的HashMap和HashTable有什么用
網(wǎng)站URL：
http://weahome.cn/article/gjgdho.html
重慶分公司
重慶分公司
