1樓：欣然
當我們新增乙個新元素時，一旦loadFactor大於等於1了，我們不能單純的往hash表裡邊新增元素。因為新增完之後，loadFactor將大於1，這樣也就不能保證查詢的期望時間複雜度為常數級了。這時，我們應該對桶陣列進行一次容量擴張，讓size增大 。
這樣就能保證新增元素後 used / size 仍然小於等於1 ， 從而保證查詢的期望時間複雜度為O(1).但是，如何進行容量擴張呢？ C++中的vector的容量擴張是一種好方法。
於是有了如下思路 ： Hash表中每次發現loadFactor==1時，就開闢乙個原來桶陣列的兩倍空間（稱為新桶陣列），然後把原來的桶陣列中元素全部轉移過來到新的桶陣列中。注意這裡轉移是需要元素乙個個重新雜湊到新桶中的，原因後面會講到。
這種方法的缺點是，容量擴張是一次完成的，期間要花很長時間一次轉移hash表中的所有元素。這樣在hash表中loadFactor==1時，往裡邊插入乙個元素將會等候很長的時間。
redis中的dict.c中的設計思路是用兩個hash表來進行進行擴容和轉移的工作：當從第乙個hash表的loadFactor=1時，如果要往字典裡插入乙個元素，首先為第二個hash表開闢2倍第乙個hash表的容量，同時將第乙個hash表的乙個非空桶中元素全部轉移到第二個hash表中，然後把待插入元素儲存到第二個hash表裡。
繼續往字典裡插入第二個元素，又會將第乙個hash表的乙個非空桶中元素全部轉移到第二個hash表中，然後把元素儲存到第二個hash表裡……直到第乙個hash表為空。
這種策略就把第乙個hash表所有元素的轉移分攤為多次轉移，而且每次轉移的期望時間複雜度為O(1)。這樣就不會出現某一次往字典中插入元素要等候很長時間的情況了。
2樓：little pie
如果是面試那應該要追問下所謂的最高效具體的含義是什麼時間空間上有什麼具體的要求。工程中的實現就是題主所看到的方式，redis的實現中 rehash不是一次性完成的分多個階段遷移保證停頓時間在可以接受的範圍內。
3樓：檀十一郎
線性雜湊表，專治擴容。若干年前瞅過幾眼mysql 的原始碼，被linear hash 在heap databse中的應用驚到了。
4樓：[已重置]
可以使用懶擴容，findNext返回null的時候再將這個元素插入到新的陣列中，但也只是使擴容的成本均勻分散到每一次插入衝突中而已，redis就是這種辦法，如果還有更好的辦法，一定會震驚業界的吧
5樓：
動態hash，如：Extendible hashing, Linear hashing, 和 consistent hashing
簡介：Extendible hashing, Linear hashing - Wikipedia, 以及Consistent hashing
6樓：
如果題主想做到盡量少元素重新分配的話，可以參考consistent hash， jump consistent hash 和highest random weight hash。這是分布式系統負載平衡的常用演算法，設計之初就考慮了增減節點時盡量少做重新分配的問題。
7樓：陳碩
實際工作中用的就是你看到的那種做法。
rehash 反正要新分配乙個 bucket，要把原來的元素都重新插入，這時追求「盡可能少的元素變動位置」意義何在？
如何挑選乙個實用低調的石英表
依依馨 看樓主的提問，推測應該是個時尚Sunny的大男孩哈，是不是也有著四字弟弟一樣好看的笑容，笑起來整個人都是溫暖的，我覺得手錶都是乙個穿搭配飾的乙個好幫手，建議去線下店多去逛逛看看，那個型別最適合你的氣質。卡西歐 卡西歐是出了名的經久耐用，價效比高 款式時尚 也是愛穿休閒潮牌年輕人佩戴的乙個符號...
如何判斷乙個女生對乙個男生有好感
小葉子 有他在的地方偷瞄他，聽著他一些無關緊要的訊息在暗地偷笑，偷偷打聽他的訊息，面對著他的時候不自然，跟他說話的時候很生硬。etc 諸葛筱暖 你一進教室，她本來趴在桌子上突然抬起頭看你，然後被你發現了馬上繼續趴在桌子上 你上課回答問題時，她會痴痴的看著你 你從她身邊經過，她會轉身看你，因為她能分辨...
對乙個人好了很久，對方都欣然接受，等到大學表白，結果人家說，我就覺得你是好朋友啊，有必要繼續喜歡嗎？
Osti 有的人說愛是無私的，喜歡你，對你好並不要求你喜歡我，對我同樣的付出。有的人說愛是自私的，喜歡你的本質就是想要你跟我在一起，和我一起才是真的幸福。決不決定繼續喜歡，取決於自己，自己想要的究竟是什麼，你可能是純粹的喜歡她，可能只是想跟他在一起，甚至你可能喜歡的是你喜歡她的感覺。自己想想把，每個...