想在一大堆資料裡找某一筆,一個個翻太慢。雜湊的點子是用一條固定公式把「鑰匙」直接算成一個格子編號, 存進去和找回來都一步到位——像行李按護照號碼分進對應的置物櫃,不必一格格找。這頁比較兩種用法: 雜湊表(Hash Table)把完整資料放進格子,能準確答出某個鍵對應什麼值;布隆過濾器(Bloom Filter)更省, 連東西本體都不存、只在牆上打幾個記號,用極少空間回答「一定沒有」或「可能有」——寧可偶爾誤報也絕不漏報。 下面你可以一步步看鑰匙怎麼被算進格子,以及碰撞與偽陽性是怎麼發生的。
兩者都靠雜湊函數把任意鍵映射到固定大小的容器，但回答的問題不同：雜湊表是精確型集合，儲存完整鍵值， 以鏈結串列處理碰撞，能準確回答「這個鍵對應的值是什麼」；布隆過濾器是機率型集合，只存 0/1 位元、不存鍵值本身， 以極省空間換來「可能存在／一定不存在」的機率性回答，且必須承擔偽陽性（誤判存在）的風險，但絕無偽陰性。
以「桶陣列 + 鏈結串列」處理碰撞：getIndex(key) = |key.hashCode()| % capacity（本例為整數鍵，Java Integer.hashCode() 即值本身，故 index = key % 8）；put 先走鏈比對是否已有相同 key（有則更新 value），否則於鏈頭插入新節點； get/remove 同樣先走鏈比對，找不到則回傳 null（miss）。碰撞集中在同一桶時需走訪整條鏈，平均 O(1)、最差 O(n)。
以 m 個位元 + k 個雜湊函數運作：add(item) 對每個 i=0..k-1 計算 index = getHash(item,i)，把 bits[index] 設為 1； mightContain(item) 同樣計算 k 個 index，只要遇到某位元為 0 就能提早判定「一定不存在」，k 個位元皆為 1 才回傳「可能存在」。 本頁 k 個雜湊函數以雙重雜湊法模擬：hash_i = hash1 + i·hash2（hash1 = Java String.hashCode()、hash2 = FNV-1a， 皆以 32-bit 溢位語意運算），因此不同字串仍可能被映射到完全相同的 k 個位元位置 —— 這正是偽陽性的成因。