用法和靈芝:
散列表
用于快速存儲和檢索數據(或記錄)。- 記錄存儲在
桶
使用散列鍵
散列鍵
通過將散列算法應用到選定的值(鑰匙
值)包含在記錄中。所選值必須是所有記錄的公共值。- 各
斗
可以有多個按特定順序組織的記錄。
真實世界的例子:
哈希公司,成立于1803年,缺乏任何計算機技術,總共有300個文件柜,為他們的大約30,000名客戶保存詳細的信息(記錄)。每個文件夾都清楚地標識了其客戶端編號,這是一個從0到29,999之間的唯一編號。
當時的檔案辦事員必須迅速為工作人員提取和儲存客戶記錄。工作人員決定,使用散列方法存儲和檢索其記錄將更為有效。
若要歸檔客戶記錄,歸檔辦事員將使用寫入文件夾上的唯一客戶編號。使用此客戶端編號,它們將對散列鍵到300,以確定它包含在其中的文件柜。當他們打開文件柜時,他們會發現里面有許多按客戶編號訂購的文件夾。在確定正確的位置后,他們就會簡單地溜進去。
為了檢索客戶記錄,檔案辦事員將在一張紙條上得到客戶號碼。使用此唯一客戶端編號(散列鍵),他們會調整它300,以確定哪個文件柜有客戶文件夾。當他們打開文件柜時,他們會發現里面有許多按客戶編號訂購的文件夾。通過搜索記錄,他們會快速找到客戶端文件夾并檢索它。
在我們的現實世界中,我們的桶是文件柜而我們記錄是文件文件夾.
需要記住的一件重要的事情是,計算機(及其算法)處理數字比處理字符串更好。因此,使用索引訪問大型數組比按順序訪問要快得多。
正如西蒙提到的我相信非常重要哈希部分是轉換一個大空間(任意長度,通常是字符串等),并將其映射到一個小空間(已知大小,通常是數字)進行索引。這如果是非常重要的記??!
所以在上面的例子中,30,000個可能的客戶機被映射到一個較小的空間。
其中的主要思想是將整個數據集分割成段,以加快實際的搜索,這通常是耗時的。在我們上面的例子中,300個文件柜中的每一個都會(統計上)包含大約100條記錄。通過100條記錄進行搜索(不管順序如何)比處理30,000條記錄要快得多。
你可能已經注意到有些人實際上已經這樣做了。但是,在大多數情況下,它們不會設計哈希方法來生成散列密鑰,而只是使用姓氏的第一個字母。因此,如果你有26個文件柜,每個都包含一個字母從A到Z,理論上你只是分割了你的數據,并加強了歸檔和檢索過程。
希望這能幫上忙
吉奇!