HashMap這些問題你知道嗎？

  • 2019 年 10 月 3 日
  • 筆記

HashMap是Java面試中的常考點之一，而且其<Key,Value>結構也是開發中常常用到的結構之一。或許你使用過HashMap，但是你知道下面這些問題嗎？

  • HashMap的底層結構是什麼？

如果你能說出是數組+鏈表，那麼你知道1.8版本之後引入的紅黑樹嗎?

  • 說道紅黑樹，你知道它的結構嗎？

你知道紅黑樹，那麼你知道它是結合平衡二叉樹和2-3樹優點的產物嗎？亦或者你知道這兩種樹的結構嗎？

  • 既然你知道樹的索引結構，那麼你了解過各種資料庫的索引結構嗎？

你或許知道類似於MySql使用的B+樹結構，那麼你知道為什麼要使用這種結構嗎？而且問題反繞回來，為什麼HashMap使用了紅黑樹而不是B+樹？為什麼資料庫中使用的是B+樹？

  • HashMap的擴容機制了解嗎？另外你知道為什麼HashMap容量要保持2的N次方嗎？

  • HashMap不是執行緒安全，那麼你知道主要發生執行緒不安全的情況是什麼嗎？

那麼從這裡開始，讓我們過一遍這些問題。

索引

  • HashMap的底層結構是什麼？
  • 從2-3樹開始看紅黑樹
    • 2-3樹
    • 紅黑樹
  • 你知道各類資料庫的索引結構嗎？
  • 資料庫為什麼選擇B+樹索引？HashMap為什麼選擇紅黑樹索引？
  • HashMap的擴容機制了解嗎？另外你知道為什麼HashMap容量要保持2的N次方嗎？
  • HashMap執行緒不安全的主要情況是什麼？
  • 小彩蛋

HashMap的底層結構是什麼？

這個問題需要從JDK的版本來說，早在JDK1.7及其引入HashMap之前，HashMap使用的結構是數組+鏈表，使用這個結構的原因主要與Hash演算法有關。HashMap的目的是為了讓數據訪問能夠達到複雜度只有O(1)的級別，它是<Key,Value>的結構，在我們存儲時，將key值使用Hash演算法獲得一個hashcode，這個hashcode就是value在HashMap的數組中的下標位置，當我們要查詢某一個key對應的value時，只需要經過一次Hash就可以得到下標位置，而不用經過繁瑣的遍歷。

因為不同對象經過Hash之後可能得到同樣的hashcode，所以這裡使用了鏈表結構，當我們命中同一個下標時就需要通過鏈表來擴充了。

1

如果一個Hash函數設計的不太精妙，或者插入的數據本身有問題，那麼就會出現一個hashcode多次命中的情況，這種情況下我們得到數組下標之後，還需要去遍歷這個鏈表來得到具體的value。在這種情況下會影響到HashMap的訪問速度。

所以在JDK1.8時，為了提高效率引入了紅黑樹結構，不過紅黑樹是在鏈表長度達到8(默認值)時，並且table的長度不小於64(否則擴容一次)時，才會將這條鏈錶轉換為紅黑樹。

假設hash衝突非常嚴重，一個數組後面接了很長的鏈表，此時重新的時間複雜度就是 O(n)。如果是紅黑樹，時間複雜度就是 O(logn)。

2

在開始下一個問題之前，在這裡貼出一段HashMap的源碼，這裡有幾個關鍵的地方需要了解。

/**   * The default initial capacity - MUST be a power of two.   */  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

DEFAULT_INITIAL_CAPACITY是指默認初始容量，這是我們直接new HashMap()之後給出的數組的大小。

/**   * The load factor used when none specified in constructor.   */  static final float DEFAULT_LOAD_FACTOR = 0.75f;

DEFAULT_LOAD_FACTOR叫做負載因子，負載因子*當前容器的大小決定了容器的擴容時機，比如當前容量是16，負載因子是0.75，那麼負載因子*當前容器的大小 = 16*0.75 = 12，當使用超過12時，就會進行一次容器擴容。

/**   * The maximum capacity, used if a higher value is implicitly specified   * by either of the constructors with arguments.   * MUST be a power of two <= 1<<30.   */  static final int MAXIMUM_CAPACITY = 1 << 30;

MAXIMUM_CAPACITY是最大擴容容量。

/**   * The bin count threshold for using a tree rather than list for a   * bin.  Bins are converted to trees when adding an element to a   * bin with at least this many nodes. The value must be greater   * than 2 and should be at least 8 to mesh with assumptions in   * tree removal about conversion back to plain bins upon   * shrinkage.   */  static final int TREEIFY_THRESHOLD = 8;

TREEIFY_THRESHOLD是鏈表長度達到此值時轉換為紅黑樹的值。

/**   * The bin count threshold for untreeifying a (split) bin during a   * resize operation. Should be less than TREEIFY_THRESHOLD, and at   * most 6 to mesh with shrinkage detection under removal.   */  static final int UNTREEIFY_THRESHOLD = 6;

UNTREEIFY_THRESHOLD是當執行resize操作時，紅黑樹中節點少於此值時退化為鏈表。

/**   * The smallest table capacity for which bins may be treeified.   * (Otherwise the table is resized if too many nodes in a bin.)   * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts   * between resizing and treeification thresholds.   */  static final int MIN_TREEIFY_CAPACITY = 64;

MIN_TREEIFY_CAPACITY是在轉變成樹之前，還會有一次判斷，只有鍵值對數量大於64才會發生轉換。這是為了避免在哈希表建立初期，多個鍵值對恰好被放入了同一個鏈表中而導致不必要的轉化。

/**   * The table, initialized on first use, and resized as   * necessary. When allocated, length is always a power of two.   * (We also tolerate length zero in some operations to allow   * bootstrapping mechanics that are currently not needed.)   */  transient Node<K,V>[] table;

table就是所謂的數組。

從2-3樹開始看紅黑樹

2-3樹

你應該知道二叉查找樹，我們可以將二叉樹的一個節點多保存一個鍵，並且稱它為2-節點。多添加兩個鍵，稱它為3-節點。

jiedian

2-結點，含有一個鍵(及其對應的值)和兩條鏈接，左鏈接指向的2-3樹中的鍵都小於該結點，右鏈接指向的2-3樹中的鍵都大於該結點。

3-結點，含有兩個鍵(及其對應的值)和三條鏈接，左鏈接指向的2-3樹中的鍵都小於該結點，中鏈接指向的2-3樹中的鍵都位於該結點的兩個鍵之間，右鏈接指向的2-3樹中的鍵都大於該結點。

指向一棵空樹的鏈接稱為空鏈接。

一棵完美平衡的2-3查找樹中的所有空鏈接到根結點的距離都應該是相同的。

那麼問題來了，2-3樹有什麼意義？

不知道你有沒有發現，二叉查找樹存在的缺點，雖然它查找一個節點很快，但是它有著很大的缺點，就是在插入新的節點時，需要對整個二叉樹進行調整。

而二叉查找樹不一樣，當我們要插入新的節點時，如果查找結束於一個2-節點，可以將一個2-節點轉換為3-節點，從而避免了平衡操作。

charu

如果查找結束於一個3-節點，可以將一個3-節點轉換為3個2-節點。

3-charu

如果要向一個父結點為2-結點的3-結點中插入新值，可以將這個3-節點轉換為3個2-節點，然後將其中一個2-節點與父節點的2-節點合併為3-節點。

4-charu

可以發現2-3樹在擁有高效查找的情況下還擁有插入的高效。

紅黑樹

紅黑樹背後的基本思想是用標準的二叉查找樹(完全由2-節點構成)和一些額外的資訊(替換3-節點)來表示2-3樹。樹種的鏈接分為兩種類型：紅鏈接將兩個2-節點連接起來構成一個3-節點，黑連接則是2-3樹中的普通鏈接。確切來說，將3-節點表示為由一個左斜的紅色鏈接連接兩個2-節點。這種情況下，我們的紅黑樹就可以直接使用標準二叉樹的get方法來查找節點，在插入節點時，我們可以對節點進行轉換，派生出一顆對應的2-3樹。

rbtree

可以發現：

  • 紅鏈接均為左鏈接
  • 沒有任何一個結點同時和兩條紅鏈接相連

你可以將紅黑樹畫平，就可以發現其中奧妙。

pin

紅黑樹會有一個所謂的難點，就是旋轉，想必你曾經因為這個問題很是惱火，那麼從2-3樹的角度來看看旋轉的本質吧。

左旋 右旋
o_zuoxuan1 o_youxuan1
o_zuoxuan2 o_youxuan1

左旋右旋的本質目的，就是為了保證紅色鏈接均為左鏈接。

你知道各類資料庫的索引結構嗎？

這裡要介紹有二叉查找樹,平衡二叉樹,B-Tree,B+-Tree,Hash結構。

  • 二叉查找樹

每個節點最多只有兩個子樹的結構。對於一個節點來說，他的左子樹節點小於他，右子樹節點大於他。

ec

  • 平衡二叉樹

在二叉樹的基礎上，他的任意一個節點的左子樹高度均不超過1。

但是二叉樹因為每個節點只有兩個子節點，所以樹的高度非常高，IO次數也會增大，有時候效率並沒有全表掃描高。所以這時候就需要B-Tree了。

  • B-Tree

img

每個節點最多有m個孩子,m階B樹。根節點至少包括兩個孩子,樹中每個節點最多包含有m個孩子，所有葉子節點都位於同一層。目的是為了讓每一個索引塊儘可能多的存儲更多的資訊，儘可能減少IO次數。

  • B+-Tree

樹中節點指針與關鍵字數目一樣，且數據均在葉子節點中。

img

所以B+Tree更適合用來做索引存儲，磁碟讀寫代價低，查詢效率穩定。這也是Mysql所使用的索引，而且Mysql為了增加查詢速度，引入了DATA指針，可以直接訪問底層數組。

  • Hash索引

通過Hash運算直接定位到目標。

hash

  • BitMap點陣圖索引

修改數據時對其他數據影響極大。

img

這類索引目前只有Oracle使用了。

資料庫為什麼選擇B+樹索引？HashMap為什麼選擇紅黑樹索引？

這個問題的答案是因為磁碟。

資料庫的查詢是位於磁碟，讀取到數據之後存儲到索引結構中。

HashMap是位於記憶體中。

而磁碟和記憶體的數據讀取有很大差異，磁碟每次讀取的最小單位是一簇，他可以是2、4、8、16、32或64個扇區的數據。而記憶體我們可以按照位來讀取。

這種情況下我們在資料庫中使用紅黑樹，建立的索引可能會龐大到無法想像，而在HashMap中使用B+樹，對於HashMap頻繁的插入操作，B+樹無疑是要頻繁進行修改的。

HashMap的擴容機制了解嗎？另外你知道為什麼HashMap容量要保持2的N次方嗎？

HashMap擴容的主要情況是當前的容量達到負載因子*容器容量。

負載因子的默認值是0.75，使用這個值的原因是太小時沒有擴容的必要，太大時才擴容會影響性能，所以選擇了0.75這個值。

另一個問題是HashMap為什麼要保持容量為2的N次方的容量。

可以當作是為了防止hash求值碰撞的問題。在使用2的N次方容量時，數組下標的求取擁有很高的散列程度。

這個是之前看到的一篇文章。

1

左邊兩組是數組長度為16（2的4次方），右邊兩組是數組長度為15。兩組的hashcode均為8和9，但是很明顯，當它們和1110與的時候，產生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就產生了碰撞，8和9會被放到同一個鏈表上，那麼查詢的時候就需要遍歷這個鏈表，得到8或者9，這樣就降低了查詢的效率。

同時，我們也可以發現，當數組長度為15的時候，hashcode的值會與14（1110）進行與，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！

所以說，當數組長度為2的n次冪的時候，不同的key算得得index相同的幾率較小，那麼數據在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。

HashMap執行緒不安全的主要情況是什麼？

HashMap執行緒不安全的主要情況是在擴容時，調用resize()方法里的rehash()時，容易出現環形鏈表。

這樣當獲取一個不存在的key時，計算出的index正好是環形鏈表的下標時就會出現死循環。

rehash操作是重建內部數據結構，從而哈希表將會擴容兩倍。通常，默認載入因子(0.75)在時間和空間成本上尋求一種折衷。載入因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數 HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點）。在設置初始容量時應該考慮到映射中所需的條目數及其載入因子，以便最大限度地減少 rehash 操作次數。如果初始容量大於最大條目數除以載入因子，則不會發生 rehash 操作。
如果很多映射關係要存儲在 HashMap 實例中，則相對於按需執行自動的 rehash 操作以增大表的容量來說，使用足夠大的初始容量創建它將使得映射關係能更有效地存儲。

1

小彩蛋

static final int hash(Object key) {      int h;      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  }

這是HashMap的hash函數，不知道你有沒有發現^ (h >>> 16)這個操作。

^ (h >>> 16)的目的就是因為hashcode的高16位在hashcode中其實並沒有多大作用，為了讓這16位也起到作用，這裡將hash與它自己的高16位亦或，讓高16位也參與hash運算中。

VirMach 便宜 VPS

QNews

QNews