散列表的查詢效率并不能籠統(tǒng)地說成是O(1)。它跟散列函數(shù)、裝載因子、散列沖突等都有關(guān)系。如果散列函數(shù)設(shè)計得不好，或者裝載因子過高，都可能導(dǎo)致散列沖突發(fā)生的概率升高，查詢效率下降。
如何設(shè)計散列函數(shù)?
散列函數(shù)設(shè)計的好壞，決定了散列表沖突的概率大小，也直接決定了散列表的性能。那什么才是好的散列函數(shù)呢?首先，散列函數(shù)的設(shè)計不能太復(fù)雜。過于復(fù)雜的散列函數(shù)，勢必會消耗很多計算時間，也就間接的影響到散列表的性能。其次，散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布，這樣才能避免或者最小化散列沖突，而且即便出現(xiàn)沖突，散列到每個槽里的數(shù)據(jù)也會比較平均，不會出現(xiàn)某個槽內(nèi)數(shù)據(jù)特別多的情況。需要綜合考慮各種因素，這些因素有關(guān)鍵字的長度、特點(diǎn)、分布、還有散列表的大小等。實(shí)際上，散列函數(shù)的設(shè)計方法還有很多，比如直接尋址法、平方取中法、折疊法、隨機(jī)數(shù)法等，這些你只要了解就行了，不需要全都掌握。感興趣的可以去看下每一種語言的散列表的散列函數(shù)實(shí)現(xiàn)。
裝載因子過大了怎么辦?
散列表的裝載因子越大，說明散列表中的元素越多，空閑位置越少，散列沖突的概率就越大。不僅插入數(shù)據(jù)的過程要多次尋址或者拉很長的鏈，查找的過程也會因此變得很慢。
對于沒有頻繁插入和刪除的靜態(tài)數(shù)據(jù)集合來說，我們很容易根據(jù)數(shù)據(jù)的特點(diǎn)、分布等，設(shè)計出完美的、極少沖突的散列函數(shù)，因?yàn)楫吘怪皵?shù)據(jù)都是已知的。
對于動態(tài)散列表來說，數(shù)據(jù)集合是頻繁變動的，我們事先無法預(yù)估將要加入的數(shù)據(jù)個數(shù)，所以我們也無法事先申請一個足夠大的散列表。隨著數(shù)據(jù)慢慢加入，裝載因子就會慢慢變大。當(dāng)裝載因子大到一定程度之后，散列沖突就會變得不可接受
動態(tài)擴(kuò)容
當(dāng)裝載因子過大時，我們也可以進(jìn)行動態(tài)擴(kuò)容，重新申請一個更大的散列表，將數(shù)據(jù)搬移到這個新散列表中。假設(shè)每次擴(kuò)容我們都申請一個原來散 列表大小兩倍的空間。如果原來散列表的裝載因子是0.8，那經(jīng)過擴(kuò)容之后，新散列表的裝載因子就下降為原來的一半，變成了0.4。
針對數(shù)組的擴(kuò)容，數(shù)據(jù)搬移操作比較簡單。但是，針對散列表的擴(kuò)容，數(shù)據(jù)搬移操作要復(fù)雜很多。因?yàn)樯⒘斜淼拇笮∽兞?，?shù)據(jù)的存儲位置也變了，所以我們需
要通過散列函數(shù)重新計算每個數(shù)據(jù)的存儲位置。
你可以看我圖里這個例子。在原來的散列表中，21這個元素原來存儲在下標(biāo)為0的位置，搬移到新的散列表中，存儲在下標(biāo)為7的位置。
插入一個數(shù)據(jù)，最好情況下，不需要擴(kuò)容，最好時間復(fù)雜度是O(1)。最壞情況下，散列表裝載因子過高，啟動擴(kuò)容，我們需要重新申請內(nèi)存空間，重新計算哈希 位置，并且搬移數(shù)據(jù)，所以時間復(fù)雜度是O(n)。用攤還分析法，均攤情況下，時間復(fù)雜度接近最好情況，就是O(1)。
動態(tài)縮容
對于動態(tài)散列表，隨著數(shù)據(jù)的刪除，散列表中的數(shù)據(jù)會越來越少，空閑空間會越來越多。如果我們對空間消耗非常敏感，我們可以在裝載因子小于某個
值之后，啟動動態(tài)縮容。當(dāng)然，如果我們更加在意執(zhí)行效率，能夠容忍多消耗一點(diǎn)內(nèi)存空間，那就可以不用費(fèi)勁來縮容了。
在JDK1.8版本中，引入了紅黑樹。而當(dāng)鏈表長度太長(默認(rèn)超過8)時，鏈表就轉(zhuǎn)換為紅黑樹。我們可以利用紅黑樹快 速增刪改查的特點(diǎn)，提高HashMap的性能。當(dāng)紅黑樹結(jié)點(diǎn)個數(shù)少于8個的時候，又會將紅黑樹轉(zhuǎn)化為鏈表。因?yàn)樵跀?shù)據(jù)量較小的情況下，紅黑樹要維護(hù)平衡，比起 鏈表來，性能上的優(yōu)勢并不明顯。
如何避免低效地擴(kuò)容?
大部分情況下，動態(tài)擴(kuò)容的散列表插入一個數(shù)據(jù)都很快，但是在特殊情況下，當(dāng)裝載因子已經(jīng)到達(dá)閾值，需要先進(jìn)行擴(kuò)容，再插入數(shù)據(jù)。這個時候，插入數(shù)據(jù)就會變得很慢，甚至?xí)o法接受。
比如列表當(dāng)前大小為1GB，要想擴(kuò)容為原來的兩倍大小，那就需要對1GB的數(shù)據(jù)重新計算哈希值，并且從原來的散列表搬移到新的散列表，這顯然是無法接受的。
這個時候，“一次性”擴(kuò)容的機(jī)制就不合適了。
為了解決一次性擴(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ù)搬移，插入操作就都變得很快了。
這期間的查詢操作怎么來做呢?對于查詢操作，為了兼容了新、老散列表中的數(shù)據(jù)，我們先從新散列表中查找，如果沒有找到，再去老的散列表中查找。
擴(kuò)展閱讀
Threadlocal 和 ThreadLocalMap https://blog.csdn.net/chen_kkw/article/details/79176371
