搜索中的散列算法用法

Question

我想知道搜索中散列的用法。例如谷歌或雅虎使用哈希算法？大公司是否使用這種散列算法？

Answer 1

是的。請參閱本書的網頁排名和更高版本，在那裏你會發現谷歌使用哈希。哈希讓你的複雜度在所有方面都很低，比如搜索，添加等。讓我告訴你一種情況，假設你正在創建一個在線聊天網站。並且你有可以處理100萬個用戶。你可以使用線性搜索，這將花費大約100萬次的最差時間來獲取一個元素。用戶將不得不在客戶端等待很多。但是，由於您不使用額外空間的複雜性。但如果你將使用哈希時間將只有一個時間獲取一個元素。但在這裏系統將花費你很多，因爲你必須支付額外的存儲空間（100萬條數據存儲記錄具有更好的哈希函數）。但是，這裏面臨的挑戰是要有一個最佳的散列函數，它可以導致最小的碰撞來存儲元素。散列是我無法簡單解釋的一個大問題。請參閱以下鏈接：

What is a good Hash Function?
http://en.wikipedia.org/wiki/Hash_function
http://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson11_2.htm
http://www.tutorialspoint.com/dbms/dbms_hashing.htm
http://www.internetlivestats.com/total-number-of-websites/

谷歌鏈接的網站萬億美元，約1156000000.let我們假設1毫秒從db.In獲得一個頁面最壞的情況下，大約需要1156000000 * 1毫秒= 1156000秒= 5.35年。用戶在最壞的情況下將需要等待5年才能搜索。因此，這不能通過簡單的線性搜索來完成.Google有自己的隱藏複雜算法（您可以在上面的書中找到）.Google有自己的服務器來存儲哈希記錄，從那裏通過使用一些散列函數獲取記錄。我對谷歌的工作原理沒有太多的想法。我所知道的是谷歌使用概率很多。在本書中查找谷歌如何工作 - http://langvillea.people.cofc.edu/UIUC.pdf