如何設(shè)計(jì)散列函數(shù)
- 散列函數(shù)的設(shè)計(jì)不能太復(fù)雜
- 散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布
裝載因子過大了怎么辦？
- 對于沒有頻繁插入和刪除的靜態(tài)數(shù)據(jù)集合來說皂冰，我們很容易根據(jù)數(shù)據(jù)的特點(diǎn)鹊奖、分布等苛聘，設(shè)計(jì)出完美的、極少沖突的散列函數(shù)忠聚，因?yàn)楫吘怪皵?shù)據(jù)都是已知的焰盗。
- 對于動態(tài)散列表來說，數(shù)據(jù)集合是頻繁變動的咒林，我們事先無法預(yù)估將要加入的數(shù)據(jù)個數(shù)，所以我們也無法事先申請一個足夠大的散列表爷光。隨著數(shù)據(jù)慢慢加入垫竞，裝載因子就會慢慢變大。當(dāng)裝載因子大到一定程度之后蛀序，散列沖突就會變得不可接受欢瞪。這個時候，我們需要“動態(tài)擴(kuò)容”徐裸。
裝載因子閾值的設(shè)置要權(quán)衡時間遣鼓、空間復(fù)雜度。如果內(nèi)存空間不緊張重贺，對執(zhí)行效率要求很高骑祟，可以降低負(fù)載因子的閾值；相反气笙，如果內(nèi)存空間緊張次企，對執(zhí)行效率要求又不高，可以增加負(fù)載因子的值潜圃，甚至可以大于 1缸棵。
如何避免低效地擴(kuò)容？
大部分情況下谭期，動態(tài)擴(kuò)容的散列表插入一個數(shù)據(jù)都很快堵第，但是在特殊情況下，當(dāng)裝載因子已經(jīng)到達(dá)閾值隧出，需要先進(jìn)行擴(kuò)容踏志，再插入數(shù)據(jù)。這個時候胀瞪，插入數(shù)據(jù)就會變得很慢狰贯，甚至?xí)o法接受。
- 為了解決一次性擴(kuò)容耗時過多的情況，我們可以將擴(kuò)容操作穿插在插入操作的過程中涵紊，分批完成傍妒。當(dāng)裝載因子觸達(dá)閾值之后，我們只申請新空間摸柄，但并不將老的數(shù)據(jù)搬移到新散列表中颤练。
- 當(dāng)有新數(shù)據(jù)要插入時，我們將新數(shù)據(jù)插入新散列表中驱负，并且從老的散列表中拿出一個數(shù)據(jù)放入到新散列表嗦玖。每次插入一個數(shù)據(jù)到散列表，我們都重復(fù)上面的過程跃脊。經(jīng)過多次插入操作之后宇挫，老的散列表中的數(shù)據(jù)就一點(diǎn)一點(diǎn)全部搬移到新散列表中了。這樣沒有了集中的一次性數(shù)據(jù)搬移酪术，插入操作就都變得很快了器瘪。
如何選擇沖突解決方法？
1. 開放尋址法
當(dāng)數(shù)據(jù)量比較小绘雁、裝載因子小的時候橡疼，適合采用開放尋址法。這也是Java 中的ThreadLocalMap使用開放尋址法解決散列沖突的原因庐舟。
2. 鏈表法
基于鏈表的散列沖突處理方法比較適合存儲大對象欣除、大數(shù)據(jù)量的散列表，而且挪略，比起開放尋址法历帚，它更加靈活，支持更多的優(yōu)化策略杠娱，比如用紅黑樹代替鏈表抹缕。
工業(yè)級的散列表應(yīng)該具有哪些特性？
- 支持快速的查詢墨辛、插入卓研、刪除操作；
- 內(nèi)存占用合理睹簇，不能浪費(fèi)過多的內(nèi)存空間奏赘；
- 性能穩(wěn)定，極端情況下太惠，散列表的性能也不會退化到無法接受的情況磨淌。
如何實(shí)現(xiàn)這樣一個散列表呢？
- 設(shè)計(jì)一個合適的散列函數(shù)凿渊；
- 定義裝載因子閾值梁只，并且設(shè)計(jì)動態(tài)擴(kuò)容策略缚柳；
- 選擇合適的散列沖突解決方法。
