在上一篇綜述中,我給出了排序是為了更快的查找這個觀點.也介紹了查找的一些典型應用場景如:
1.判斷一個給定值,是否在一個數組
2.mysql 的查詢優化
3.再到給定a、b兩個文件，各存放50億個url，每個url各佔64字節，內存限制是4G，找出a、b文件共同的url.
也簡單的介紹了兩種查找的方法:
一是遍歷查找:
也叫順序查找,思路為 遍歷整個列表，逐個進行記錄的關鍵字與給定值比較，若某個記錄的關鍵字和給定值相等，則查找成功，找到所查的記錄。如果直到最後一個記錄，其關鍵字和給定值比較都不等時，則表中沒有所查的記錄，查找失敗。
這個萌蠢的查找思想,是選擇排序的基礎,不過這裡空白太小,我寫不下,容我後面再說.
二是二分查找:
也叫折半查找,思路為 在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續查找；若給定值大於中間記錄的關鍵字，則在中間記錄的右半區繼續查找。不斷重複上述過程，直到找到為止。
二分查找,要求查找的數列是有序的. 於是,又引入了一個問題,如何排序? ---- 不過同樣的,這裡空白太小,我寫不下.
費馬老爺子
還有其他的諸如 索引查找, 二叉樹查找, 哈希查找等方法, 這裡我講講哈希查找,其他的查找方法,如果您有興趣瞭解-----那等我有興趣寫就可以了.....
就你皮
哈希(hash),翻譯過來叫散列.定義一個函數 F = f(ꭓ) , 對於不同的 ꭓ ,得到不同的 f(ꭓ) [標:不完全一定,會有不同的ꭓ,得到相同的f(ꭓ)情況,術語叫哈希碰撞], 查找的時候,將要查找的key,也按照定義好的哈希函數轉換 得到一個哈希值,然後用這個哈希值,直接去哈希表中取,取出則為找出key,取不出即為查找的key不存在.
來看看哈希思想的幾個應用:
面試題一:
判斷 8 是否存在數組[1,3,5,7,11,13,17]中.
普通青年
但是這種方式,每查找一次,都要整個的遍歷一次.來看看下面的方法:
文藝青年
可以看到,只要 hash 表建立成功後,每次判斷一個數是不是在數組中,只需要直接執行 arrHashObject[key] 就可以得到結果了.效率大大提高.
面試題二:
當 usertype=1 時, userTypeName 為 student,
當 usertype=2 時, userTypeName 為 teacher,
當 usertype=3 時, userTypeName 為 admin,
請用代碼描述.
普通青年
但是這種寫法,當條件增多的情況,簡直就是災難.我們可以使用哈希的思想,寫得文藝一點:
文藝青年
增加角色,只需配置這個哈希表,避免了繁瑣的 if-else.
面試題三:
需要對存儲大量的 URL,並需要根據URL 進行搜索查找.
普通青年: 使用 B-Tree來存儲 URL, 會有如下查詢:
select id from url where url = 'http://www.mysql.com';
文藝青年: 刪除原來 URL 上的索引,新增一個被索引的 url_crc列,使用 CRC32做哈希,就可以使用下面的方式查詢:
select id from url where url = 'http://www.mysql.com'
and url_crc = CRC32('http://www.mysql.com');
性能 biu 的一下就上去了,佔的空間還不大.
還有在 APP 開發中,我們通常使用 token 來模擬 session 以判斷是否用戶登錄. 大概思路是: 將 將 token 存入到 redis 中. 然後直接使用 Redis->get(token) 看值是否為空來判斷是否登錄...
有同學要問了, 哈希查找這麼好,那有缺點沒有?