由散列表到BitMap的概念與應用（一）
散列表
提到散列表，大家可能會想到常用的集合HashMap，HashTable等。
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
散列表是種數據結構，它可以提供快速的插入操作和查找操作。第一次接觸散列表時，它的優點多得讓人難以置信。不論散列表中有多少數據，插入和刪除只需要接近常量的時間即O(1）的時間級。實際上，這隻需要幾條機器指令。
對散列表的使用者來說，這是一瞬間的事。散列表運算得非常快，在計算機程序中，如果需要在一秒種內查找上千條記錄通常使用散列表（例如拼寫檢查器)的速度明顯比樹快，樹的操作通常需要O(N)的時間級。散列表不僅速度快，編程實現也相對容易。
散列表也有一些缺點。它是基於數組的，數組創建後難於擴展。某些散列表被基本填滿時，性能下降得非常嚴重，所以程序雖必須要清楚表中將要存儲多少數據（或者準備好定期地把數據轉移到更大的散列表中，這是個費時的過程）。
當我們對某個元素進行哈希運算，得到一個存儲地址，然後要進行插入的時候，發現已經被其他元素佔用了，其實這就是所謂的衝突，也叫哈希碰撞。前面我們提到過，散列函數的設計至關重要，好的散列函數會盡可能地保證計算簡單和散列地址分佈均勻。但是，我們需要清楚的是，數組是一塊連續的固定長度的內存空間，再好的散列函數也不能保證得到的存儲地址絕對不發生衝突。那麼哈希衝突如何解決呢？哈希衝突的解決方案有多種：開放定址法（發生衝突，繼續尋找下一塊未被佔用的存儲地址）、再散列函數法和鏈地址法等，而HashMap即是採用了鏈地址法，也就是數組+鏈表的方式。
下面我們通過HashMap來具體講解散列表的應用以及衝突解決方式。
HashMap實現原理
Java中HashMap的主幹是一個Entry數組。Entry是HashMap的基本組成單元，每一個Entry包含一個key-value鍵值對。
從中，我們可以看出 Entry 實際上就是一個單向鏈表。這也是為什麼我們說HashMap是通過拉鍊法解決哈希衝突的。
簡單來說，HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希衝突而存在的，如果定位到的數組位置不含鏈表（當前entry的next指向null）,那麼對於查找，添加等操作很快，僅需一次尋址即可；如果定位到的數組包含鏈表，對於添加操作，其時間複雜度為O(n)，首先遍歷鏈表，存在即覆蓋，否則新增；對於查找操作來講，仍需遍歷鏈表，然後通過key對象的equals方法逐一比對查找。所以，從性能方面考慮，HashMap中的鏈表出現越少，性能才會越好。
Hash表算法
Hash表的構造方法有多種，包括：直接定址法、除留取餘法、平均取中法、摺疊法、隨機數法和數學分析法等。
直接定址法
取關鍵字key的某個線性函數為散列地址，如
或
A，B為常數。
如：有一個從1到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函數取關鍵字自身。但這種方法效率不高，時間複雜度是O(1)，空間複雜度是O(n)，n是關鍵字的個數。
除留取餘法
關鍵值除以比散列表長度小的素數所得的餘數作為散列地址。Hash(key) = key % p 。
在這裡p的選取非常關鍵，p選擇的好的話，能夠最大程度地減少衝突，p一般取不大於m的最大質數。
平均取中法
先計算構成關鍵碼的標識符的內碼的平方，然後按照散列表的大小取中間的若干位作為散列地址。
如：有以下關鍵字序列{421，423，436}，平方之後的結果為{177241，178929，190096}，那麼可以取{72，89，00}作為Hash地址。
摺疊法
把關鍵碼自左到右分為位數相等的幾部分，每一部分的位數應與散列表地址位數相同，只有最後一部分的位數可以短一些。把這些部分的數據疊加起來，就可以得到具有關鍵碼的記錄的散列地址。分為移位法和分界法。
隨機數法
選擇一個隨機函數，取關鍵字的隨機函數作為它的哈希地址。
，其中random為隨機函數。通常用於關鍵字長度不等時採用此法。
數學分析法
設有N個d位數，每一位可能有r種不同的符號。這r種不同的符號在各位上出現的頻率不一定相同，可能在某些位上分佈均勻些，每種符號出現的機會均等；在某些位上分佈不均勻，只有某幾種符號經常出現。可根據散列表的大小，選取其中各種符號分佈均勻的若干位作為散列地址。
如：一批人的生日數據如下：
年.月.日 95.10.03 95.11.23 96.07.12 95.04.21 96.02.15 ...
經分析,第一位，第二位，第三位重複的可能性大，取這三位造成衝突的機會增加，所以儘量不取前三位，取後三位比較好。
衝突解決
在上面介紹了Hash表的構造方法，儘管有這麼多種方法，但是不同的key值可能會映射到同一散列地址上。這樣就會造成哈希衝突/哈希碰撞。下面我們介紹下Hash表的衝突處理方法。
閉散列方法
又稱為開放定址法，有線性探測和二次探測兩種。
線性探測：當不同的key值通過哈希函數映射到同一散列地址上時，檢測當前地址的下一個地址是否可以插入，如果可以的話，就存在當前位置的下一個地址，否則，繼續向下一個地址尋找，地址++。比如有一組關鍵字{12，13，25，23，38，34，6，84，91}，Hash表長為11，Hash函數為address(key)=key%11，當插入12(hash(12)=1)，13(hash(13)=2)，25(hash(25)=3)時可以直接插入，而當插入23時，地址1被佔用了，因此沿著地址1依次往下探測(探測步長可以根據情況而定，如(hash(23)+1)%11=2,(hash(23)+2)%11=3,(hash(23)+3)%11=4)，直到探測到地址4，發現為空，則將23插入其中。二次探測：是針對線性探測的一個改進，線性探測後插入的key值太集中，這樣造成key值通過散列函數後還是無法正確的映射到地址上，太集中也會造成查找、刪除時的效率低下。因此，通過二次探測的方法，取當前地址加上i^2，可以取到的新的地址就會稍微分散開。(hash(23)+1^2)%11=2,(hash(23)+2^2)%11=5，直到探測到地址5，發現為空，則將23插入其中。再哈希法
當發生衝突時，使用第二個、第三個、哈希函數計算地址，直到無衝突時。這種做法使得計算時間增加。
開鏈法（哈希桶）
當用線性探測和二次探測時，總是在一個有限的哈希表中存儲數據，當數據特別多時，效率就比較低。因此採用拉鍊法的方式來降低哈希衝突。
當一個鏈上鍊的數據過多時，我們可以採用紅黑樹的方式來降低高度，保持平衡且不至於過載。
BitMap
BitMap理解為位圖的意思，用一個Bit位來標記某個元素對應的Value，而Key即是該元素。
在所有具有性能優化的數據結構中，使用最多的就是Hash表。在上一小節已經提到，Hash表具有定位查找上的時間級為O(1)。但是數據量大了，內存就不夠了。由於採用了Bit為單位來存儲數據，因此BitMap在存儲空間方面，可以大大節省。
BitMap算法思想
32位機器上，一個整形，比如int a;在內存中佔32bit位，可以用對應的32bit位對應十進制的0-31個數，BitMap算法利用這種思想處理大量數據的排序與查詢.
優點：
運算效率高，不許進行比較和移位；佔用內存少，比如N=10000000；只需佔用內存為N/8=1250000Byte=1.25M。缺點：所有的數據不能重複。即不可對重複的數據進行排序和查找。
比如：
00000000000000000000000000010100 標註了2和4。
十進制和二進制bit位需要一個map圖，把十進制的數映射到bit位。下面詳細說明這個map映射表。
map映射表
假設需要排序或者查找的總數N=10000000，那麼我們需要申請內存空間的大小為int a[1 + N/32]，其中：a[0]在內存中佔32為可以對應十進制數0-31，依次類推BitMap表為：
a[0]--------->0-31a[1]--------->32-63a[2]--------->64-95a[3]--------->96-127…那麼十進制數如何轉換為對應的bit位，下面介紹用位移將十進制數轉換為對應的bit位。
求十進制0-N對應在數組a中的下標：十進制0-31，對應在a[0]中，先由十進制數n轉換為與32的餘可轉化為對應在數組a中的下標。當n=24，那麼n/32=0，則24對應在數組a中的下標為0。當n=51，那麼n/32=1，則51對應在數組a中的下標為1，同理可以計算0-N在數組a中的下標。求0-N對應0-31中的數：十進制0-31就對應0-31，而32-63則對應也是0-31，即給定一個數n可以通過模32求得對應0-31中的數。利用移位0-31使得對應32bit位為1。BitMap應用
排序
假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這裡假設這些元素沒有重複），我們就可以採用Bit-map的方法來達到排序的目的。要表示8個數，我們就只需要8個Bit（1Bytes），首先我們開闢1Byte的空間，將這些空間的所有Bit位都置為0。
遍歷一遍Bit區域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的，時間複雜度O(n)。
快速去重
2.5億個整數中找出不重複的整數的個數，內存空間不足以容納這2.5億個整數。
內存空間不足以容納這2.5億個整數，我們可以快速的聯想到BitMap。下邊關鍵的問題就是怎麼設計我們的Bit-map來表示這2.5億個數字的狀態了。其實這個問題很簡單，一個數字的狀態只有三種，分別為不存在，只有一個，有重複。因此，我們只需要2bits就可以對一個數字的狀態進行存儲了，假設我們設定一個數字不存在為00，存在一次01，存在兩次及其以上為11。那我們大概需要存儲空間幾十兆左右。
接下來的任務就是遍歷一次這2.5億個數字，如果對應的狀態位為00，則將其變為01；如果對應的狀態位為01，則將其變為11；如果為11，對應的轉態位保持不變。
最後，我們將狀態位為01的進行統計，就得到了不重複的數字個數，時間複雜度為O(n)。
快速查詢
利用BitMap也可以進行快速查詢，這種情況下對於一個數字只需要一個bit位就可以了，0表示不存在，1表示存在。假設上述的題目改為，如何快速判斷一個數字是夠存在於上述的2.5億個數字集合中。
同之前一樣，首先我們先對所有的數字進行一次遍歷，然後將相應的轉態位改為1。遍歷完以後就是查詢，由於我們的BitMap採取的是連續存儲（整型數組形式，一個數組元素對應32bits），我們實際上是採用了一種分桶的思想。一個數組元素可以存儲32個狀態位，那將待查詢的數字除以32，定位到對應的數組元素（桶），然後再求餘（%32），就可以定位到相應的狀態位。如果為1，則代表改數字存在；否則，該數字不存在。
單使用BitMap有時候是不夠的，如果數據量大到一定程度，如64bit類型的數據，這時候用BitMap？所需要的存儲大小：
1PB=1024TB，1TB=1024GB。而EB（Exabyte，艾字節）這個計算機科學中統計數據量的單位有多大，1EB=1024PB。這個量級的BitMap，已經不是人類硬件所能承擔的了。所以Bitmap的好處在於空間複雜度不隨原始集合內元素的個數增加而增加，而它的壞處也源於這一點——空間複雜度隨集合內最大元素增大而線性增大。
所以接下來，我們要引入另一個著名的工業實現——布隆過濾器（Bloom Filter）。如果說Bitmap對於每一個可能的整型值，通過直接尋址的方式進行映射，相當於使用了一個哈希函數，那布隆過濾器就是引入了k(k>1)k(k>1)個相互獨立的哈希函數，保證在給定的空間、誤判率下，完成元素判重的過程。下圖中是k=3時的布隆過濾器。
布隆過濾器的其中一種應用就是緩存雪崩。
總結
本文首先講解了散列表的相關概念和應用。Hash表實際上為每一個可能出現的數字提供了一個一一映射的關係，每個元素都相當於有了自己的獨享的一份空間，這個映射由散列函數來提供。Hash表甚至還能記錄每個元素出現的次數，利用這一點可以實現更復雜的功能。
我們的需求是集合中每個元素有一個獨享的空間並且能找到一個到這個空間的映射方法。獨享的空間對於我們的問題來說，一個Boolean就夠了，或者說，1個bit就夠了，我們只想知道某個元素出現過沒有。如果為每個所有可能的值分配1個bit，32bit的int所有可能取值需要內存空間為：
。由此引出BitMap算法。我們介紹了BitMap算法的思想和部分應用，包括排序、去重、查詢等應用，BitMap在這些大數據量上的應用都很高效。Bloom filter可以看做是對BitMap的擴展。更大數據量的有一定誤差的用來判斷映射是否重複的算法。關於布隆過濾器的具體應用細節，內容較多，將會在下篇文章具體介紹。
最後，歡迎購買筆者的新書《Spring Cloud微服務架構進階》
https://item.jd.com/12453340.html。
參考
哈希表（閉散列、拉鍊法--哈希桶）BitMap大數據處理-Bitmap