當前位置:首頁 » 服務存儲 » 面試hashmap存儲原理
擴展閱讀
webinf下怎麼引入js 2023-08-31 21:54:13
堡壘機怎麼打開web 2023-08-31 21:54:11

面試hashmap存儲原理

發布時間: 2023-07-23 06:28:39

⑴ hashmap的最大容量是多少,在多少的時候會導致查詢響應過慢

原則上,hashmap的插入和搜索,復雜度都是1,是非常快速的跟你的容量大小通常是沒有直接關系的但是這是理想的情況。
這里說的理想,是在你所存儲的對象的hashcode這個方法寫的非常有效的情況下。根據hash的原理,存放一個對象是根據他的hashcode來計算的,如果沒有哈希沖突,那麼他的存儲效率是最高,最完美的。
為什麼哈希沖突會使得效率下降呢?
具體來分析,假設一個對象O1,他的hashcode算出來是1,另一個對象是O2,hashcode算起來也是1. 先放入O1對象,這時候速度很快,根據hashcode計算出來這個對象應該在哪個位置存放,然後直接放進去。但是到了放O2的時候,根據hashcode計算的地址存放,發現之前已經有O1了,那麼顯然是不能放的,因此就要採取些措施,比如,再計算一次,然後分配存放的地址(如果沖突,將繼續,知道解決),一種最惡劣的情況下,很多很多的對象都存在hash沖突,那麼重要就變得存儲越來越慢。但是這個不是hashmap的責任,而是你的對象的hashcode方法沒有定義好,使得沖突頻繁
另外,哈希表為了避免這種沖突,會有一點優化。簡單的說,原本可以放100個數據的空間,當放到80個的時候,根據經驗,接下去沖突的可能性會更加高,就好比一個靶子上80%都是箭的時候你再射一箭出去,射中箭的可能性很大。因此就自動增加空間來減小沖突可能性。
80/100 = 0.8 這個0.8就是負載因子。
java中的hashmap的負載因子是0.75說了寫理論。說這個的原因是想解釋一下你的疑問「10000條的時候在搜索的時候很快,那麼在多少條的時候可能導致效率下降呢」。這個答案是肯定的,就是存儲的量跟存儲效率沒有直接的關系。
這頁是hash表這個數據結構的優勢所在
如果你覺得效率出現問題的時候,應該去關注一下你的存儲對象的hashcode方法寫的是否有問題
如果想更完美的解決效率問題,還可以手動指定hashmap的負載因子(用HashMap(int factor)這個構造方法),負載因子越低,沖突可能越小。但是犧牲的空間會相應增加

如果還是不能很好理解,可以先參看hash這個數據結構的特點,和JDK中HashMap的源代碼,以及注釋

學好java,數據結構是很重要的,理解原理的使用,跟生搬硬套的使用,不可同年而語
所以,去面試淘寶,騰訊,化為這種公司不會問你struts怎麼用,只會問你struts怎麼寫。如同不會問你hashmap怎麼用,而會問你hashmap的設計理念,和實現原理

希望對你有所幫助