1. 哈希表（Hash Table）

(1) 定義

哈希表（Hash Table）：一種不允許值重復(fù)的順序數(shù)據(jù)結(jié)構(gòu)。（散列表）

• 利用 哈希函數(shù)(散列函數(shù)) 生成 key 對應(yīng)的 index【￥】
• 根據(jù) index 操作定位數(shù)組元素【】

哈希表是【空間換時間】的典型應(yīng)用
哈希表內(nèi)部的數(shù)組元素，也稱Bucket(桶)，整個數(shù)組叫Buckets或Bucket Array

哈希表

(2) 哈希沖突（Hash Collision）

哈希沖突（Hash Collision）： 2個不同的key，經(jīng)過 哈希函數(shù) 計算得出相同的結(jié)果（哈希碰撞）

• key1 key2，hash(key1) hash(key2)

哈希沖突的解決辦法：

• 開放地址法：按照一定規(guī)則向其他地址探測，直到遇到空桶
• 再哈希法：設(shè)計多個哈希函數(shù)
• 鏈地址法：比如通過鏈表將同一index的元素串起來

JDK1.8中的哈希表是使用 鏈表+紅黑樹 解決哈希沖突

哈希沖突

哈希沖突解決方法：鏈表+紅黑樹

(3) 哈希函數(shù)

哈希表中 哈希函數(shù) 的實現(xiàn)步驟如下：

• 生成 key的哈希值（必須是整數(shù)）
• 讓 key的哈希值 跟 數(shù)組的大小 進行相關(guān)運算，生成一個索引值

public int hash(Object key) {
    return hash_code(key) % table.length;
}

// 以 &運算 替代 %元素，以提高效率（將數(shù)組長度設(shè)計為2的冪 2^n）
public int hash(Object key) {
    return hash_code(key) & (table.length - 1);
}

良好的哈希函數(shù)

• 讓哈希值更加均勻分布 -> 減少哈希沖突次數(shù) -> 提升哈希表的性能

(4) key的哈希值

key 的常見種類可能有

• 整數(shù)、浮點數(shù)、字符串、自定義對象

不同種類的 key，哈希值的生成方式不一樣，但目標是一致的

• 盡量讓每個 key 的哈希值是唯一的
• 盡量讓 key 的所有信息參與運算

在Java中，HashMap 的 key 必須實現(xiàn) hashCode、equals 方法，也允許 key 為 null

1> 整數(shù)

• 整數(shù)值當(dāng)做哈希值

比如 10 的哈希值就是 10

public static int hashCode(int value) {
    return value;
}

2> 浮點數(shù)

• 將存儲的二進制格式轉(zhuǎn)為整數(shù)值

public static int hashCode(float value) {
    return floatToIntBits(value);
}

3> Long和Double的哈希值

public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}

public static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

>>> 和 ^ 的作用是？

• 高32bit 和 低32bit 混合計算出 32bit 的哈希值
• 充分利用所有信息計算出哈希值

位運算

^ 按位異或運算符 ：參加運算的兩個二進制位相同為0，相異為1

4> 字符串的哈希值

Q：整數(shù) 5489 是如何計算出來的？

• 5 ? 10^3 + 4 ? 10^2 + 8 ? 10^1 + 9 ? 10^0

字符串是由若干個字符組成的

比如字符串 jack，由 j、a、c、k 四個字符組成（字符的本質(zhì)就是一個整數(shù)）

因此，jack 的哈希值可以表示為
j ? n^3 + a ? n^2 + c ? n^1 + k ? n^0

等價于
[ ( j ? n + a ) ? n + c ] ? n + k

Q：在JDK中，乘數(shù) n 為 31，為什么使用 31？

• 31 是一個奇素數(shù)，JVM會將 31 * i 優(yōu)化成 (i << 5) – i

(5) TreeMap vs HashMap

TreeMap適用：

• 元素具備 可比較性 且 要求升序遍歷（按照元素從小到大）

HashMap適用

• 無序遍歷

	TreeMap	HashMap
時間復(fù)雜度（平均）添加、刪除、搜索
key的可比較性	必須具備	不需要
元素的分布	有序	無序