欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

HashMap和HashTable底層原理以及常見面試題

 更新時間:2019年01月14日 09:46:44   作者:qq_43193797  
今天小編就為大家分享一篇關于HashMap和HashTable底層原理以及常見面試題,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧

1.HashMap VS HashTable

1.1.首先說下 HashMap 的原理。

HashMap 的數(shù)據(jù)結(jié)構(gòu)

/**
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存儲函數(shù)的實現(xiàn)put(K key, V value)

根據(jù)下面put方法的源代碼可以看出,當程序試圖將一個key-value對放入HashMap中時

  • 1.程序首先計算該key的hashCode()值
  • 2.然后對該哈希碼值進行再哈希
  • 3.然后把哈希值和(數(shù)組長度-1)進行按位與操作,得到存儲的數(shù)組下標
  • 4.如果該位置處設有鏈表節(jié)點,那么就直接把包含<key,value>的節(jié)點放入該位置。如果該位置有結(jié)點,就對鏈表進行遍歷,看是否有hash,key和要放入的節(jié)點相同的節(jié)點,如果有的話,就替換該節(jié)點的value值,如果沒有相同的話,就創(chuàng)建節(jié)點放入值,并把該節(jié)點插入到鏈表表頭(頭插法)。
public V put(K key, V value) {
 //HashMap允許存放null鍵和null值。
 //當key為nu11時, 調(diào)用putForNullKey方法,將valve放置在數(shù)組第一個位置。
 if (key = null)
 return putForNullKey(value);
 //根據(jù)key的keyCode重新計算hash值。
 int hash = hash(key .hashCode());
 //搜索指定hash值在對應table中的索
 int i = indexFor(hash, table . length);
 //如果i索引處的Entry不為null,通過循環(huán)不斷遍歷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];
 //將新創(chuàng)健的Entry 放入bucketIndex索引處,并讓新的Entry 指向原來的Entry
 table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
 //如果Hap中的key-value對的數(shù)里超過了極限
 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);
}

擴展:為何數(shù)組的長度是2的n次方呢?

1.這個方法非常巧妙,它通過h & (table.length-1)來得到該對象的保存位,而HashMap底層數(shù)組的長度總是2的n次方,2^n -1得到的二進制數(shù)的每個位上的值都為1,那么與全部為1的一一個數(shù)進行與操作,速度會大大提升。

2.當length總是2的n次方時,h& (length-1)運 算等價王對length取模,也就是h%length,但是&比%縣有更高的效率。

3.當數(shù)組長度為2的n次冪的時候,不同的key算得的index相同的幾率較小,那么數(shù)據(jù)在數(shù)組上分布就比較均勻,也就是說碰擁的幾率小,相對的,查詢的時候就不用遍歷某個位置上的鏈表,這樣查詢效率也就較高了。

HashMap讀取函數(shù)的實現(xiàn)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后的值與數(shù)組的長度-1進行與操作,定位到數(shù)組的某個位置,2. 然后對該列的鏈表進行遍歷,一般情況下,hashMap的這種查找速度是非??斓?,hash 值相同的元(O就會造成鏈表中數(shù)據(jù)很多,而鏈表中的數(shù)據(jù)查找是通過應歷所有鏈表中的元素進行的,這可能會影響到查找速度,找到即返回。特別注意:當返回為null時,你不能判斷是沒有找到指定元素,還是在hashmap中存著一一個value為null的元素,因為hashmap允許value為null.

HashMap的擴容機制:

當HashMap中的結(jié)點個數(shù)超過數(shù)組大小loadEactor*(加載因子)時,就會進行數(shù)組擴容,loadFactor的默認值為0.75.世就是說,默認情況下,數(shù)組大小為16,那么當HashMap電結(jié)點個數(shù)超過160.75=12的時候,就把數(shù)組的大小和展為216=32,即擴大一倍,然后重新計算每個元素在數(shù)組中的位置,并放進去,而這是一個非常消耗性能的操作。

多線程下HashMap出現(xiàn)的問題:

1.多線程put操作后,get操作導致死循環(huán)導致cpu100%的現(xiàn)象。主要是多線程同時put時,如果同時觸發(fā)了rehash操作,會導政擴客后的HashMap中的鏈表中出現(xiàn)循環(huán)節(jié)點進而使得后面get的時候,會死循環(huán)。

2.多線程put操作,導致元素丟失,也是發(fā)生在個線程對hashmap 擴容時。

2.hashTable的原理。

它的原理和hashMap基本一致。

3.HashMap和HashTable的區(qū)別。

1.Hashtable 是線程安全的,方法是Synchronized 的,適合在多線程環(huán)境中使用,效率稍低: HashMap不是線程安全的,方法不是Synchronized的,效率稍高,適合在單線程環(huán)境下使用,所以在多線程場合下使用的話,需要手動同步HashMap,Collctions. synchronizedMap()。

PS:HashTable的效率比較低的原因?

在線程競爭激烈的情況下HashTable的效率非常低下。因為當一個線程訪間HashTable的同步方法時,訪問其他同步方法的線程就可能會進入阻嘉或者輪訓狀態(tài)。如線程1使用put進行添加元素,線程2不但不能使用put方法添加元素,并且也不能使用get方法來獲取元素,所以競爭越激烈改率越低.

2.HashMap的key和value都可以為null值,HashTable 的key和value都不允許L Null值。

3.HashMap中數(shù)組的默認大小是16,而且一定是2的倍數(shù),擴容后的數(shù)組長度是之前數(shù)組長度的2倍。HashTable中數(shù)組默認大小是11.擴容后的數(shù)組長度是之前數(shù)組長度的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(); //注意區(qū)分2者的hash值!! int index = (hash & 0x7FFFFFFF) % tab.length;

4.判斷是否含有某個鍵

在HashMap中,null 可以作為鍵,這樣的鍵只有一個,可以有一個或多個鍵所對應的值為null,當get()方法返回null值時,既可以表示HashMap中沒有該鍵,也可以表示該鍵所對應的值為null。因此,在HashMap中不能用get()方法來判斷HashMap中是否存在某個鍵,而應該用containsKey()方法來判析。Hashtable的鍵值都不能為null,所以可以用get()方 法來判斷是否含有某個鍵。

總結(jié)

以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值,謝謝大家對腳本之家的支持。如果你想了解更多相關內(nèi)容請查看下面相關鏈接

相關文章

  • 深入XPath的詳解以及Java示例代碼分析

    深入XPath的詳解以及Java示例代碼分析

    本篇文章是對XPath進行了詳細的分析介紹,需要的朋友參考下
    2013-06-06
  • Java中對于雙屬性枚舉的使用案例

    Java中對于雙屬性枚舉的使用案例

    今天小編就為大家分享一篇關于Java中對于雙屬性枚舉的使用案例,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • Spring中Bean的命名方式代碼詳解

    Spring中Bean的命名方式代碼詳解

    這篇文章主要介紹了Spring中Bean的命名方式代碼詳解,具有一定借鑒價值,需要的朋友可以參考下
    2018-01-01
  • 詳解如何保證Java本地緩存的一致性

    詳解如何保證Java本地緩存的一致性

    所謂的一致性是指在同時使用緩存和數(shù)據(jù)庫的場景下,要確保數(shù)據(jù)在緩存與數(shù)據(jù)庫中的更新操作保持同步,那么,怎么保證Java本地緩存的一致性?所以本文將給大家介紹了如何保證Java本地緩存的一致性,需要的朋友可以參考下
    2024-01-01
  • Java終止線程實例和stop()方法源碼閱讀

    Java終止線程實例和stop()方法源碼閱讀

    這篇文章主要介紹了Java終止線程實例和stop()方法源碼閱讀,具有一定借鑒價值,需要的朋友可以參考下
    2017-12-12
  • InterProcessMutex實現(xiàn)zookeeper分布式鎖原理

    InterProcessMutex實現(xiàn)zookeeper分布式鎖原理

    本文主要介紹了InterProcessMutex實現(xiàn)zookeeper分布式鎖原理,文中根據(jù)實例編碼詳細介紹的十分詳盡,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • 一文探究ArrayBlockQueue函數(shù)及應用場景

    一文探究ArrayBlockQueue函數(shù)及應用場景

    這篇文章主要為大家介紹了一文探究ArrayBlockQueue函數(shù)及應用場景,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-03-03
  • Java?stream?sorted使用?Comparator?進行多字段排序的方法

    Java?stream?sorted使用?Comparator?進行多字段排序的方法

    這篇文章主要介紹了Java?stream?sorted使用?Comparator?進行多字段排序,主要講解使用Java?Stream流排序器Comparator對List集合進行多字段排序的方法,包括復雜實體對象多字段升降序排序方法,需要的朋友可以參考下
    2023-03-03
  • 從Java的jar文件中讀取數(shù)據(jù)的方法

    從Java的jar文件中讀取數(shù)據(jù)的方法

    這篇文章主要介紹了從Java的jar文件中讀取數(shù)據(jù)的方法,實例分析了java檔案文件的相關操作技巧,需要的朋友可以參考下
    2015-06-06
  • spring配置定時任務的幾種方式總結(jié)

    spring配置定時任務的幾種方式總結(jié)

    這篇文章主要介紹了spring配置定時任務的幾種方式總結(jié),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-12-12

最新評論