快捷導(dǎo)航

java HashMap內(nèi)部實(shí)現(xiàn)原理詳解

更新時(shí)間：2017年02月04日 09:59:46 投稿：lqh

這篇文章主要介紹了java HashMap內(nèi)部實(shí)現(xiàn)原理詳解的相關(guān)資料,需要的朋友可以參考下

詳解HashMap內(nèi)部實(shí)現(xiàn)原理

內(nèi)部數(shù)據(jù)結(jié)構(gòu)

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

從上面的數(shù)據(jù)結(jié)構(gòu)定義可以看出，HashMap存元素的是一組鍵值對的鏈表，以什么形式存儲(chǔ)呢

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

可以看出，是以數(shù)組形式儲(chǔ)存，好的，現(xiàn)在我們知道，HashMap是以數(shù)組形式存儲(chǔ)，每個(gè)數(shù)組里面是一個(gè)鍵值對，這個(gè)鍵值對還可以鏈接到下個(gè)鍵值對。如下圖所示:

hashmap的添加

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
      inflateTable(threshold);
    }
    if (key == null)
      return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    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;
  }

這里可以看出，hashmap的添加，首先根據(jù)一個(gè)entry的hash屬性去查找相應(yīng)的table元素i，然后看這個(gè)位置是否有元素存在，如果沒有，直接放入，如果有，遍歷此次鏈表，加到表尾

刪除

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
      return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
      Entry<K,V> next = e.next;
      Object k;
      if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k)))) {
        modCount++;
        size--;
        if (prev == e)
          table[i] = next;
        else
          prev.next = next;
        e.recordRemoval(this);
        return e;
      }
      prev = e;
      e = next;
    }

    return e;
  }

刪除的話，還是先根據(jù)hash在table數(shù)組中查找，然后再根據(jù)equals在鏈表中進(jìn)行查找，這個(gè)也是為什么hashmap和hashset等以hash方式進(jìn)行存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)要求實(shí)現(xiàn)兩個(gè)方法hashcode和equalsd的原因

學(xué)過hash的人都知道，hash表的性能和hash沖突的發(fā)生次數(shù)有很大關(guān)系，但有不能申請過長的table表浪費(fèi)空間，所以這里有了我們的resize函數(shù)

擴(kuò)容機(jī)制

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);
  }

這個(gè)方法會(huì)在put的時(shí)候調(diào)用,上面put的時(shí)候先調(diào)用 addEntry(hash, key, value, i);方法，然后看addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
  }

上面可以看出那么 HashMap 當(dāng) HashMap 中的元素個(gè)數(shù)超過數(shù)組大小 *loadFactor 時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor 的默認(rèn)值為 0.75，這是一個(gè)折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為 16，那么當(dāng) HashMap 中元素個(gè)數(shù)超過 16*0.75=12 的時(shí)候，就把數(shù)組的大小擴(kuò)展為 2*16=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知 HashMap 中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高 HashMap 的性能。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: