天天看點
傳回

HashMap - 哈希表TreeMap分析HashMaphashHash CollisionputcontainsKeycontainsValue擴容

文章目錄

  • TreeMap分析
  • HashMap
  • hash
    • Long和Double的哈希值
    • 字元串的哈希值
      • 關于31的探讨
    • 擾動計算
    • 自定義對象作為key
  • Hash Collision
    • JDK1.8的哈希沖突解決方案
  • put
  • containsKey
  • containsValue
  • 擴容

TreeMap分析

内部通過紅黑樹實作節點存儲Entity映射

◼ 時間複雜度（平均）

添加、删除、搜尋：O(logn)

◼ 特點

Key 必須具備可比較性

元素的分布是有順序的

◼ 在實際應用中，很多時候的需求

Map 中存儲的元素不需要講究順序

Map 中的 Key 不需要具備可比較性

◼ 不考慮順序、不考慮 Key 的可比較性，Map 有更好的實作方案，平均時間複雜度可以達到 O(1)

那就是采取哈希表來實作 Map

HashMap

通過哈希表實作Map

HashMap - 哈希表TreeMap分析HashMaphashHash CollisionputcontainsKeycontainsValue擴容

◼ 添加、搜尋、删除的流程都是類似的

  1. 利用哈希函數生成 key 對應的 index【O(1)】
  2. 根據 index 操作定位數組元素【O(1)】

◼ 哈希表是【空間換時間】的典型應用

◼ 哈希函數，也叫做散列函數

◼ 哈希表内部的數組元素，很多地方也叫 Bucket（桶），整個數組叫 Buckets 或者 Bucket Array

hash

  1. 先生成 key 的哈希值（必須是整數）
  2. 再讓 key 的哈希值跟數組的大小進行相關運算，生成一個索引值

◼ 良好的哈希函數

讓哈希值更加均勻分布 → 減少哈希沖突次數 → 提升哈希表的性能

✓ 盡量讓每個 key 的哈希值是唯一的

✓ 盡量讓 key 的所有資訊參與運算

◼ 為了提高效率，可以使用 & 位運算取代 % 運算**【前提：将數組的長度設計為 2 的幂（ 2n ）】**

1100 1010 1011 1100
& 1111 & 1111
1010 1100

Long和Double的哈希值

◼ >>> 和 ^ 的作用是？

高32bit 和 低32bit 混合計算出 32bit 的哈希值

充分利用所有資訊計算出哈希值

value 1111 1111 1111 1111 1111 1111 1111 1111 1011 0110 0011 1001 0110 1111 1100 1010
value >>> 32 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 1111 1111 1111
value ^ (value >>> 32) 1111 1111 1111 1111 1111 1111 1111 1111 0100 1001 1100 0110 1001 0000 0011 0101

字元串的哈希值

首先類比5489的計算

◼ 整數 5489 是如何計算出來的？

 5 ∗ 103 + 4 ∗ 102 + 8 ∗ 101 + 9 ∗ 100

◼ 字元串是由若幹個字元組成的

比如字元串 jack，由 j、a、c、k 四個字元組成（字元的本質就是一個整數）

是以，jack 的哈希值可以表示為 j ∗ n3 + a ∗ n2 + c ∗ n1 + k ∗ n0 ，等價于 [ ( j ∗ n + a ) ∗ n + c ] ∗ n + k 在JDK中，乘數 n 為 31，為什麼使用 31？

✓ 31 是一個奇素數，JVM會将 31 * i 優化成 (i << 5) – i

關于31的探讨

◼ 31 * i = (2^5 – 1) * i = i * 2^5 – i = (i << 5) – i

◼ 31不僅僅是符合2^n – 1，它是個奇素數（既是奇數，又是素數，也就是質數）

素數和其他數相乘的結果比其他方式更容易産成唯一性，減少哈希沖突

最終選擇31是經過觀測分布結果後的選擇

如果哈希值太大，整型溢出怎麼辦？

✓ 不用作任何處理（相當于隻保留）

擾動計算

無論key是哪種類型，重新計算hash值

h = key.hashCode();
(h ^ (h >>> 16)) & (table.length - 1); // 其實在對hash值進行高低位混合計算

自定義對象作為key

◼ 自定義對象作為 key，最好同時重寫 hashCode 、equals 方法

equals ：用以判斷 2 個 key 是否為同一個 key

✓ 自反性：對于任何非 null 的 x，x.equals(x)必須傳回true

✓ 對稱性：對于任何非 null 的 x、y，如果 y.equals(x) 傳回 true，x.equals(y) 必須傳回 true

✓ 傳遞性：對于任何非 null 的 x、y、z，如果 x.equals(y)、y.equals(z) 傳回 true，那麼x.equals(z)必須傳回 true

✓ 一緻性：對于任何非 null 的 x、y，隻要 equals 的比較操作在對象中所用的資訊沒有被修改，多次調用x.equals(y) 就會一緻地傳回 true，或者一緻地傳回 false

✓ 對于任何非 null 的 x，x.equals(null) 必須傳回 false

hashCode ：必須保證 equals 為 true 的 2 個 key 的哈希值一樣

反過來 hashCode 相等的 key，不一定 equals 為 true

◼ 不重寫 hashCode 方法隻重寫 equals 會有什麼後果？

✓ 可能會導緻 2 個 equals 為 true 的 key 同時存在哈希表中

Hash Collision

HashMap - 哈希表TreeMap分析HashMaphashHash CollisionputcontainsKeycontainsValue擴容

2 個不同的 key，經過哈希函數計算出相同的結果

key1 ≠ key2 ，hash(key1) = hash(key2)

◼ 解決哈希沖突的常見方法

  1. 開放定址法（Open Addressing）

    ✓ 按照一定規則向其他位址探測，直到遇到空桶

  2. 再哈希法（Re-Hashing）

    ✓ 設計多個哈希函數

  3. 鍊位址法（Separate Chaining）

    ✓ 比如通過連結清單将同一index的元素串起來

JDK1.8的哈希沖突解決方案

◼ 預設使用單向連結清單将元素串起來

◼ 在添加元素時，可能會由單向連結清單轉為紅黑樹來存儲元素

比如當哈希表容量 ≥ 64 且 單向連結清單的節點數量大于 8 時

◼ 當紅黑樹節點數量少到一定程度時，又會轉為單向連結清單

◼ JDK1.8中的哈希表是使用連結清單+紅黑樹解決哈希沖突

◼ 思考：這裡為什麼使用單連結清單？

每次都是從頭節點開始周遊

  • 當确定到同一索引處，通過比較equals，确定是否為同一entity
  • 是以一定要從頭開始逐個比較
  • 更新

單向連結清單比雙向連結清單少一個指針，可以節省記憶體空間

put

先不考慮擴容

  • 當計算得到的索引的bucket為空時

    說明紅黑樹為空，直接添加

  • 當bucket非空時
    • 如果之前加入過相同key，覆寫
    • 沒有加入過，添加

先實作根據key查找對應節點

// 由key計算出索引，再到相應bucket查找
	private Node<K, V> node(K key) {
		Node<K, V> root = table[index(key)];
		return root == null ? null : node(root, key);
	}

實作查找key最簡單的方式：

  • 最簡單的查找結點實作

    直接比較是否equals，不equals再去去掃描，并且隻要找不到，就預設添加到紅黑樹的右子節點

  • 優化一

    為了減少遞歸查找調用，每次從紅黑樹的根節點開始比較時

    通過比較存在相同的key【cmp = 0】，覆寫，之後退出循環

    當最終不存在這個key時【cmp != 0】，遞歸比較目前結點和它的所有子節點，如果沒有找到，那麼預設繼續和右子節點比較

    對于之後的節點，如果掃描過，記錄下來和都已經比較過，即目前節點和其子樹都不存在key，那麼預設

do {
		K k2 = node.key;
		if (Objects.equals(k1, k2)) {
			cmp = 0;
		} else if (searched) { // 下面就是既not equals 就不具備可比較性，那就掃描查找存不存在 // 已經掃描了
			cmp = 1 
		} else { // searched == false; 還沒有掃描，然後再根據記憶體位址大小決定左右
			if ((node.left != null && (result = node(node.left, k1)) != null) // 在左邊找到
					|| (node.right != null && (result = node(node.right, k1)) != null)) { // 在右邊找到
				// 已經存在這個key
				node = result;
				cmp = 0;
			} else { // 不存在這個key
				searched = true; // 當掃描到目前節點時，找不到
				cmp = 1
			}
		}
		
		if (cmp > 0) {
			node = node.right;
		} else if (cmp < 0) {
			node = node.left;
		} else { // 相等，覆寫
			V oldValue = node.value;
			node.key = key;
			node.value = value;
			node.hash = h1;
			return oldValue;
		}
	} while (node != null);
           
public V put(K key, V value) {
		int index = index(key);
		// 取出index位置的紅黑樹根節點
		Node<K, V> root = table[index];
		if (root == null) {
			root = new Node<>(key, value, null);
			table[index] = root;
			size++;
			afterPut(root);
			return null;
		}
		
		// 添加新的節點到紅黑樹上面
		Node<K, V> parent = root;
		Node<K, V> node = root;
		int cmp = 0;
		K k1 = key;
		int h1 = k1 == null ? 0 : k1.hashCode();
		Node<K, V> result = null;
		boolean searched = false; // 是否已經搜尋過這個key
		do {
			parent = node;
			K k2 = node.key;
			int h2 = node.hash;
			if (h1 > h2) {
				cmp = 1;
			} else if (h1 < h2) {
				cmp = -1;
			} else if (Objects.equals(k1, k2)) {
				cmp = 0;
			} else if (k1 != null && k2 != null 
					&& k1.getClass() == k2.getClass()
					&& k1 instanceof Comparable
					&& (cmp = ((Comparable) k1).compareTo(k2)) != 0) { // 如果隻是大小相等，cmp==0，是不能确定equals是以要掃描

			} else if (searched) { // 下面就是既not equals 就不具備可比較性，那就掃描查找存不存在 // 已經掃描了
				cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
			} else { // searched == false; 還沒有掃描，然後再根據記憶體位址大小決定左右
				if ((node.left != null && (result = node(node.left, k1)) != null) // 在左邊找到
						|| (node.right != null && (result = node(node.right, k1)) != null)) { // 在右邊找到
					// 已經存在這個key
					node = result;
					cmp = 0;
				} else { // 不存在這個key
					searched = true; // 當掃描到目前節點時，找不到
					cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
				}
			}
			
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {
				node = node.left;
			} else { // 相等，覆寫
				V oldValue = node.value;
				node.key = key;
				node.value = value;
				node.hash = h1;
				return oldValue;
			}
		} while (node != null);

		// 看看插入到父節點的哪個位置
		Node<K, V> newNode = new Node<>(key, value, parent);
		if (cmp > 0) {
			parent.right = newNode;
		} else {
			parent.left = newNode;
		}
		size++;
		
		// 新添加節點之後的處理
		afterPut(newNode);
		return null;
	}

  • 優化二

    先比較hash，并增加規則

    再比較equals，not equals再比較

    無可比較性，再掃描

    并且随機向紅黑樹左右子樹添加

do {
			parent = node;
			K k2 = node.key;
			int h2 = node.hash;
			if (h1 > h2) {
				cmp = 1;
			} else if (h1 < h2) {
				cmp = -1;
			} else if (Objects.equals(k1, k2)) {
				cmp = 0;
			} else if (k1 != null && k2 != null 
					&& k1.getClass() == k2.getClass()
					&& k1 instanceof Comparable
					&& (cmp = ((Comparable) k1).compareTo(k2)) != 0) { // 如果隻是大小相等，cmp==0，是不能确定equals是以要掃描

			} else if (searched) { // 下面就是既not equals 就不具備可比較性，那就掃描查找存不存在 // 已經掃描了
				cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
			} else { // searched == false; 還沒有掃描，然後再根據記憶體位址大小決定左右
				if ((node.left != null && (result = node(node.left, k1)) != null) // 在左邊找到
						|| (node.right != null && (result = node(node.right, k1)) != null)) { // 在右邊找到
					// 已經存在這個key
					node = result;
					cmp = 0;
				} else { // 不存在這個key
					searched = true; // 當掃描到目前節點時，找不到
					cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
				}
			}
			
			if (cmp > 0) {
				node = node.right;
			} else if (cmp < 0) {
				node = node.left;
			} else { // 相等，覆寫
				V oldValue = node.value;
				node.key = key;
				node.value = value;
				node.hash = h1;
				return oldValue;
			}
		} while (node != null);

containsKey

紅黑樹中都是存放的node

是以根據key查找node實作containsKey

優化

  1. 添加時先比較hash值，大的放右邊

    是以，查找時也先從右邊找

  2. 再比較是否equals

  3. 再通過比較性，判斷向左子樹還是右子樹繼續查找

    【比較性】大小相等，cmp==0，不代表找到key，隻有equals才可以确定

private Node<K, V> node(K key) {
		Node<K, V> root = table[index(key)];
		return root == null ? null : node(root, key);
	}
	
	// 在node所在的根結點的紅黑樹中找
	private Node<K, V> node(Node<K, V> node, K k1) {
		int h1 = hash(k1);
		// 存儲查找結果
		Node<K, V> result = null;
		int cmp = 0;
		while (node != null) {
			K k2 = node.key;
			int h2 = node.hash;
			// 添加時先比較hash值，大的放右邊
			// 是以，查找時也先從右邊找
			if (h1 > h2) {
				node = node.right;
			} else if (h1 < h2) {
				node = node.left;
			} else if (Objects.equals(k1, k2)) { // hashcode相等
				return node; // equals相等，找到
			} else if (k1 != null && k2 != null 
				&& k1.getClass() == k2.getClass()
				&& k1 instanceof Comparable
				&& (cmp = ((Comparable) k1).compareTo(k2)) != 0) {
				node = cmp > 0 ? node.right : node.left;
			} else if (node.right != null && (result = node(node.right, k1)) != null) { // 不具備可比較性，向右子樹查找
				return result; // 在右子樹找到key
			} else { // 右邊掃描找不到，隻能往左邊找
				node = node.left;
			}
//			} else if (node.left != null && (result = node(node.left, k1)) != null) { 
//				return result; // 把left傳參，等價于把left指派node循環
//			} else {
//				return null;
//			}
		}
		return null;
	}

containsValue

value可以是任意的，是以隻能周遊掃描

這裡采用了層序查找

public boolean containsValue(V value) {
		if (size == 0) return false;
		Queue<Node<K, V>> queue = new LinkedList<>();
		for (int i = 0; i < table.length; i++) { // bucket
			if (table[i] == null) continue;
			
			queue.offer(table[i]);
			while (!queue.isEmpty()) { // RBTree
				Node<K, V> node = queue.poll();
				if (Objects.equals(value, node.value)) return true;
				
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
		return false;
	}

擴容

◼ 裝填因子（Load Factor）：節點總數量 / 哈希表桶數組長度，也叫做負載因子

◼ 在JDK1.8的HashMap中，如果裝填因子超過0.75，就擴容為原來的2倍

當擴容為原來容量的2倍時,節點的索引有2種情況

  1. 保持不變
  2. index = index+舊容量 
一開始容量為2^2
1010
& 11
----
  10

1110
& 11
----
  10


擴容為2^3

1010
&111
----
 010

1110
&111
----
 110

Reference：小碼哥MJ

dsa # Tree
上一篇: libxml庫之xmlParseMemory和xmlDocDumpFormatMemory函數
下一篇: 二叉樹周遊應用preorderinorderpostorderlevel orderisCompleteheight

繼續閱讀