最近讀了一篇好文：【微信高并發(fā)資金交易系統(tǒng)設計方案——百億紅包背后的技術支撐】，其中關于高并發(fā)性能問題的解決方案中怎顾，有應用 hash 算法的思想。想起公眾號后臺里斷斷續(xù)續(xù)有讀者提起算法方面的問題，覺得可以寫篇文章聊聊算法中的 hash 算法戳气。順道科普下算法與數(shù)據(jù)結構的重要性句各。
開講前吸占，先跑題閑聊下程序員的技術功底。我常說每個程序員都有自己獨特的技術視野和知識盲區(qū)凿宾，不同程序員之間很難因為某些知識點儲備不一樣而分個高低好壞矾屯。但我們工作當中，又能明顯感覺不同團隊成員之間的技術水平存在差異初厚，到底差在哪呢件蚕？很多人調侃批量生產(chǎn)的培訓程序員，那這些人和四年的大學本科之間又有多少距離产禾？僅僅是時間嗎骤坐？
差在基本功，基本功有很多項下愈，數(shù)據(jù)結構與算法就是其中之一纽绍。雖然是基本功，卻是最難儲備和最易忽視的势似。行業(yè)越浮躁拌夏，變化越快，開發(fā)平臺越便捷履因，高級 API 越多障簿，基本功的重要性就越容易被忽視。即使能意識到基礎薄弱栅迄，肯下定決心騰出幾個月時間惡補基本功不是件容易的事站故，尤其是參加工作后，瑣事繁多，一時熱血下定的決心能堅持一周都屬不易西篓。后臺偶爾有人問及程序員如何進階的問題愈腾，以我這些年所經(jīng)驗，回過頭來夯實下基礎岂津，對大部分人都會有奇效虱黄。
數(shù)據(jù)結構與算法的學習難度經(jīng)常被夸大，不少人甚至談算法色變吮成，尤其無法忍受在面試當中問及算法問題橱乱。其實多點兒耐心，多投入些時間粱甫，學習算法并不難泳叠。至少學習基礎的算法并不難，理解算法和去 leetcode 刷題是兩回事茶宵，刷題所涉及的算法多需要技巧危纫，基礎的算法知識和其他計算機知識一樣，不需要特別「聰明」的大腦节预，大多數(shù)人都能學會叶摄。Peak 君沒刷過題属韧，但對算法方面的知識也比較有自信安拟。
數(shù)據(jù)結構和算法是相輔相成的，基礎的其實就那么些：時間復雜度的概念宵喂，List糠赦，Array，Stack锅棕，Queue拙泽，Tree 等。Graph 實際應用中較少遇到裸燎，可以不做深入了解顾瞻，但 BFS，DFS德绿，Dijkstra 還是應該知道荷荤。基礎的算法需要能達到手寫的程度移稳，比如排序至少能寫出兩種時間復雜度為 N*logN 的算法蕴纳。理解這些比去 leetcode 刷題重要，學習難度也并不高个粱。學習這些的意義在于掌握解決問題的基礎思路古毛，形成計算機思維，比如 divide and conque都许，recursive 等常規(guī)思想稻薇。
再回到本文重點 hash 算法嫂冻。關于 hash 算法的實現(xiàn)原理和關鍵概念，網(wǎng)絡上已有不少好文加以介紹颖低。本文不做原理層面的解釋絮吵，只談應用。對實現(xiàn)感興趣的可以搜索關鍵字：hash忱屑，load factor蹬敲，擴容，hash 沖突解決等莺戒。
Objective C 中對于 hash 的應用主要封裝在兩個數(shù)據(jù)類當中：NSDictionary 和 NSSet伴嗡。這點大家都知道，hash 算法能以空間換時間从铲，在 NSDictionary 和 NSSet 中瘪校，判斷一個元素是否存在只需要 O(1) 的時間復雜度。這一特點也使得在一些需要快速存取元素的場景名段，比如 Cache 設計阱扬，也能看到 NSDictionary 的身影。當然 hash 的應用遠不止如此伸辟，做的應用越多麻惶，解決問題越深入，碰到 hash 算法的概率也會更高信夫。
「The Algorithm Design Manual」一書中提到窃蹋，雅虎的 Chief Scientist ，Udi Manber 曾說過静稻，在 yahoo 所應用的算法中警没，最重要的三個是：hash，hash 和 hash振湾。其重要性不言而喻杀迹。書中還舉了一個很有趣的應用例子，請聽題：
一場拍賣會中押搪，物品是價高者得树酪，如果每個人只有一次出價機會，同時提交自己的價格后嵌言，最后一起公布嗅回，出價最高則勝出。這種形式存在作弊的可能摧茴，如果有出價者能 hack 進后臺绵载，然后將自己的價格改為最高價 + 1，則能以最低的代價獲得勝利。如何杜絕這種作弊呢娃豹？
三分鐘思考時間焚虱，一，二懂版，三鹃栽。
參與者都提交自身出價的 hash 值就可以了，即使有人能黑進后臺也無法得知明文價格躯畴，等到公布之時民鼓，再對比原出價與 hash 值是否對應即可。是不是很巧妙蓬抄？
看到這丰嘉，可能有朋友想到了 MD5，SHA嚷缭。是的饮亏，上面的做法，和我們在 server 端存儲密碼的 MD5 值而非明文阅爽，是同一種思想路幸，殊途同歸。hash 算法包含有多種解決問題的思路付翁，這里可以歸納為【通過 hash简肴，生成不可逆的信息摘要】。
書里還有關于 hash 應用的其他有趣的場景（比如論文內容抄襲檢測）胆敞，都值得一讀着帽。
回到微信紅包的例子杂伟，后臺工程師為了防止搶紅包時移层，用戶的流量都涌進同個服務器，在同個 DB 上讀寫而導致的性能下降赫粥，采用了通過 hash 算法來分流的策略观话。每個紅包創(chuàng)建的時候分配一個 ID，通過算法將 ID 映射到不同的邏輯服務器越平，一氣呵成的解決方案频蛔。這里體現(xiàn)的是 hash 算法的另一種思想：【hash 能以 O（1）的復雜度將內容映射到位置】。這種應用 hash 的思路非常常見秦叛，還有不少例子晦溪。
去年寫過一篇多線程文章【正確使用多線程同步鎖@synchronized()】，當時閱讀 OC 源碼的時候也看到了 hash 的身影挣跋。@synchronized(token) 中的 token 通過 hash 算法存儲到了一份手動維護的 cache 中三圆，cache 的 key 使用的是 token 的內存地址。@synchronized 使用多了之后，如何快速的通過 token 取出對應的鎖舟肉，對多線程的性能至關重要修噪。hash 算法恰能以 O（1）的時間復雜度，以 token 為 key 取出對應的鎖路媚，和上面紅包的例子本質上是同一種思想黄琼。即內容與位置之間的快速映射關系。
我還見到過很多例子整慎，多多少少都有 hash 算法的影子脏款。大家說 hash 算法是不是很重要？數(shù)據(jù)結構與算法是不是要學裤园？不懂算法弛矛，有時候看別人代碼就真如「過眼云煙」了，觀其形而不知其意比然。別人賞雪丈氓，心中所念是：「都城十日雪，庭戶皓已盈」强法，你只能一句「我靠万俗！好美！」以抒胸臆饮怯，豈不煞風景闰歪？
之前有幾位讀者在后臺留言，求算法書推薦蓖墅。算法方面的好書有不少库倘，不過大多是英文的，除去一些專業(yè)術語外论矾，多是一些簡單的詞匯教翩，閱讀難度不算大，維堅持二字贪壳。推薦一本現(xiàn)今還留有印象的：《編程珠璣》饱亿，英文名《Programming Pearls》，不是大部頭闰靴，建議啃英文原版彪笼。
