《數(shù)據(jù)結構與算法之美》，王爭 著

標簽：數(shù)據(jù)結構、算法

第4章 哈希表、位圖和哈希算法

一、哈希

作者在哈希（又稱散列表）這個小節(jié)，介紹下面的內容：

• 哈希思想：什么是哈希

• 哈希函數(shù)：什么是哈希函數(shù)和哈希沖突

• 哈希沖突：解決哈希沖突的兩種常用方法：開放尋址法和鏈表法

• 哈希表：如何打造一個工業(yè)級的哈希表：?設計哈希函數(shù)、解決裝載因子過大的問題、避免低效的擴容、選擇合適的沖突解決策略、工業(yè)級的哈希表（Java HashMap）舉例分析

• 哈希表：如何利用哈希表優(yōu)化LRU緩存淘汰算法

?二、位圖

通過如何實現(xiàn)網頁爬蟲中的網址鏈接去重功能的三種解決方案

哈希表、位圖和布魯姆過濾器的簡述比較，給讀者引出了位圖和布魯姆過濾器兩個強大的東西（有實際工業(yè)背景的東西）。這是一般數(shù)據(jù)結構教材不會出現(xiàn)的。

?三、哈希算法

本節(jié)從實戰(zhàn)的角度，如何應用哈希算法來解決問題（安全加密、唯一標識、數(shù)據(jù)校驗、哈希函數(shù)、負載均衡、數(shù)據(jù)分片、分布式存儲）。雖然文字篇幅不多，但是感謝作者的收集和匯總。

?

這一節(jié)，最大的特色是給讀者列出了很多哈希（哈希表和哈希算法兩個分別是數(shù)據(jù)結構和算法中很有代表性的東西，常規(guī)教材講的不多，考試一般考的也不難，課程實現(xiàn)一般沒有）可以解決的實際問題，是對常規(guī)教材和課程中哈希內容的補充，同時對讀者了解哈希的實際應用以及面試也是很有幫助的。

簡單說，很多開發(fā)語言和平臺，都有哈希表可以使用；哈希表和哈希函數(shù)的應用范圍和可解決的問題是非常多的。