Hash底層實(shí)現(xiàn)原理

1、HashMap的底層實(shí)現(xiàn)原理一、HashMap的數(shù)據(jù)結(jié)構(gòu)總述：哈希的出現(xiàn)時因?yàn)閭鹘y(tǒng)數(shù)據(jù)結(jié)構(gòu)如線性表（數(shù)組，鏈表等），樹中，關(guān)鍵字與其它的存放位置不存在對應(yīng)的關(guān)系。因此在查找關(guān)鍵字的時候需要逐個比對，雖然出現(xiàn)了二分查找等各種提高效率的的查找算法。但是這些并不足夠，希望在查詢關(guān)鍵字的時候不經(jīng)過任何比較，一次存取便能得到所查記錄。因此，我們必須在關(guān)鍵字和其對應(yīng)的存儲位置間建立對應(yīng)的關(guān)系f。這種對應(yīng)的關(guān)系f被稱為哈希函數(shù)，按此思想建立的表為哈希表。關(guān)鍵在于哈希函數(shù)如何構(gòu)造。意思就是：關(guān)鍵字的存儲位置是有關(guān)鍵字的內(nèi)容決定的。數(shù)據(jù)結(jié)構(gòu)中有數(shù)組和鏈表來實(shí)現(xiàn)對數(shù)據(jù)的存儲，但這兩者基本上是兩個極端。數(shù)組：數(shù)組存

2、儲區(qū)間是連續(xù)的，占用內(nèi)存嚴(yán)重，故空間復(fù)雜的很大。但數(shù)組的二分查找時間復(fù)雜度小，為O(1)；數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；鏈表：鏈表存儲區(qū)間離散，占用內(nèi)存比較寬松，故空間復(fù)雜度很小，但時間復(fù)雜度很大，達(dá)O（N）。鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。哈希表：那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表。哈希表（(Hash table）既滿足了數(shù)據(jù)的查找方便，同時不占用太多的內(nèi)容空間，使用也十分方便。哈希表有多種不同的實(shí)現(xiàn)方法，我接下來解釋的是最常用的一種方法拉鏈法，我們可以理解為“鏈表的數(shù)組”一個長度為16的數(shù)組中，

3、每個元素存儲的是一個鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢。一般情況是通過hash(key)&len-1獲得，也就是元素的key的哈希值對數(shù)組長度取模得到。HashMap其實(shí)也是一個線性的數(shù)組實(shí)現(xiàn)的,所以可以理解為其存儲數(shù)據(jù)的容器就是一個線性數(shù)組。這可能讓我們很不解，一個線性的數(shù)組怎么實(shí)現(xiàn)按鍵值對來存取數(shù)據(jù)呢？這里HashMap有做一些處理。首先HashMap里面實(shí)現(xiàn)一個靜態(tài)內(nèi)部類Entry，其重要的屬性有key , value, next，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實(shí)現(xiàn)的一個基礎(chǔ)bean，我們上面說到HashMap的基

4、礎(chǔ)就是一個線性數(shù)組，這個數(shù)組就是Entry，Map里面的內(nèi)容都保存在Entry里面。Transient Entrytable;二、HashMap的存取實(shí)現(xiàn)：/ 存儲時:int hash = key.hashCode(); / 這個hashCode方法這里不詳述,只要理解每個key的hash是一個固定的int值int index = hash % Entry.length;Entryindex = value;/ 取值時:int hash = key.hashCode();int index = hash % Entry.length;return Entryindex;（1）Put疑問：如果兩

5、個key通過hash%Entry.length得到的index相同，會不會有覆蓋的危險(xiǎn)？這里HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個概念。上面我們提到過Entry類里面有一個next屬性，作用是指向下一個Entry。打個比方， 第一個鍵值對A進(jìn)來，通過計(jì)算其key的hash得到的index=0，記做:Entry0 = A。一會后又進(jìn)來一個鍵值對B，通過計(jì)算其index也等于0，現(xiàn)在怎么辦？HashMap會這樣做:B.next = A,Entry0 = B,如果又進(jìn)來C,index也等于0,那么C.next = B,Entry0 = C；這樣我們發(fā)現(xiàn)index=0的地方其實(shí)存取了A,B,C三個鍵

6、值對,他們通過next這個屬性鏈接在一起。所以疑問不用擔(dān)心。也就是說數(shù)組中存儲的是最后插入的元素。到這里為止，HashMap的大致實(shí)現(xiàn)，我們應(yīng)該已經(jīng)清楚了。public V put(K key, V value) if (key = null) return putForNullKey(value); /null總是放在數(shù)組的第一個鏈表中 int hash = hash(key.hashCode(); int i = indexFor(hash, table.length); /遍歷鏈表 for (Entry e = tablei; e != null; e = e.next) Object

7、k; /如果key在鏈表中已存在，則替換為新value if (e.hash = hash & (k = e.key) = key | key.equals(k) V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; modCount+; addEntry(hash, key, value, i); return null; void addEntry(int hash, K key, V value, int bucketIndex) Entry e = tablebucketIndex;

8、tablebucketIndex = new Entry(hash, key, value, e); /參數(shù)e, 是Entry.next /如果size超過threshold，則擴(kuò)充table大小。再散列 if (size+ = threshold) resize(2 * table.length);當(dāng)然HashMap里面也包含一些優(yōu)化方面的實(shí)現(xiàn)，這里也說一下。比如：Entry的長度一定后，隨著map里面數(shù)據(jù)的越來越長，這樣同一個index的鏈就會很長，會不會影響性能？HashMap里面設(shè)置一個因子，隨著map的size越來越大，Entry會以一定的規(guī)則加長長度。（2）Getpublic V

9、get(Object key) if (key = null) return getForNullKey(); int hash = hash(key.hashCode(); /先定位到數(shù)組元素，再遍歷該元素處的鏈表 for (Entry e = tableindexFor(hash, table.length); e != null; e = e.next) Object k; if (e.hash = hash & (k = e.key) = key | key.equals(k) return e.value; return null;（3）null key 的存取null key總是存

10、放在Entry數(shù)組的第一個元素。private V putForNullKey(V value) for (Entry e = table0; e != null; e = e.next) if (e.key = null) V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; modCount+; addEntry(0, null, value, 0); return null; private V getForNullKey() for (Entry e = table0; e != nu

11、ll; e = e.next) if (e.key = null) return e.value; return null;（4）確定數(shù)組index：hashCode&table.length（類似取模運(yùn)算）HashMap存取時，都需要計(jì)算當(dāng)前key應(yīng)該對應(yīng)Entry數(shù)組哪個元素，即計(jì)算數(shù)組下標(biāo)；算法如下：/* * Returns index for hash code h. */ static int indexFor(int h, int length) return h & (length-1); 按位取并，作用上相當(dāng)于取模mod或者取余%。這意味著數(shù)組下標(biāo)相同，并不表示hashCode

12、相同。（5）table初始大小 public HashMap(int initialCapacity, float loadFactor) . / Find a power of 2 = initialCapacity int capacity = 1; while (capacity initialCapacity) capacity = initialCapacity的2的n次冪！三、解決Hash沖突的辦法如果兩個不同對象的hashCode相同，這種現(xiàn)象稱為沖突。開放定址法（線性探測再散列，二次探測再散列，偽隨機(jī)探測再散列）再哈希法鏈地址法建立一個公共溢出區(qū)Java中hashmap的解決辦

13、法就是采用的鏈地址法。四、再散列rehash過程當(dāng)哈希表的容量超過默認(rèn)容量時，必須調(diào)整table的大小。當(dāng)容量已經(jīng)達(dá)到最大可能值時，那么該方法就將容量調(diào)整到Integer.MAX_VALUE返回，這時，需要創(chuàng)建一張新表，將原表的映射到新表中。void resize(int newCapacity) Entry oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity = MAXIMUM_CAPACITY) threshold = Integer.MAX_VALUE; return; Entry newTable =

14、 new EntrynewCapacity; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); /* * Transfers all entries from current table to newTable. */ void transfer(Entry newTable) Entry src = table; int newCapacity = newTable.length; for (int j = 0; j src.length; j+) Entry e = srcj

15、; if (e != null) srcj = null; do Entry next = e.next; /重新計(jì)算index int i = indexFor(e.hash, newCapacity); e.next = newTablei; newTablei = e; e = next; while (e != null); HashTable和HashMap區(qū)別第一，繼承不同。public class Hashtable extends Dictionary implements Mappublic class HashMap extends AbstractMap implemen

16、ts Map第二Hashtable中的方法是同步的，而HashMap中的方法在缺省情況下是非同步的。即是說，在多線程應(yīng)用程序中，不用專門的操作就安全地可以使用Hashtable了；而對于HashMap，則需要額外的同步機(jī)制。但HashMap的同步問題可通過Collections的一個靜態(tài)方法得到解決：Map Collections.synchronizedMap(Map M)這個方法返回一個同步的Map，這個Map封裝了底層的HashMap的所有方法，使得底層的HashMap即使是在多線程的環(huán)境中也是安全的。第三Hashtable中，key和value都不允許出現(xiàn)null值。在HashMap中

17、，null可以作為鍵，這樣的鍵只有一個；可以有一個或多個鍵所對應(yīng)的值為null。當(dāng)get()方法返回null值時，即可以表示 HashMap中沒有該鍵，也可以表示該鍵所對應(yīng)的值為null。因此，在HashMap中不能由get()方法來判斷HashMap中是否存在某個鍵， 而應(yīng)該用containsKey()方法來判斷。第四，兩個遍歷方式的內(nèi)部實(shí)現(xiàn)上不同。Hashtable、HashMap都使用了 Iterator。而由于歷史原因，Hashtable還使用了Enumeration的方式 。第五哈希值的使用不同，HashTable直接使用對象的hashCode。而HashMap重新計(jì)算hash值。第

18、六Hashtable和HashMap它們兩個內(nèi)部實(shí)現(xiàn)方式的數(shù)組的初始大小和擴(kuò)容的方式。HashTable中hash數(shù)組默認(rèn)大小是11，增加的方式是old*2+1。HashMap中hash數(shù)組的默認(rèn)大小是16，而且一定是2的指數(shù)。Hashtable 與 ConcurrentHashMap 的區(qū)別ConcurrentHashMap融合了hashtable和hashmap二者的優(yōu)勢。hashtable是做了同步的，hashmap未考慮同步。所以hashmap在單線程情況下效率較高。hashtable在的多線程情況下，同步操作能保證程序執(zhí)行的正確性。但是hashtable每次同步執(zhí)行的時候都要鎖住整個結(jié)構(gòu)。ConcurrentHashMap正是為了解決這個問題而誕生的。ConcurrentHashMap鎖的方式是稍微細(xì)粒度的。ConcurrentHashMap將hash表分為16個桶（默認(rèn)值），諸如get,put,remove等常用操作只鎖當(dāng)前需要用到的桶。試想，原來 只能一個線程進(jìn)入，現(xiàn)在卻能同時16個寫線程進(jìn)入（寫線程才需要鎖定，而讀線程幾乎不受限制，之后會提到），并發(fā)性的提升是顯而易見的。更令人驚訝的是ConcurrentHashMap的讀取并發(fā)，因?yàn)樵谧x取的大多數(shù)時候都沒有用到鎖定，所以讀取操作幾乎是完全的并發(fā)操作，而寫操作鎖定的粒度又非常細(xì)，比起之前