HashMap中的幾個(gè)重要變量

默認(rèn)初始容量,必須是2的n次方

static final int DEFAULT_INITIAL_CAPACITY = 16;

最大容量，當(dāng)通過(guò)構(gòu)造方法傳入的容量比它還大時(shí)，就用這個(gè)最大容量，必須是2的n次方

static final int MAXIMUM_CAPACITY = 1 << 30;

默認(rèn)負(fù)載因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

用來(lái)存儲(chǔ)鍵值對(duì)，可以看到鍵值對(duì)都是存儲(chǔ)在Entry中的

transient Entry<K,V>[] table;

//capacity * load factor,超過(guò)這個(gè)數(shù)就會(huì)進(jìn)行再哈希
int threshold;

HashMap中的元素是用名為table的Entry數(shù)組來(lái)保存的，默認(rèn)大小是16

• capacity:數(shù)組的容量
• load_factor:負(fù)載因子
• threshold：實(shí)際能承載的容量，等于上面兩個(gè)相乘，當(dāng)size大于threshold時(shí)，就會(huì)進(jìn)行rehash
  

jdk7中在面對(duì)key為String的時(shí)候采用了區(qū)別對(duì)待，會(huì)有alternative hashing，但是這個(gè)在jdk8中已經(jīng)被刪除了

存儲(chǔ)結(jié)構(gòu)

Entry是一個(gè)鏈表結(jié)構(gòu)，不僅包含key和value，還有可以指向下一個(gè)的next

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

 /**
  * Creates new entry.
  */
 Entry(int h, K k, V v, Entry<K,V> n) {
  value = v;
  next = n;
  key = k;
  hash = h;
 }
 ...

put方法

public V put(K key, V value) {
 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;
 }

首先通過(guò)hash方法對(duì)hashcode進(jìn)行處理：

final int hash(Object k) {
 int h = 0;
 h ^= k.hashCode();

 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }

可以看到只是在key的hashcode值上做了一些處理，通過(guò)hash計(jì)算出來(lái)的值將會(huì)使用indexFor方法找到它應(yīng)該所在的table下標(biāo)：

static int indexFor(int h, int length) {
 return h & (length-1);
 }

這個(gè)方法其實(shí)相當(dāng)于對(duì)table.length取模。

當(dāng)需要插入的key為null時(shí)，調(diào)用putForNullKey方法處理：

 private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null) {
  V oldValue = e.value;
  e.value = value;
  e.recordAccess(this);
  return oldValue;
  }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
 }

putForNullKey方法只從table[0]這個(gè)位置開(kāi)始遍歷，因?yàn)閗ey為null只放在table中的第一個(gè)位置，下標(biāo)為0，在遍歷中如果發(fā)現(xiàn)已經(jīng)有key為null了，則替換新value，返回舊value，結(jié)束；如果還沒(méi)有key為null，調(diào)用addEntry方法增加一個(gè)Entry:

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

可以看到j(luò)dk7中resize的條件已經(jīng)發(fā)生改變了，只有當(dāng) size>=threshold并且 table中的那個(gè)槽中已經(jīng)有Entry時(shí)，才會(huì)發(fā)生resize。即有可能雖然size>=threshold，但是必須等到每個(gè)槽都至少有一個(gè)Entry時(shí)，才會(huì)擴(kuò)容。還有注意每次resize都會(huì)擴(kuò)大一倍容量

void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
 }

最后看createEntry，它先保存這個(gè)桶中的第一個(gè)Entry，創(chuàng)建新的Entry放入第一個(gè)位置，將原來(lái)的Entry接在后面。這里采用的是頭插法插入元素。

get方法

其實(shí)get方法和put方法如出一轍，怎么放的怎么拿

public V get(Object key) {
 if (key == null)
  return getForNullKey();
 Entry<K,V> entry = getEntry(key);

 return null == entry ? null : entry.getValue();
 }

key為null時(shí)，還是去table[0]去取：

private V getForNullKey() {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
  if (e.key == null)
  return e.value;
 }
 return null;
 }

否則調(diào)用getEntry方法：

final Entry<K,V> getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key);
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
  e != null;
  e = e.next) {
  Object k;
  if (e.hash == hash &&
  ((k = e.key) == key || (key != null && key.equals(k))))
  return e;
 }
 return null;
 }

這個(gè)方法也是通過(guò)key的hashcode計(jì)算出它應(yīng)該所在的下標(biāo)，再遍歷這個(gè)下標(biāo)的Entry鏈，如果key的內(nèi)存地址相等（即同一個(gè)引用）或者equals相等，則說(shuō)明找到了

hash的原則

A、等冪性。不管執(zhí)行多少次獲取Hash值的操作，只要對(duì)象不變，那么Hash值是固定的。如果第一次取跟第N次取不一樣，那就用起來(lái)很麻煩.

B、對(duì)等性。若兩個(gè)對(duì)象equal方法返回為true，則其hash值也應(yīng)該是一樣的。舉例說(shuō)明：若你將objA作為key存入HashMap中，然后new了一個(gè)objB。在你看來(lái)objB和objA是一個(gè)東西（因?yàn)樗麄僥qual），但是使用objB到hashMap中卻取不出來(lái)東西。

C、互異性。若兩個(gè)對(duì)象equal方法返回為false，hash值有可能相同，但最好是不同的，這個(gè)不是必須的，只是這樣做會(huì)提高h(yuǎn)ash類操作的性能（碰撞幾率低）。

解決hash碰撞的方法：

• 開(kāi)放地址法
• 鏈地址法

hashmap采用的就是鏈地址法，這種方法好處是無(wú)堆積現(xiàn)象，但是next指針會(huì)占用額外空間

和jdk8中的HashMap區(qū)別

在jdk8中，仍然會(huì)根據(jù)key.hashCode()計(jì)算出hash值，再通過(guò)這個(gè)hash值去定位這個(gè)key，但是不同的是，當(dāng)發(fā)生沖突時(shí)，會(huì)采用鏈表和紅黑樹(shù)兩種方法去處理，當(dāng)結(jié)點(diǎn)個(gè)數(shù)較少時(shí)用鏈表（用Node存儲(chǔ)），個(gè)數(shù)較多時(shí)用紅黑樹(shù)（用TreeNode存儲(chǔ)），同時(shí)結(jié)點(diǎn)也不叫Entry了，而是分成了Node和TreeNode。再最壞的情況下，鏈表查找的時(shí)間復(fù)雜度為O(n),而紅黑樹(shù)一直是O(logn),這樣會(huì)提高HashMap的效率。jdk8中的HashMap中定義了一個(gè)變量TREEIFY_THRESHOLD，當(dāng)節(jié)點(diǎn)個(gè)數(shù)>= TREEIFY_THRESHOLD - 1時(shí)，HashMap將采用紅黑樹(shù)存儲(chǔ)

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流。

最新評(píng)論