1 哈希函數(shù)特點(diǎn)
輸入域無限，輸出域有限
對于同一哈希函數(shù)，輸入相同纵东，輸出一定相同
-
哈希函數(shù)的輸出值在一定范圍內(nèi)具有離散性，哈希函數(shù)的輸出值 % m (即對m取模)后啥寇，結(jié)果仍就有均勻性
由第一個(gè)特性偎球，對于不同的輸入，哈希函數(shù)的輸出有可能相同辑甜，即存在哈希碰撞衰絮。
由第三個(gè)特性，當(dāng)輸入數(shù)量足夠大時(shí)磷醋，哈希函數(shù)的輸出值在一定域內(nèi)（如 0 ~ m-1）的分布是離散的猫牡，且碰撞到域中的每個(gè)值的數(shù)量是幾乎均勻的。
2 哈希表的擴(kuò)容
當(dāng)哈希表的碰撞累計(jì)數(shù)量超出一定范圍是子檀，哈希表在碰撞鏈上的查詢需消耗更多的時(shí)間（盡管碰撞鏈的查詢是線性的）
此時(shí)需要對哈希表進(jìn)行擴(kuò)容镊掖，一般哈希表的初始容量設(shè)為奇數(shù)（可稍稍提高輸出的均勻性），當(dāng)擴(kuò)容時(shí)褂痰，如從17 -> 34亩进，需要對哈希表的內(nèi)容重新計(jì)算哈希值。理論上缩歪，平均每插入一個(gè)數(shù)據(jù)归薛，哈希表擴(kuò)容的時(shí)間成本為 ，由于其常數(shù)項(xiàng)非常小，故可近似視為
主籍。
此外习贫，對于使用虛擬機(jī)的語言，如Java中的JVM千元，虛擬機(jī)會(huì)在后臺(tái)離線擴(kuò)容苫昌，從而不占用用戶在線等待時(shí)間，進(jìn)一步減少了哈希表擴(kuò)容時(shí)間成本（用戶在線等待的時(shí)間成本）幸海。
C++祟身，C等無虛擬機(jī)，故每次擴(kuò)容為在線擴(kuò)容物独。
