哈希表的概念
散列表
設所有可能的關鍵詞集記為U（簡稱全集），實際出現（即實際存儲）的關鍵詞集記為K（| K |遠小於|U|）。
哈希方法是利用函數H（m = O（| U |）將U映射到表T【m】的下標上，使U中的關鍵字為自變量、H為函數的運算結果為phase。
根據節點的存儲地址，可以在o（）時間內完成搜索。
在…之中
① h U→{ … m} H通常被稱為哈希函數。哈希函數H的功能是壓縮要處理的下標範圍，以便它可以被處理。
的|U|值減少到m個值，從而減少了空間開銷。
② T是哈希表。
③h（K i）（ki∈U）是帶有關鍵字ki的節點的存儲地址（也稱為哈希值或哈希地址）。
④根據關鍵字哈希地址將節點存儲在哈希表中的過程稱為哈希。
哈希表的沖突現象
沖突（）
由於相同的散列函數值，兩個不同的關鍵字被映射到相同的表位置。這種現象被稱為碰撞或碰撞。
該關鍵字被稱為哈希函數的同義詞。
例如上圖中的k ≠k為h（K）= h（K），所以K和K所在節點的存儲地址是相同的。
（）安全避免沖突的條件
解決沖突最理想的方式是安全地避免沖突。為此，必須滿足兩個條件。
（1）壹個是| u |U|≤m m。
（2）其次是選擇合適的哈希函數。
這僅適用於|U|較小且關鍵字事先已知的情況。此時，通過仔細設計散列函數h可以完全避免沖突。
沖突是無法完全避免的。
正常情況下，H是壓縮圖像|K|≤m但| u |》；m，因此，無論如何設計H，都不可能完全避免沖突，因此只能在設計H時進行。
為了最大限度地減少沖突，還需要確定解決沖突的方法，以便可以將有沖突的同義詞存儲在表中。
（）影響沖突的因素
沖突的頻率不僅與H有關，還與表的填充程度有關。
設m和n分別表示表的長度和表中填充的節點數，並將α=n/m定義為哈希表的加載因子α越大，表越滿的概率。
它越大，α越≤
Lishi Xinzhi/Article/program/sjjg/201311/23740