|
HashMap簡介： HashMap在日常的開發(fā)中應(yīng)用的非常之廣泛，它是基于Hash表，實現(xiàn)了Map接口，以鍵值對(key-value)形式進(jìn)行數(shù)據(jù)存儲，HashMap在數(shù)據(jù)結(jié)構(gòu)上使用的是數(shù)組 鏈表。允許null鍵和null值，不保證鍵值對的順序。 HashMap檢索數(shù)據(jù)的大致流程： 當(dāng)我們使用HashMap搜索key所對應(yīng)的value時，HashMap會根據(jù)Hash算法對key進(jìn)行計算，得到一個key的hash值，再根據(jù)hash值算出該key在數(shù)組中存儲的位置index，然后獲取數(shù)組在index位置的鍵值對e,再使用鏈表對e進(jìn)行遍歷，查找遍歷的元素是否和給定的key相符合，若有符合的，則返回其value值。 自己手動畫了一個HashMap的數(shù)據(jù)結(jié)構(gòu)圖：
HashMap源碼分析： HashMap是存儲鍵值對的集合，實現(xiàn)了Map接口,下面我們看一下Map接口的定義：
 /** *映射key到value的頂級接口，不能包含重復(fù)的key，一個key最多可以映射到一個value,鍵和值均可為null */ public interface Map<K,V> { //返回該map包含的鍵值對的個數(shù)，如果鍵值對的個數(shù)超過了Integer.MAX_VALUE,則返會Integer.MAX_VALUE int size(); //如果該Map沒有包含鍵值對，則返回true，否則返回false boolean isEmpty(); //判斷該map是否包含指定的key所對應(yīng)的鍵值對，key可以為null boolean containsKey(Object key); //判斷該map是否包含指定的value所對應(yīng)的鍵值對,若map中包含有一個及以上的key,對應(yīng)指定的value,則返回true，value可以為null boolean containsValue(Object value); //返回指定的key所對應(yīng)的value，若key不存在，則返回null;但是返回null的key,不代表key在map中不存在，有可能是key所對應(yīng)的value為null V get(Object key); //將指定的key和value映射為一個鍵值對，放入map中；若之前該map中包含了指定的Key,則該key所對應(yīng)的老的值oldValue將會被替換為value V put(K key, V value); //刪除指定的key所對應(yīng)的鍵值對，并返回該key對應(yīng)的value V remove(Object key); //將指定的map中的鍵值對復(fù)制到當(dāng)前map中 void putAll(Map<? extends K, ? extends V> m); //清除map中所有的鍵值對，該操作完成后，該map就是空的了 void clear(); //將map中所有的key返回，由于map中的key是不能重復(fù)的，所以用Set集合的方式裝載所有的key Set<K> keySet(); //將map中所有的value返回，由于map中的value是可重復(fù)的，所以用Collection集合的方式裝載所有的value Collection<V> values(); //將map中所有的鍵值對Entry返回，由于map中的鍵值對是不可重復(fù)的（key不可重復(fù)），所以用Set集合的方式裝載所有的value Set<Map.Entry<K, V>> entrySet(); //Map中承載鍵值對的數(shù)據(jù)結(jié)構(gòu)Entry interface Entry<K,V> { //返回鍵值對的鍵值key K getKey(); //返回鍵值對的value值 V getValue(); //將當(dāng)前鍵值對的value值 替換為指定的value值 V setValue(V value); //判斷指定的對象和當(dāng)前鍵值對是否equals相等，若相等，則代表是同一個鍵值對； boolean equals(Object o); //返回當(dāng)前鍵值對的hashCode值 int hashCode(); } //判斷指定對象和當(dāng)前Map的equals是否相等 boolean equals(Object o); //返回當(dāng)前Map的hashCode int hashCode(); }
下面我們具體的看一下HashMap： //HashMap是基于hash表來實現(xiàn)Map接口的，HashMap維護(hù)了下面幾個變量： //HashMap默認(rèn)的初始化大小為16 static final int DEFAULT_INITIAL_CAPACITY = 16; //HashMap包含鍵值對的最大容量為2^30,HashMap的容量一定要是2的整數(shù)次冪 static final int MAXIMUM_CAPACITY = 1 << 30; //默認(rèn)的加載因子為0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //裝載鍵值對的內(nèi)部容器Entry數(shù)組，長度一定得是2的冪 transient Entry[] table; //HashMap中包含的鍵值對的個數(shù) transient int size; //HashMap的極限 當(dāng)鍵值對的個數(shù)達(dá)到threshold時，數(shù)組table要擴容的 int threshold; //加載因子 final float loadFactor; //HashMap結(jié)構(gòu)上被改變的次數(shù)，結(jié)構(gòu)上的改變包括：鍵值對的大小的改變，修改HashMap的內(nèi)部結(jié)構(gòu)（比較進(jìn)行了rehash操作），此屬性用來保持fail-fast transient volatile int modCount; 接下來我們看一下HashMap的構(gòu)造函數(shù)： /** *根據(jù)指定的容量initialCapacity和加載因子loadFactor構(gòu)造HashMap */ public HashMap(int initialCapacity, float loadFactor) { //對initialCapacity進(jìn)行參數(shù)校驗，若小于0，則拋出IllegalArgumentException異常 if (initialCapacity < 0) throw new IllegalArgumentException('Illegal initial capacity: ' initialCapacity); //若initialCapacity大于MAXIMUM_CAPACITY(2^30),則將MAXIMUM_CAPACITY賦值給initialCapacity if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //對參數(shù)loadFactor進(jìn)行有效性校驗，不能<=0,不能非數(shù)字，否則拋出IllegalArgumentException異常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException('Illegal load factor: ' loadFactor); // Find a power of 2 >= initialCapacity 找到一個2的冪的數(shù)capacity，使其不小于參數(shù)initialCapacity int capacity = 1; //若capacity小于initialCapacity,則將capacity擴大一倍 while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; //設(shè)置極限，大小為 capacity * loadFactor,即(容量*負(fù)載因子) threshold = (int)(capacity * loadFactor); //創(chuàng)建一個大小為capacity的Entry數(shù)組table,用來保存鍵值對 table = new Entry[capacity]; //調(diào)用方法init(),進(jìn)行額外的初始化操作 init(); } //init方法是空的，如果你定制額外的初始化操作，可以繼承HashMap，覆蓋init()方法 void init() { } //通過指定的容量initialCapacity來構(gòu)造HashMap，這里使用了默認(rèn)的加載因子DEFAULT_LOAD_FACTOR 0.75 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //無參的構(gòu)造函數(shù) 加載因子為DEFAULT_LOAD_FACTOR 0.75，容量為默認(rèn)的DEFAULT_INITIAL_CAPACITY 16，極限為 16*0.75=12 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
下面我們看一下HashMap中承載鍵值對的數(shù)據(jù)結(jié)構(gòu)Entry的實現(xiàn),Entry<K,V>是HashMap的一個靜態(tài)內(nèi)部類 /** *Entry是HashMap里面承載鍵值對數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)了Map接口里面的Entry接口，除了方法recordAccess(HashMap<K,V> m),recordRemoval(HashMap<K,V> m)外，其他方法均為final方法，表示即使是子類也不能覆寫這些方法。 */ static class Entry<K,V> implements Map.Entry<K,V> { //鍵值,被final修飾，表明一旦賦值，不可修改 final K key; //value值 V value; //下一個鍵值對的引用 Entry<K,V> next; //當(dāng)前鍵值對中鍵值的hash值 final int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } //設(shè)置value值，返回原來的value值 public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } //比較鍵值對是否equals相等，只有鍵、值都相等的情況下，才equals相等 public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); //若k1 == k2(k1,k2引用同一個對象),或者k1.equals(k2)為true時，進(jìn)而判斷value值是否相等 if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); //若v1 == v2(v1,v2引用同一個對象),或者v1.equals(v2)為true時，此時才能說當(dāng)前的鍵值對和指定的的對象equals相等 if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } //其他均為false return false; } public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() '=' getValue(); } //此方法只有在key已存在的時候調(diào)用m.put(key,value)方法時，才會被調(diào)用，即覆蓋原來key所對應(yīng)的value值時被調(diào)用 void recordAccess(HashMap<K,V> m) { } //此方法在當(dāng)前鍵值對被remove時調(diào)用 void recordRemoval(HashMap<K,V> m) { } }
下面是Hash的put方法的實現(xiàn)： /** *將指定的鍵key,值value放到HashMap中 */ public V put(K key, V value) { //首先判斷鍵key是否為null,若為null,則調(diào)用putForNullKey(V v)方法完成put if (key == null) return putForNullKey(value); //程序走到這，說明key不為null了，先調(diào)用hash(int)方法，計算key.hashCode的hash值 int hash = hash(key.hashCode()); //再調(diào)用indexFor(int,int)方法求出此hash值對應(yīng)在table數(shù)組的哪個下標(biāo)i上 (bucket桶) int i = indexFor(hash, table.length); //遍歷bucket桶上面的鏈表元素，找出HashMap中是否有相同的key存在，若存在，則替換其value值，返回原來的value值 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //若元素e.hash值和上面計算的hash值相等，并且(e.key == 入?yún)ey,或者入?yún)ey equals 相等 e.key)，則說明HashMap中存在了和入?yún)⑾嗤膋ey了，執(zhí)行替換操作 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; //在執(zhí)行替換操作的時候，調(diào)用Entry對象的recordAccess(HashMap<K,V> m)方法，這個上面說過了 e.recordAccess(this); return oldValue; } } //程序走到這，說明原來HashMap中不存在key,則直接將鍵值對插入即可，由于插入元素，修改了HashMap的結(jié)構(gòu)，因此將modeCount 1 modCount ; //調(diào)用addEntry(int,K,V,int)方法進(jìn)行鍵值對的插入 addEntry(hash, key, value, i); //由于原來HashMap中不存在key，則不存在替換value值問題，因此返回null return null; }  當(dāng)key為null時，HashMap是這樣進(jìn)行數(shù)據(jù)插入的： //先看看HashMap中原先是否有key為null的鍵值對存在，若存在，則替換原來的value值；若不存在，則將key為null的鍵值對插入到Entry數(shù)組的第一個位置table[0] private V putForNullKey(V value) { //獲取Entry數(shù)組的第一個元素:table[0],然后通過e.next進(jìn)行鏈表的遍歷，若遍歷過程中有元素e.key為null,則替換該元素的值 for (Entry<K,V> e = table[0]; e != null; e = e.next) { //說明原來之前HashMap中就已經(jīng)存在key問null的鍵值對了，現(xiàn)在又插入了一個key為null的新元素，則替換掉原來的key為null的value值 if (e.key == null) { V oldValue = e.value; e.value = value; //在執(zhí)行替換操作的時候，調(diào)用Entry對象的recordAccess(HashMap<K,V> m)方法，這個上面說過了 e.recordAccess(this); return oldValue; } } //程序走到這，說明HashMap中原來沒有key為null的鍵值對，需要直接插入元素，由于插入元素，修改了HashMap的結(jié)構(gòu)，因此將modeCount 1 modCount ; //調(diào)用addEntry(int,K,V,int)方法進(jìn)行鍵值對的插入,這里將入?yún)ash設(shè)置為0，K為null,插入的位置index也為0，說明key為null的元素插入在bucket[0]第一個桶上 addEntry(0, null, value, 0); return null; }
HashMap在插入數(shù)據(jù)之前，要根據(jù)key值和hash算法來計算key所對應(yīng)的hash值 //根據(jù)key的hashCode值，來計算key的hash值 static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** *在HashMap中要找到某個元素，需要根據(jù)key的hash值來求得對應(yīng)數(shù)組中的位置,如何計算這個位置就是hash算法. *HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合,所以我們當(dāng)然希望這個HashMap里面的元素位置盡量的分布均勻些，盡量使得每個位置上的元素數(shù)量只有一個, *那么當(dāng)我們用hash算法求得這個位置的時候，馬上就可以知道對應(yīng)位置的元素就是我們要的，而不用再去遍歷鏈表. *所以我們首先想到的就是把hashcode對數(shù)組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的,但是，“?！边\算的消耗還是比較大的， *能不能找一種更快速，消耗更小的方式那？java中時這樣做的 :將hash值和數(shù)組長度按照位與&來運算 */ static int indexFor(int h, int length) { return h & (length-1); } 下面我們看一看實際進(jìn)行數(shù)據(jù)添加的操作addEntry方法 /** *將指定的key,value,hash,bucketIndex 插入鍵值對，若此時size 大于極限threshold,則將Entry數(shù)組table擴容到原來容量的兩倍 */ void addEntry(int hash, K key, V value, int bucketIndex) { //取出原來bucketIndex處的鍵值對e Entry<K,V> e = table[bucketIndex]; //創(chuàng)建一個新的鍵值對，使用給定的hash、key、value,并將新鍵值對的next屬性指向e,最后將新鍵值對放在bucketIndex處 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //將size 1,若此時size 大于極限threshold,則將Entry數(shù)組table擴容到原來容量的兩倍 if (size >= threshold) //調(diào)用resize(int)方法，進(jìn)行數(shù)組的擴容 resize(2 * table.length); }
我們知道HashMap采用的數(shù)組 鏈表來實現(xiàn)的，當(dāng)HashMap中元素的個數(shù)size大于極限threshold時，會進(jìn)行數(shù)組的擴容操作，這個操作使用resize(int newCapacity)方法實現(xiàn)的： /** *將HashMap中Entry數(shù)組table的容量擴容至新容量newCapacity,數(shù)組的擴容不但涉及到數(shù)組元素的復(fù)制，還要將原數(shù)組中的元素rehash到新的數(shù)組中，很耗時;如果能預(yù)估到放入HashMap中元素的大小，最好使用new HashMap(size)方式創(chuàng)建足夠容量的HashMap，避免不必要的數(shù)組擴容(rehash操作)，提高效率 */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果原數(shù)組的大小已經(jīng)為允許的最大值MAXIMUM_CAPACITY了，則不能進(jìn)行擴容了，這里僅僅將極限threshold設(shè)置為Integer.MAX_VALUE，然后返回 if (oldCapacity == MAXIMUM_CAPACITY) { //將極限threshold設(shè)置為Integer.MAX_VALUE threshold = Integer.MAX_VALUE; return; } //程序走到這，說明可以進(jìn)行擴容，先創(chuàng)建容量為newCapacity的新Entry數(shù)組newTable Entry[] newTable = new Entry[newCapacity]; //調(diào)用tranfer(Entry[] newTable)方法，進(jìn)行數(shù)組元素的移動和rehashing transfer(newTable); //將新數(shù)組newTable賦值給table table = newTable; //計算極限threshold的最新值 threshold = (int)(newCapacity * loadFactor); } //將原Entry數(shù)組table中的所有鍵值對遷移到新Entry數(shù)組newTable上 void transfer(Entry[] newTable) { //原數(shù)組賦值給src Entry[] src = table; //新數(shù)組長度為newCapacity int newCapacity = newTable.length; //遍歷原數(shù)組 for (int j = 0; j < src.length; j ) { //獲取原數(shù)組中的元素(鍵值對),賦值給e Entry<K,V> e = src[j]; //若元素e不為null if (e != null) { //將當(dāng)前元素設(shè)值為null src[j] = null; //遍歷元素e所對應(yīng)的bucket桶內(nèi)的所有元素 do { //獲取下一個元素next Entry<K,V> next = e.next; //重新計算鍵值對e在新數(shù)組newTable中的bucketIndex位置(即rehash操作) int i = indexFor(e.hash, newCapacity); //這步操作，說實話，沒看懂，有清楚的，請不吝賜教 e.next = newTable[i]; //將當(dāng)前元素e放入新數(shù)組的i位置 newTable[i] = e; //將下一個元素next賦值給當(dāng)前元素，以便完成遍歷 e = next; } while (e != null); } } }
下面我們看一下HashMap檢索數(shù)據(jù)的操作： //獲取指定key所對應(yīng)的value值 public V get(Object key) { //若key==null,則直接調(diào)用getForNullKey()方法 if (key == null) return getForNullKey(); //到這說明key != null,先獲取key的hash值 int hash = hash(key.hashCode()); //在indexFor(int hash,int length)獲取key落在Entry數(shù)組的哪個bucket桶上，獲取該bucket桶上的元素e,進(jìn)而遍歷e的鏈表，找相對應(yīng)的key,若找到則返回key所對應(yīng)的value值，找不到則返回null for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //若元素e.hash == 上面計算的hash值，并且(e.key 和入?yún)ey是同一個對象的引用，或者e.key和入?yún)ey equals相等)， //則認(rèn)為入?yún)ey和當(dāng)前遍歷的元素e的key是同一個,返回e的value值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } //上面遍歷了一遍也沒有找到，則返回null return null; } //獲取key為null的value值，由上面putForNullKey方法可知，key為null的鍵值對，被放在了Entry數(shù)組table的第一個bucket桶(table[0]) private V getForNullKey() { //獲取Entry數(shù)組table的第一個元素e,從e開始往下遍歷，若找到元素e.key 為null的，則直接返回該元素e.value值 for (Entry<K,V> e = table[0]; e != null; e = e.next) { //找到元素e.key 為null的，則直接返回該元素e.value值 if (e.key == null) return e.value; } //從table[0]開始，遍歷鏈表一遍，沒有找到key為null的，則返回null return null; } //獲取指定key所對應(yīng)的鍵值對Entry,先獲取key的hash值，再獲取該hash值應(yīng)放入哪個hash桶，然后遍歷該桶中的鍵值對，若有則返回該鍵值對；若沒有則返回null final Entry<K,V> getEntry(Object key) { //若key為null,則hash值為0；若key != null,則利用hash(int)計算key的hash值 int hash = (key == null) ? 0 : hash(key.hashCode()); //獲取該hash值應(yīng)放入哪個hash桶,并遍歷該hash桶 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //若元素e.hash == hash,并且(e.key == key，或者 key.equals(e.key)為true)，則認(rèn)為入?yún)ey和當(dāng)前遍歷的元素e.key是同一個，返回該元素e if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } //若沒有則返回null return null; }
//判斷HashMap中是否含有指定key的鍵值對，內(nèi)部用getEntry(Object key)來實現(xiàn) public boolean containsKey(Object key) { return getEntry(key) != null; }
//將指定Map中的所有元素(鍵值對)拷貝到當(dāng)前HashMap中，對于當(dāng)前HashMap中存在的key,則進(jìn)行value值的替換 public void putAll(Map<? extends K, ? extends V> m) { //若指定的Map中沒有元素，則直接返回 int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; //若必要，則進(jìn)行數(shù)組的擴容 if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; //計算新的容量 int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; //若新容量大于目前數(shù)組的長度，則調(diào)用resize(int)進(jìn)行擴容 if (newCapacity > table.length) resize(newCapacity); } //獲取指定Map的迭代器，循環(huán)調(diào)用put(K k,V v)方法，進(jìn)行鍵值對的插入 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); put(e.getKey(), e.getValue()); } }
下面看下HashMap的remove操作： /** * 刪除指定key所對應(yīng)的元素 */ public V remove(Object key) { //調(diào)用方法reomveEntryForKey(Object key)來刪除并獲取指定的entry Entry<K,V> e = removeEntryForKey(key); //若entry為null，則返回null；否則返回entry的value值 return (e == null ? null : e.value); } /** *移除并返回指定key所關(guān)聯(lián)的鍵值對entry,若HashMap中沒有鍵值對和指定的key相關(guān)聯(lián)，則返回null */ final Entry<K,V> removeEntryForKey(Object key) { //若key為null,則hash值為0；若key != null,則利用hash(int)計算key的hash值 int hash = (key == null) ? 0 : hash(key.hashCode()); //獲取key應(yīng)放入的在數(shù)組中的位置索引i int i = indexFor(hash, table.length); //標(biāo)識前一個元素 Entry<K,V> prev = table[i]; //標(biāo)識遍歷過程中的當(dāng)前元素 Entry<K,V> e = prev; //遍歷bucket桶table[i]中的元素，尋找對應(yīng)的key while (e != null) { //當(dāng)前元素的下一個元素 Entry<K,V> next = e.next; Object k; //元素e.hash和上面計算的hash值相等，并且(key == e.key 或者key.equals(e.key) 為true)，說明找到了指定key所對應(yīng)的鍵值對 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { //由于刪除了一個元素，修改了HashMap的結(jié)構(gòu)，因此將modCount 1 modCount ; //將size-1 size--; //若待查找的元素為桶內(nèi)的第一個元素，則當(dāng)前元素的下一個元素next放入數(shù)組中位置i中 if (prev == e) table[i] = next; //否則將上一個元素的next屬性指向 當(dāng)前元素的next else prev.next = next; //當(dāng)元素被remove時，調(diào)用Entry對象的recordRemove(Map<K,V> m)方法 e.recordRemoval(this); //返回找到的當(dāng)前元素 return e; } //程序走到這，說明當(dāng)前元素不是要查找的元素；則將當(dāng)前元素賦值給上一個元素，將下一個元素賦值給當(dāng)前元素，以完成遍歷 prev = e; e = next; } return e; }
//判斷HashMap中是否包含指定的對象value public boolean containsValue(Object value) { //若value為null，則調(diào)用containsNullValue()方法處理 if (value == null) return containsNullValue(); //將數(shù)組table賦值給tab Entry[] tab = table; //遍歷數(shù)組tab的每個索引位置(此層循環(huán)對應(yīng)數(shù)組結(jié)構(gòu)) for (int i = 0; i < tab.length ; i ) //對應(yīng)指定的索引位置i,遍歷在索引位置i上的元素(此層循環(huán)對應(yīng)鏈表結(jié)構(gòu)) for (Entry e = tab[i] ; e != null ; e = e.next) //若某個元素e.value和指定的value equals相等，則返回true if (value.equals(e.value)) return true; //遍歷完成沒有找到對應(yīng)的value值，返回false return false; } //判斷HashMap是否包含value為null的元素 private boolean containsNullValue() { //將數(shù)組table賦值給tab Entry[] tab = table; //遍歷數(shù)組tab的每個索引位置(此層循環(huán)對應(yīng)數(shù)組結(jié)構(gòu)) for (int i = 0; i < tab.length ; i ) //對應(yīng)指定的索引位置i,遍歷在索引位置i上的元素(此層循環(huán)對應(yīng)鏈表結(jié)構(gòu)) for (Entry e = tab[i] ; e != null ; e = e.next) //若某個元素e.value == null，則返回true if (e.value == null) return true; //沒有找到value值為null的，返回false return false; }
//清除HashMap中所有的鍵值對，此操作過后，HashMap就是空的了 public void clear() { //要刪除所有的元素，肯定會對HashMap的結(jié)構(gòu)造成改變，因此modCount 1 modCount ; Entry[] tab = table; //遍歷數(shù)組，將數(shù)組中每個索引位置的設(shè)置為null for (int i = 0; i < tab.length; i ) tab[i] = null; //將size 修改為0 size = 0; }
現(xiàn)在看一下上面沒有講的一個構(gòu)造函數(shù): //構(gòu)造一個新的HashMap，以承載指定Map中所有的鍵值對，使用默認(rèn)的加載因子DEFAULT_LOAD_FACTOR public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); //調(diào)用putAllForCreate(Map<? extends K, ? extends V>)方法完成元素的遷移 putAllForCreate(m); } private void putAllForCreate(Map<? extends K, ? extends V> m) { for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); //在迭代器循環(huán)中調(diào)用putForCreate(K k,V v)來實現(xiàn)元素的創(chuàng)建 putForCreate(e.getKey(), e.getValue()); } } //該方法和put方法不同，它不會進(jìn)行數(shù)組的擴容resize,和對modCount的檢查 private void putForCreate(K key, V value) { //若key為null,則hash值為0；若key != null,則利用hash(int)計算key的hash值 int hash = (key == null) ? 0 : hash(key.hashCode()); //求key應(yīng)該放入哪個hash桶(bucket)內(nèi) int i = indexFor(hash, table.length); //遍歷鏈表，若key之前在Map中已經(jīng)有了，則直接返回 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } //調(diào)用createEntry(int hash,K k,V v,int bucketIndex)方法完成鍵值對的創(chuàng)建并加入到鏈表中 createEntry(hash, key, value, i); } void createEntry(int hash, K key, V value, int bucketIndex) { //將bucketIndex位置的元素取出來 Entry<K,V> e = table[bucketIndex]; //創(chuàng)建一個新的鍵值對，使用給定的hash、key、value,并將新鍵值對next指向e,最后將新鍵值對放在bucketIndex處 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //將數(shù)組大小size 1 size ; }
下面我們講下HashMap的負(fù)載因子loadfactor, 所謂負(fù)載因子就是散列表的實際元素數(shù)目(n)/散列表的容量(m), 它衡量的是一個散列表的空間的使用程度，默認(rèn)情況下loadfactor是0.75，它的作用是當(dāng)HashMap中元素的個數(shù)size 大于(HashMap的容量capacity * 負(fù)載因子loadfactor)時，該HashMap便會進(jìn)行擴容resize。 我們先說下hash沖突： 當(dāng)利用HashMap存數(shù)據(jù)的時候，先根據(jù)key的hashcode值來計算key的hash值(利用hash函數(shù))，再根據(jù)hash值來計算該key在數(shù)組table中的位置index（hash & (length-1)）,比如我們要存兩個鍵值對key1-value1和key2-value2, 如果key1、key2分別通過hash函數(shù)計算的hash值hash1、hash值hash2 相等，那key1和key2一定會落在數(shù)組table的同一個位置上，這就產(chǎn)生了沖突，這個沖突是由不同的key值但是卻相同的hash值引起的，稱之為hash沖突。HashMap解決hash沖突的方式就是鏈表，雖然key1-value1和key2-value2這兩個鍵值對落在了數(shù)組table的同一個位置上，但是它們是鏈表的方式連接在一起，當(dāng)HashMap查找key1時，就需要遍歷這個鏈表了。 當(dāng)負(fù)載因子越大的時候，出現(xiàn)hash沖突的可能性越大，這意味著數(shù)組table中某個具體的桶bucket上不止有一個元素（此時就構(gòu)成了鏈表了）可能性增大，在檢索數(shù)據(jù)的時候需要遍歷鏈表的可能性增大，因此檢索的效率就比較低（耗時長），但是空間的利用率越高。 當(dāng)負(fù)載因子越小的時候，出現(xiàn)hash沖突的可能性越小，這意味著數(shù)組table中某個具體的桶bucket上不止有一個元素（此時就構(gòu)成了鏈表了）可能性減小了，在檢索數(shù)據(jù)的數(shù)據(jù)需要遍歷鏈表的可能性減小，因此檢索的效率就比較高，但是空間利用率越低。 上面的源碼解析了提到了HashMap的容量一定得是2的整數(shù)此冪(2^n),這又是問什么呢？ 通過上面的源碼我們知道：根據(jù)hash值求該hash值在數(shù)組中的位置的實現(xiàn)是： hash & (length-1)，當(dāng)數(shù)組table的長度length為2的整數(shù)次冪的時候，那（length-1）二進(jìn)制表示形式從低位開始一定都是1，直到為0，如果length依次為2,4,8,16,32，64，則(length-1)一次為1,3,7,15,31,63，那(length-1)的二進(jìn)制形式依次為1,11,111,1111,11111，我們知道二進(jìn)制的與運算&，當(dāng)一方位數(shù)全是1的時候，進(jìn)行&運算的結(jié)果完全取決于另外一方。 比如從0開始到15,依次和15進(jìn)行&運算，看看結(jié)果的平均分布情況：
通過位與&操作后，發(fā)現(xiàn)0-15完全平均的落在了數(shù)組的各個索引位置 下面通過一個小例子予以驗證： public class HashDemo { private final int[] table; public HashDemo(int size) { this.table = new int[size]; for (int i = 0; i < size; i ) { table[i] = i; } } //求key所對應(yīng)的在數(shù)組中的位置 public int index(int key){ //求hash值 int hash = hash(key); //返回key所對應(yīng)的在數(shù)組中的位置 return hash & (table.length-1); } //HashMap中hash函數(shù)的實現(xiàn),求hash值 public int hash(int h){ h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } public static void main(String[] args) { Map<String,Integer> keyToNumber = new HashMap<String, Integer>(); int size = 16; HashDemo hashDemo = new HashDemo(size); int testSize = 1000; for (int i = 0; i < testSize; i ) { int index = hashDemo.index(i); Integer number = keyToNumber.get('key' index); if (number == null) { keyToNumber.put('key' index,1); }else { keyToNumber.put('key' index,keyToNumber.get('key' index) 1); } } Iterator<Map.Entry<String, Integer>> it = keyToNumber.entrySet().iterator(); while (it.hasNext()) { Map.Entry<String, Integer> entry = it.next(); System.out.println(entry.getKey() ' == ' entry.getValue()); } } } 當(dāng)我們將size設(shè)置為16 （2的4次冪）時，控制臺輸出： key4 == 62 由上面的輸出可見，數(shù)據(jù)非常平均的分配在了數(shù)組的16個索引位置， 當(dāng)size設(shè)置為非2的整數(shù)次冪的時候，比如50，這時控制臺輸出： key0 == 120 由此可見1000個數(shù)據(jù)只分配在了8個索引位置上。
使用HashMap的注意事項： 1.HashMap采用數(shù)組 鏈表的形式存儲數(shù)據(jù)，當(dāng)預(yù)先知道要存儲在HashMap中數(shù)據(jù)量的大小時，可以使用new HashMap(int size)來指定其容量大小，避免HashMap數(shù)組擴容導(dǎo)致的元素復(fù)制和rehash操作帶來的性能損耗。 2.HashMap是基于Hash表、實現(xiàn)了Map接口的，查找元素的時候，先根據(jù)key計算器hash值，進(jìn)而求得key在數(shù)組中的位置，但是要盡量避免hash沖突造成的要遍歷鏈表操作，因此在我們手動指定HashMap容量的時候，容量capacity一定得是2的整數(shù)次冪，這樣可以讓數(shù)據(jù)平均的分配在數(shù)組中，減小hash沖突，提高性能。 3.HashMap是非線程安全的，在多線程條件下不要使用HashMap，可以使用ConcurrentHashMap代替。
|
|
|
