摘要: Hashing定義了一種將字符組成的字符串轉換為固定長度(一般是更短長度)的數值或索引值的方法,稱為散列法,也叫哈希法。由于通過更短的哈希值比用原始值進行數據庫搜索更快,這種方法一般用來在數據庫中建立索引并進行搜索,同時還用在各種解密算法中。
設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為K(|K|比|U|小得多)。|K|是集合K中元素的個數。
散列方法是使用函數hash將U映射到表T[0..m-1]的下標上(m=O(|U|))。這樣以U中關鍵字為自變量,以h為函數的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。
……
閱讀全文