1. 引言
許多應用都需要動態集合結構，它至少需要支持Insert，search和delete字典操作。散列表（hash table）是實現字典操作的一種有效的數據結構。
2. 直接尋址表
在介紹散列表之前，我們先介紹直接尋址表。
當關鍵字的全域U（關鍵字的范圍）比較小時，直接尋址是一種簡單而有效的技術。我們假設某應用要用到一個動態集合，其中每個元素的關鍵字都是取自于全域U=｛0，1，…，m-1｝，其中m不是一個很大的數。另外，假設每個元素的關鍵字都不同。
為表示動態集合，我們用一個數組，或稱為直接尋址表（direct-address table），記為T[0~m-1]，其中每一個位置（slot，槽）對應全域U中的一個關鍵字，對應規則是，槽k指向集合中關鍵字為k的元素，如果集合中沒有關鍵字為k的元素，則T[k]=NIL。
幾種字典操作實現起來非常簡單：
上述的每一個操作的時間均為O(1)時間。
在某些應用中，我們其實可以把對象作為元素直接保存在尋址表的槽中，而不需要像上圖所示使用指針指向該對象，這樣可以節省空間。
3. 散列表
我們可以看出，直接尋址技術有幾個明顯的缺點：如果全域U很大，那么表T 將要申請一段非常長的空間，很可能會申請失敗；對于全域較大，但是元素卻十分稀疏的情況，使用這種存儲方式將浪費大量的存儲空間。
為了克服直接尋址技術的缺點，而又保持其快速字典操作的優勢，我們可以利用散列函數（hash function）
h：U→｛0，1，2，…，m-1｝
來計算關鍵字k所在的的位置，簡單的講，散列函數h(k)的作用是將范圍較大的關鍵字映射到一個范圍較小的集合中。這時我們可以說，一個具有關鍵字k的元素被散列到槽h(k)上，或者說h(k)是關鍵字k的散列值。
示意圖如下：
這時會產生一個問題：兩個關鍵字可能映射到同一槽中（我們稱之為沖突（collision）），并且不管你如何優化h(k)函數，這種情況都會發生（因為|U|>m）。
因此我們現在面臨兩個問題，一是遇到沖突時如何解決；二是要找出一個的函數h(k)能夠盡量的減少沖突；
我們先來解決第一個問題。
解決辦法就是，我們把同時散列到同一槽中的元素以鏈表的形式“串聯”起來，而該槽中保存的是指向該鏈表的指針。如下圖所示：
采用該解決辦法后，我們可以通過如下的操作方式來進行字典操作：
下面我們來分析上圖各操作的性能。
首先是插入操作，很明顯時間為O(1)。
然后分析刪除操作，其花費的時間相當于從鏈表中刪除一個元素的時間：如果鏈表T[h(k)]是雙鏈表，花費的時間為O(1)；如果鏈表T[h(k)]是單鏈表，則花費的時間和查找操作的漸進運行時間相同。
下面我們重點分析查找運行時間：
首先，我們假定任何一個給定元素都等可能地散列在散列表T的任何一個槽位中，且與其他元素被散列在T的哪個位置無關。我們稱這個假設為簡單均勻散列（simple uniform hashing）。
不失一般性，我們設散列表T的m個槽位散列了n個元素，則平均每個槽位散列了α = n/m個元素，我們稱α為T的裝載因子（load factor）。我們記位于槽位j的鏈表為T[j]（j=1，2，…，m-1），而nj表示鏈表T[j]的長度，于是有
n = n0+n1+…+nm-1，
且E[nj] = α = n / m。
現在我們分查找成功和查找不成功兩種情況討論。
① 查找不成功
在查找不成功的情況下，我們需要遍歷鏈表T[j]的每一個元素，而鏈表T[j]的長度是α，因此需要時間O(α)，加上索引到T(j)的時間O(1)，總時間為θ(1 + α)。
② 查找成功
在查找成功的情況下，我們無法準確知道遍歷到鏈表T[j]的何處停止，因此我們只能討論平均情況。
我們設xi是散列表T的第i個元素（假設我們按插入順序對散列表T中的n個元素進行了1~n的編號），ki表示xi.key，其中i = 1，2，…，n，再定義隨機變量Xij=I｛h(ki)=h(kj)｝，即：
在簡單均勻散列的假設下有
P｛h(ki)=h(kj)｝ = 1 / m，
E[Xij] = 1 / m。
則所需檢查的元素的數目的期望是：
因此，一次成功的檢查所需要的時間是O(2 + α / 2 –α / 2n) = θ(1 + α)。
綜合上面的分析，在平均下，全部的字典操作都可以在O(1)時間下完成。
4. 散列函數
現在我們來解決第二個問題：如何構造一個好的散列函數。
一個好的散列函數應（近似地）滿足簡單均勻散列：每個關鍵字都等可能的被散列到各個槽位，并與其他關鍵字散列到哪一個槽位無關（但很遺憾，我們一般無法檢驗這一條件是否成立）。
在實際應用中，常?？梢钥梢赃\用啟發式方法來構造性能好的散列函數。設計過程中，可以利用關鍵字分布的有用信息。一個好的方法導出的散列值，在某種程度上應獨立于數據可能存在的任何模式。
下面給出兩種基本的構造散列函數的方法：
除法散列法的做法很簡單，就是讓關鍵字k去除以一個數m，取余數，這樣就將k映射到m個槽位中的某一個，即散列函數是：
h(k) = k mod m ，
由于只做一次除法運算，該方法的速度是非?？斓?。但應當注意的是，我們在選取m的值時，應當避免一些選取一些值。例如，m不應是2的整數冪，因為如果m = 2 ^ p，則h(k)就是k的p個最低位數字。除非我們已經知道各種最低p位的排列是等可能的，否則我們最好慎重的選擇m。而一個不太接近2的整數冪的素數，往往是較好的選擇。
該方法包含兩個步驟。第一步：用關鍵字k乘以A（0 < A < 1），并提取kA的小數部分；第二步：用m乘以這個值，在向下取整，即散列函數是：
h(k) = [m (kA mod 1)]，
這里“kA mod 1”的是取kA小數部分的意思，即kA –[kA]。
乘法散列法的一個優點是，一般我們對m的選擇不是特別的關鍵，一般選擇它為2的整數冪即可。雖然這個方法對任意的A都適用，但Knuth認為，A ≈ （√5 - 1）/ 2 = 0.618033988…是一個比較理想的值
(5) 布隆過濾器
布隆過濾器（Bloom Filter）是一種常被用來檢驗一個元素是否在一個集合里面的算法（從這里我們可以看出，這個集合只需要保存比對元素的“指紋”即可，而不需要保存比對元素的全部信息），由一個很長的二進制向量和一系列隨機映射函數組成。相較于其他算法，它具有空間利用率高，檢測速度快等優點。
在介紹布隆過濾器之前，我們先假設這樣一種場景：某公司致力于解決用戶常常遭遇騷擾電話的問題。該公司打算建立一個騷擾電話號碼的黑名單，即把所有騷擾電話的號碼保存到一張hash表中。當用戶接到某個陌生電話時，服務器會立即將該號碼與黑名單進行比對，若比對成功，則對該號碼進行攔截。
他們當然不會直接將騷擾電話號碼保存在hash表中，而是對每一個號碼利用某種算法進行數據壓縮，最終得到一個8字節的信息指紋，然后將其存入表中。但即便如此，問題還是來了：由于hash表的空間利用率大約只有50%，等價換算過來，儲存一個號碼將要花費16字節的空間。按照這樣計算，儲存1億個號碼將要花費大約1.6G的空間，儲存幾十億的號碼可能需要上百G的空間。那么有沒有更好解決辦法呢？
這時，布隆過濾器就派上用場了。假設我們有1億條騷擾電話號碼需要記錄，我們的做法是，首先建立一個2億字節（即16億位，并假設我們對這16億位以1~16億的順序進行了編號）的向量，將每位都置為0。當要插入某個電話號碼x時，我們使用某種算法（該算法可以做到每個位被映射的概率是一樣的，且某個映射的分布與其他的映射分布無關）讓號碼x映射到1~16億中的8個位上，然后把這8個位設為1。當查找時，利用同樣的方法將號碼映射到8個位上，若這8個位都為1，則說明該號碼在黑名單中，否則就不在。
我們可以發現，布隆過濾器的做法在思想上和hash函數將關鍵字映射到hash表的做法很相似，因此布隆過濾器也會遇到沖突問題，這會導致將一個“好”的號碼誤判為騷擾號碼（但絕對不會將騷擾號碼誤判為一個“好”的號碼）。下面我們通過計算來證明，在大多數情況和場景中，這種誤判我們是可以忍受的。
假設某布隆過濾器共有的m個槽位，我們要把n個號碼添加到其中，而每個號碼會映射k個槽位。那么，添加這n個號碼將會產生kn次映射。因為這m個槽位中，每個槽被映射到的概率是相等的。因此，
在一次映射中，某個槽位被映射到的概率（即該槽位值為1的概率）為
該槽位值為0的概率為
經過kn次映射后，某個槽值為0的概率為
為1的概率為
所以，誤判（k個槽位均為1）的概率就為
利用
，上式可化為：
這時我們注意到，當k=1時，情況就就變成了hash table的情況，
根據自變量的不同我們分以下兩種方式討論：
① 我們把誤判率p看作關于裝載因子α的函數（k看作常數），這時我們從函數
的函數圖像
中可以得出一下結論：
隨著裝載因子α（α = n / m）的增大，誤判率（或者是產生沖突的概率）也將增大，但增長速度逐漸減慢。
要使誤判率小于0.5，裝載因子必須小于0.7。這也從某種程度上解釋了為什么JDK HashMap的裝載因子默認是0.75。
② 我們把誤判率p看作關于k的函數（α作為常數），通過對p求導分析，我們發現，當k=ln2 / α時，誤判率p取得最小值。此時，p = 2^(-k)（或者k = – ln p / ln 2），這個結論讓我們能夠根據可以忍受的誤判率計算出最為合適的k值。
下面給出一個BloomFilter的java實現代碼（來自：https://github.com/MagnusS/Java-BloomFilter，只是把其中的變量和方法名換成了上文提及的）：
public class BloomFilter<E> implements Serializable { PRivate static final long serialVersionUID = -9077350041930475408L; private BitSet bitset;// 二進制向量 private int slotSize; // 二進制向量的總位（槽）數（文中的m） private double loadFactor; // 裝載因子 （文中的α） private int capacity; // 布隆過濾器的容量（文中的n） private int size; // 裝載的數目 private int k; // 一個元素對應的位數（文中的k） static final Charset charset = Charset.forName("UTF-8"); static final String hashName = "md5";// 默認采用MD5算法，也可改為SHA1 static final MessageDigest digestFunction; static { MessageDigest tmp; try { tmp = java.security.MessageDigest.getInstance(hashName); } catch (NoSuchAlgorithmException e) { tmp = null; } digestFunction = tmp; } public BloomFilter(int slotSize, int capacity) { this(slotSize / (double) capacity, capacity, (int) Math.round((slotSize / (double) capacity) * Math.log(2.0))); } public BloomFilter(double falsePositiveProbability, int capacity) { this(Math.log(2) / (Math.ceil(-(Math.log(falsePositiveProbability) / Math.log(2)))),//loadFactor = ln2 / k; capacity, // (int) Math.ceil(-(Math.log(falsePositiveProbability) / Math.log(2)))); //k = -ln p / ln2 } public BloomFilter(int slotSize, int capacity, int size, BitSet filterData) { this(slotSize, capacity); this.bitset = filterData; this.size = size; } public BloomFilter(double loadFactor, int capacity, int k) { size = 0; this.loadFactor = loadFactor; this.capacity = capacity; this.k = k; this.slotSize = (int) Math.ceil(capacity * loadFactor); this.bitset = new BitSet(slotSize); } public static int createHash(String val, Charset charset) { return createHash(val.getBytes(charset)); } public static int createHash(String val) { return createHash(val, charset); } public static int createHash(byte[] data) { return createHashes(data, 1)[0]; } public static int[] createHashes(byte[] data, int hashes) { int[] result = new int[hashes]; int k = 0; byte salt = 0; while (k < hashes) { byte[] digest; synchronized (digestFunction) { digestFunction.update(salt); salt++; digest = digestFunction.digest(data); } for (int i = 0; i < digest.length / 4 && k < hashes; i++) { int h = 0; for (int j = (i * 4); j < (i * 4) + 4; j++) { h <<= 8; h |= ((int) digest[j]) & 0xFF; } result[k] = h; k++; } } return result; } /** * Compares the contents of two instances to see if they are equal. * * @param obj * is the object to compare to. * @return True if the contents of the objects are equal. */ @Override public boolean equals(Object obj) { if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final BloomFilter<E> other = (BloomFilter<E>) obj; if (this.capacity != other.capacity) { return false; } if (this.k != other.k) { return false; } if (this.slotSize != other.slotSize) { return false; } if (this.bitset != other.bitset && (this.bitset == null || !this.bitset.equals(other.bitset))) { return false; } return true; } /** * Calculates a hash code for this class. * * @return hash code representing the contents of an instance of this class. */ @Override public int hashCode() { int hash = 7; hash = 61 * hash + (this.bitset != null ? this.bitset.hashCode() : 0); hash = 61 * hash + this.capacity; hash = 61 * hash + this.slotSize; hash = 61 * hash + this.k; return hash; } /** * Calculates the expected probability of false positives based on the * number of expected filter elements and the size of the Bloom filter. * <br /> * <br /> * The value returned by this method is the <i>expected</i> rate of false * positives, assuming the number of inserted elements equals the number of * expected elements. If the number of elements in the Bloom filter is less * than the expected value, the true probability of false positives will be * lower. * * @return expected probability of false positives. */ public double expectedFalsePositiveProbability() { return getFalsePositiveProbability(capacity); } /** * Calculate the probability of a false positive given the specified number * of inserted elements. * * @param numberOfElements * number of inserted elements. * @return probability of a false positive. */ public double getFalsePositiveProbability(double numberOfElements) { // (1 - e^(-k * n / m)) ^ k return Math.pow((1 - Math.exp(-k * (double) numberOfElements / (double) slotSize)), k); } /** * Get the current probability of a false positive. The probability is * calculated from the size of the Bloom filter and the current number of * elements added to it. * * @return probability of false positives. */ public double getFalsePositiveProbability() { return getFalsePositiveProbability(size); } /** * Returns the value chosen for K.<br /> * <br /> * K is the optimal number of hash functions based on the size of the Bloom * filter and the expected number of inserted elements. * * @return optimal k. */ public int getK() { return k; } /** * Sets all bits to false in the Bloom filter. */ public void clear() { bitset.clear(); size = 0; } /** * Adds an object to the Bloom filter. The output from the object's * toString() method is used as input to the hash functions. * * @param element * is an element to register in the Bloom filter. */ public void add(E element) { add(element.toString().getBytes(charset)); } /** * Adds an array of bytes to the Bloom filter. * * @param bytes * array of bytes to add to the Bloom filter. */ public void add(byte[] bytes) { int[] hashes = createHashes(bytes, k); for (int hash : hashes) bitset.set(Math.abs(hash % slotSize)); size++; } /** * Adds all elements from a Collection to the Bloom filter. * * @param c * Collection of elements. */ public void addAll(Collection<? extends E> c) { for (E element : c) add(element); } /** * Returns true if the element could have been inserted into the Bloom * filter. Use getFalsePositiveProbability() to calculate the probability of * this being correct. * * @param element * element to check. * @return true if the element could have been inserted into the Bloom * filter. */ public boolean contains(E element) { return contains(element.toString().getBytes(charset)); } /** * Returns true if the array of bytes could have been inserted into the * Bloom filter. Use getFalsePositiveProbability() to calculate the * probability of this being correct. * * @param bytes * array of bytes to check. * @return true if the array could have been inserted into the Bloom filter. */ public boolean contains(byte[] bytes) { int[] hashes = createHashes(bytes, k); for (int hash : hashes) { if (!bitset.get(Math.abs(hash % slotSize))) { return false; } } return true; } /** * Returns true if all the elements of a Collection could have been inserted * into the Bloom filter. Use getFalsePositiveProbability() to calculate the * probability of this being correct. * * @param c * elements to check. * @return true if all the elements in c could have been inserted into the * Bloom filter. */ public boolean containsAll(Collection<? extends E> c) { for (E element : c) if (!contains(element)) return false; return true; } /** * Read a single bit from the Bloom filter. * * @param bit * the bit to read. * @return true if the bit is set, false if it is not. */ public boolean getBit(int bit) { return bitset.get(bit); } /** * Set a single bit in the Bloom filter. * * @param bit * is the bit to set. * @param value * If true, the bit is set. If false, the bit is cleared. */ public void setBit(int bit, boolean value) { bitset.set(bit, value); } /** * Return the bit set used to store the Bloom filter. * * @return bit set representing the Bloom filter. */ public BitSet getBitSet() { return bitset; } /** * Returns the number of bits in the Bloom filter. Use count() to retrieve * the number of inserted elements. * * @return the size of the bitset used by the Bloom filter. */ public int slotSize() { return slotSize; } /** * Returns the number of elements added to the Bloom filter after it was * constructed or after clear() was called. * * @return number of elements added to the Bloom filter. */ public int size() { return size; } /** * Returns the expected number of elements to be inserted into the filter. * This value is the same value as the one passed to the constructor. * * @return expected number of elements. */ public int capacity() { return capacity; } /** * Get expected number of bits per element when the Bloom filter is full. * This value is set by the constructor when the Bloom filter is created. * See also getBitsPerElement(). * * @return expected number of bits per element. */ public double getLoadFactor() { return this.loadFactor; }}
新聞熱點
疑難解答
