溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1．HashMap VS HashTable
1.1.首先說下 HashMap 的原理。
HashMap 的數據結構
/**
The table, resized as necessary. Length MUST Always be a power of two.
**/
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V>{
final K key;
V value;
Entry<K,V> next;
final int hash;
...
}
HashMap存儲函數的實現put(K key, V value)
根據下面put方法的源代碼可以看出，當程序試圖將一個key-value對放入HashMap中時
public V put(K key, V value) {
//HashMap允許存放null鍵和null值。
//當key為nu11時， 調用putForNullKey方法，將valve放置在數組第一個位置。
if (key = null)
return putForNullKey(value);
//根據key的keyCode重新計算hash值。
int hash = hash(key .hashCode());
//搜索指定hash值在對應table中的索
int i = indexFor(hash, table . length);
//如果i索引處的Entry不為null,通過循環不斷遍歷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;
}
}
//如果讀引處的Entry為null，表明此處還沒有Entry
omodCount++;
//將key、 value添加到索引處。
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//獲取指定bucketIndex 索引處的Entry
Entry<K,V> e = table[bucketIndex];
//將新創健的Entry 放入bucketIndex索引處，并讓新的Entry 指向原來的Entry
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//如果Hap中的key-value對的數里超過了極限
if (size++ >= threshold)
//把table對象的長度擴充到原理的2倍
resize(2*table.length);
}
二倍擴容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
static int hash(int h){
h ^ =(h>>>20)^ (h>>>12);
return h ^ (h>>>7) ^ (h>>>4);
}
擴展:為何數組的長度是2的n次方呢?
1.這個方法非常巧妙，它通過h & (table.length-1)來得到該對象的保存位，而HashMap底層數組的長度總是2的n次方，2^n -1得到的二進制數的每個位上的值都為1,那么與全部為1的一一個數進行與操作，速度會大大提升。
2.當length總是2的n次方時，h& (length-1)運 算等價王對length取模，也就是h%length,但是&比%縣有更高的效率。
3.當數組長度為2的n次冪的時候，不同的key算得的index相同的幾率較小，那么數據在數組上分布就比較均勻，也就是說碰擁的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。
HashMap讀取函數的實現get
public V get(object key) {
if (key = null)
return getForNullKey();
int hash ”hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table. length)];
e!=null;
e = e.next) {
0bject k;
if (e.hash=hash && ((k=e.key)==key II key.equals(k)){
return e.value;
}
return null;
}
hashMap的get方法1. 是首先通過key的兩次hash后的值與數組的長度-1進行與操作，定位到數組的某個位置，2. 然后對該列的鏈表進行遍歷，一般情況下，hashMap的這種查找速度是非常快的，hash 值相同的元(O就會造成鏈表中數據很多，而鏈表中的數據查找是通過應歷所有鏈表中的元素進行的，這可能會影響到查找速度，找到即返回。特別注意:當返回為null時，你不能判斷是沒有找到指定元素，還是在hashmap中存著一一個value為null的元素，因為hashmap允許value為null.
HashMap的擴容機制:
當HashMap中的結點個數超過數組大小loadEactor*(加載因子)時，就會進行數組擴容,loadFactor的默認值為0.75.世就是說，默認情況下，數組大小為16，那么當HashMap電結點個數超過160.75=12的時候，就把數組的大小和展為216=32,即擴大一倍，然后重新計算每個元素在數組中的位置，并放進去，而這是一個非常消耗性能的操作。
多線程下HashMap出現的問題:
1.多線程put操作后，get操作導致死循環導致cpu100%的現象。主要是多線程同時put時，如果同時觸發了rehash操作，會導政擴客后的HashMap中的鏈表中出現循環節點進而使得后面get的時候，會死循環。
2.多線程put操作，導致元素丟失，也是發生在個線程對hashmap 擴容時。
2.hashTable的原理。
它的原理和hashMap基本一致。
3.HashMap和HashTable的區別。
1.Hashtable 是線程安全的，方法是Synchronized 的，適合在多線程環境中使用，效率稍低: HashMap不是線程安全的，方法不是Synchronized的，效率稍高，適合在單線程環境下使用，所以在多線程場合下使用的話，需要手動同步HashMap，Collctions. synchronizedMap()。
PS:HashTable的效率比較低的原因?
在線程競爭激烈的情況下HashTable的效率非常低下。因為當一個線程訪間HashTable的同步方法時，訪問其他同步方法的線程就可能會進入阻嘉或者輪訓狀態。如線程1使用put進行添加元素，線程2不但不能使用put方法添加元素，并且也不能使用get方法來獲取元素，所以競爭越激烈改率越低.
2.HashMap的key和value都可以為null值，HashTable 的key和value都不允許L Null值。
3.HashMap中數組的默認大小是16，而且一定是2的倍數，擴容后的數組長度是之前數組長度的2倍。HashTable中數組默認大小是11.擴容后的數組長度是之前數組長度的2倍+1。
4.哈希直的使用不同。
而HashMap重新計算hash值，面且用&代替求模:
int hash = hash(key.hashcode0);
int i= indexFor(hash, table.length);
static int hash(Objectx) {
int h = x.hashCode();
h += ~(h<<9);h^= (h>>> 14);
h+=(h<< 4);
h ^= (h>>> 10);
returm h;
}
static int indexFor(int h, int length) {
return h & (length-1); //hashmap的表長永遠是2^n。
}
HashTable直接使用對象的hashCode值:
int hash = key.hashCode(); //注意區分2者的hash值!! int index = (hash & 0x7FFFFFFF) % tab.length;
4.判斷是否含有某個鍵
在HashMap中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為null,當get()方法返回null值時，既可以表示HashMap中沒有該鍵，也可以表示該鍵所對應的值為null。因此，在HashMap中不能用get()方法來判斷HashMap中是否存在某個鍵，而應該用containsKey()方法來判析。Hashtable的鍵值都不能為null,所以可以用get()方 法來判斷是否含有某個鍵。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對億速云的支持。如果你想了解更多相關內容請查看下面相關鏈接
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
