歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

2014阿裡實習面試題——哈希的原理和Java中HashMap如何實現的

1、哈希的原理

哈希的出現時因為傳統數據結構如線性表(數組,鏈表等),樹中,關鍵字與其它的存放位置不存在對應的關系。因此在查找關鍵字的時候需要逐個比對,雖然出現了二分查找等各種提高效率的的查找算法。但是這些並不足夠,希望在查詢關鍵字的時候不經過任何比較,一次存取便能得到所查記錄。因此,我們必須在關鍵字和其對應的存儲位置間建立對應的關系f。這種對應的關系f被稱為哈希函數,按此思想建立的表為哈希表。關鍵在於哈希函數如何構造。

有如下幾種方法:

1)直接定址法

取關鍵字或者關鍵字的某個線性函數值為哈希地址。

2)數字分析法

3)平方取中法

取關鍵字平方後的中間幾位為哈希地址。

4)折疊法

將關鍵字分割成位數相同的幾部分(最後一部分的位數可以不通),然後取這幾部分的疊加和(捨去進位)作為哈希地址。

5)取余數法

取關鍵字被某個不大於哈希表表長(HASH_TABLE_LENGTH)的數p除後所得的余數作為哈希地址。

H(key) = key % p          (其中p小於或者等於哈希表表長HASH_TABLE_LENGTH)

6)隨機數法

取關鍵字的隨機函數值作為它的哈希地址。

那麼確定了哈希函數之後,就要解決哈希沖突的問題,常用的方法如下:

1)開放定址法

Hi = (H(key) + di) % M                            i = 1, 2, 3,..., k ( k <= M-1 )

其中:H(key)為哈希函數;M為哈希表表長;di為增量序列;di可能有下列三種取法:

a 線性探測再散列:di = 1, 2, 3, ..., M-1

b 二次探測再散列:di = (+,-)k^2,(k <= M/2)

c 隨機探測再散列:di為隨機數序列

2)再哈希法

3)鏈地址法

4)建立一個公共溢出區

2、java中的hashmap是如何實現的

HashMap實際上是一個“鏈表散列”的數據結構,即數組和鏈表的結合體。我們可以理解為“鏈表的數組”,如圖:

HashMap其實也是一個線性的數組實現的,所以可以理解為其存儲數據的容器就是一個線性數組。那麼一個線性的數組怎麼實現按鍵值對來存取數據呢?這裡HashMap有做一些處理。

  1.首先HashMap裡面實現一個靜態內部類Entry,其重要的屬性有 key , value, next,從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實現的一個基礎bean,我們上面說到HashMap的基礎就是一個線性數組,這個數組就是Entry[],Map裡面的內容都保存在Entry[]裡面。

2、hashmap中hash沖突的解決(鏈地址法):Entry類裡面有一個next屬性,作用是指向下一個Entry。每當同一個index有新的結點(A)插入時,A成為此索引的頭結點,然後A->NEXT=舊頭結點。

Copyright © Linux教程網 All Rights Reserved