您好,登錄后才能下訂單哦!
小編給大家分享一下HashMap底層原理分析,希望大家閱讀完這篇文章之后都有所收獲,下面讓我們一起去探討吧!
眾所周知,HashMap是一個(gè)用于存儲(chǔ)Key-Value鍵值對(duì)的集合,每一個(gè)鍵值對(duì)也叫做Entry。這些個(gè)鍵值對(duì)(Entry)分散存儲(chǔ)在一個(gè)數(shù)組當(dāng)中,這個(gè)數(shù)組就是HashMap的主干
1. 特性
我們可以用任何類作為HashMap的key,但是對(duì)于這些類應(yīng)該有什么限制條件呢?且看下面的代碼:
public class Person { private String name; public Person(String name) { this.name = name; } } Map testMap = new HashMap(); testMap.put(new Person("hello"), "world"); testMap.get(new Person("hello")); // ---> null
本是想取出具有相等字段值Person類的value,結(jié)果卻是null。對(duì)HashMap稍有了解的人看出來(lái)——Person類并沒(méi)有override hashcode方法,導(dǎo)致其繼承的是Object的hashcode(返回是其內(nèi)存地址),兩次new出來(lái)的Person對(duì)象并不equals——這也是為什么在工程項(xiàng)目中常用不變類(如String、Integer等)做為HashMap的key的原因。那么,HashMap是如何利用hashcode給key做索引的呢?
2. 原理
首先,我們來(lái)看《Thinking in Java》中一個(gè)簡(jiǎn)單HashMap的實(shí)現(xiàn)方案:
//: containers/SimpleHashMap.java // A demonstration hashed Map. import java.util.*; import net.mindview.util.*; public class SimpleHashMap extends AbstractMap { // Choose a prime number for the hash table size, to achieve a uniform distribution: static final int SIZE = 997; // You can't have a physical array of generics, but you can upcast to one: @SuppressWarnings("unchecked") LinkedList>[] buckets = new LinkedList[SIZE]; public V put(K key, V value) { V oldValue = null; int index = Math.abs(key.hashCode()) % SIZE; if(buckets[index] == null) buckets[index] = new LinkedList>(); LinkedList> bucket = buckets[index]; MapEntry pair = new MapEntry(key, value); boolean found = false; ListIterator> it = bucket.listIterator(); while(it.hasNext()) { MapEntry iPair = it.next(); if(iPair.getKey().equals(key)) { oldValue = iPair.getValue(); it.set(pair); // Replace old with new found = true; break; } } if(!found) buckets[index].add(pair); return oldValue; } public V get(Object key) { int index = Math.abs(key.hashCode()) % SIZE; if(buckets[index] == null) return null; for(MapEntry iPair : buckets[index]) if(iPair.getKey().equals(key)) return iPair.getValue(); return null; } public Set> entrySet() { Set> set= new HashSet>(); for(LinkedList> bucket : buckets) { if(bucket == null) continue; for(MapEntry mpair : bucket) set.add(mpair); } return set; } public static void main(String[] args) { SimpleHashMap m = new SimpleHashMap(); m.putAll(Countries.capitals(25)); System.out.println(m); System.out.println(m.get("ERITREA")); System.out.println(m.entrySet()); } }
SimpleHashMap構(gòu)造一個(gè)hash表來(lái)存儲(chǔ)key,hash函數(shù)是取模運(yùn)算Math.abs(key.hashCode()) % SIZE,采用鏈表法解決hash沖突;buckets的每一個(gè)槽位對(duì)應(yīng)存放具有相同(hash后)index值的Map.Entry,如下圖所示: JDK的HashMap的實(shí)現(xiàn)原理與之相類似,其采用鏈地址的hash表table存儲(chǔ)Map.Entry:
/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table = (Entry[]) EMPTY_TABLE; static class Entry implements Map.Entry { final K key; V value; Entry next; int hash; … }
Map.Entry的index是對(duì)key的hashcode進(jìn)行hash后所得。當(dāng)要get key對(duì)應(yīng)的value時(shí),則對(duì)key計(jì)算其index,然后在table中取出Map.Entry即可得到,具體參看代碼:
public V get(Object key) { if (key == null) return getForNullKey(); Entry entry = getEntry(key); return null == entry ? null : entry.getValue(); } final Entry getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }
可見(jiàn),hashcode直接影響HashMap的hash函數(shù)的效率——好的hashcode會(huì)極大減少hash沖突,提高查詢性能。同時(shí),這也解釋開(kāi)篇提出的兩個(gè)問(wèn)題:如果自定義的類做HashMap的key,則hashcode的計(jì)算應(yīng)涵蓋構(gòu)造函數(shù)的所有字段,否則有可能得到null。
看完了這篇文章,相信你對(duì)“HashMap底層原理分析”有了一定的了解,如果想了解更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。