jdk_Collection_HashMap源碼深入解讀

涅槃沉殤 2018-01-05

展開(kāi)全文

源碼

package com.collection.Map;
import java.util.Set;

public interface Map<K,V> {

interface Entry<K,V> {

K getKey();

V getValue();

V setValue(V v);

boolean equals(Object o);

int hashCode();

}

int size();
boolean isEmpty();
V put(K k,V v);
V get(K k);
V remove(Object k);
Set<Map.Entry<K, V>> entrySet();
boolean containsKey(Object k);
boolean containsValue(Object v);
}

package com.collection.Map;

import .Serializable;
import java.util.AbstractSet;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;

public class HashMap<K, V>
implements Map<K,V>, Cloneable, Serializable{

/**
*
*/
private static final long serialVersionUID = 1L;

private static final int DEFAULT_INITIAL_CAPACITY = 16; //hashMap 初始容量

private static final float DEFAULT_LOAD_FACTOR = 0.75f; //默認(rèn)--加載因子

static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量為2的30次方

int threshold;//容量的0.75倍超過(guò)它以2倍擴(kuò)容方式擴(kuò)容
//final float loadFactor;

transient Entry<K,V>[] table;

final float loadFactor;//加載因子
transient int modCount;//HashMap被改變的次數(shù)
transient int size;//寬度

private transient Set<com.collection.Map.Map.Entry<K, V>> entrySet = null;

public Set<com.collection.Map.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return entrySet0();
}

private Set<com.collection.Map.Map.Entry<K, V>> entrySet0() {
Set<com.collection.Map.Map.Entry<K, V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}

private final class EntrySet extends AbstractSet<com.collection.Map.Map.Entry<K, V>>
{
@SuppressWarnings("unchecked")
public Iterator<com.collection.Map.Map.Entry<K, V>> iterator() {
return newEntryIterator();
}

@Override
public int size() {
// TODO Auto-generated method stub
return size;
}

}

private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry

HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}

public final boolean hasNext() {
return next != null;
}

final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();

if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}

}

public HashMap() {
// 設(shè)置“加載因子”為默認(rèn)加載因子0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 設(shè)置“HashMap閾值”，當(dāng)HashMap中存儲(chǔ)數(shù)據(jù)的數(shù)量達(dá)到threshold時(shí)，就需要將HashMap的容量加倍,。
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
// 創(chuàng)建Entry數(shù)組,，用來(lái)保存數(shù)據(jù)
table = new Entry[DEFAULT_INITIAL_CAPACITY];
}

public com.collection.Map.HashMap.EntryIterator newEntryIterator() {
// TODO Auto-generated method stub
return new EntryIterator();
}

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {

public Map.Entry<K,V> next() {
return nextEntry();
}
@Override
public void remove() {
// TODO Auto-generated method stub

}
}

public int hash(Object k) {
int h;
return (k==null)?0:(h=k.hashCode())^(h>>>16);
}

int indexFor(int hash, int newLength) {
// TODO Auto-generated method stub
return hash&(newLength-1);
}

static class Entry<K,V> implements Map.Entry<K, V>
{
  final K k;
  V v;
  Entry<K,V> next;
  int hash;


public Entry(int h, K k, V v, Entry<K,V> n) {
this.k = k;
this.v = v;
this.next = n;
this.hash = h;
}

@Override
public K getKey() {
return k;
}

@Override
public V getValue() {
return v;
}

@Override
public V setValue(V v) {
V oldValue = this.v;
this.v = v;
return oldValue;
}

}




@Override
public int size() {
// TODO Auto-generated method stub
return size;
}

@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return size==0;
}

@Override
public V remove(Object key) {

Entry<K,V> e = removeEntryForKey(key);

return e==null?null:e.v;
}

private Entry<K,V> removeEntryForKey(Object key) {
int findHash = (key==null)?0:hash(key);
int i = indexFor(findHash,table.length);

Entry<K,V> prev = table[i];
Entry<K,V> e = prev;

while (e!=null)
{
Entry<K,V> next = e.next;
Object k;

//當(dāng)前對(duì)象等于刪除對(duì)象
if(e.hash==findHash&&((k=e.k)==k||key!=null&&key.equals(k)))
{
modCount++;
size--;

if(prev==e)
{
table[i] = next;
}
else
{
prev.next = next;
}
return e;
}

prev = e;
e = next;
}
return null;

}

@Override
public boolean containsKey(Object k) {
return getEntry(k)!=null;
}

private Entry<K,V> getEntry(Object key) {
int hash = (key==null)?0:hash(key);
for (Entry<K,V> e = table[indexFor(hash,table.length)];e!=null; e = e.next)
{
Object k;

if(e.hash==hash&&((k=e.k)==k||key!=null&&key.equals(k)) )
{
return e;
}
}
return null;
}

@Override
public boolean containsValue(Object v) {
if(v==null)
{
return containsNullValue(v);
}

Entry[] tab = table;

for(int i=0; i<tab.length; i++)
{
for(Entry<K,V> e = tab[i]; e!=null; e= e.next)
{
if(v.equals(e.v))
{
return true;
}
}
}
return false;
}

private boolean containsNullValue(Object value) {
Entry<K, V>[] tab = table;

for (int i=0; i<tab.length;i++)
{
for(Entry<K,V> e = tab[i];e!=null; e= e.next)
{
if(e.v==null)
{
return true;
}
}
}

return false;
}

@Override
public V put(K key,V value)
{
if(key==null)
{
return putForNullKey(value);
}

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

for (Entry<K,V> e = table[i]; e!=null; e = e.next )
{
Object k = null;

if(e.hash==hash && ((k=e.k) == key)||(key.equals(k)) )
{
V olaValue = e.v;
e.v = value;
return olaValue;
}

}
modCount++;
addEntry(hash, key, value, i);
return null;
}

//單獨(dú)處理鍵值為null的
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0];e!=null;e = e.next )
{
if(e.getKey()==null)
{
V oldValue = e.v;
e.v = value;
return oldValue;
}
}

modCount++;
//
addEntry(0,null,value,0);
return null;

}

private void addEntry(int h, K key, V value, int j) {
Entry<K,V> e = table[j];
//int h, K k, V v, Entry<K,V> n-----總是讓新的entry 指向舊的entry
table[j] = new Entry<K,V>(h, key,value,e);

//threshold 超過(guò)擴(kuò)充值
if(size++>threshold)
{
resize(2*table.length);
}
}

private void resize(int i) {
Entry[] oldTable = table;
int oldCapaCity = oldTable.length;

//容量已經(jīng)達(dá)到最大值
if(oldCapaCity > MAXIMUM_CAPACITY)
{
// 設(shè)置為Integer 最大值
threshold = Integer.MAX_VALUE;
return ;
}

Entry[] newTbale = new Entry[i];

//oldtbale 舊內(nèi)容copy到 newTable
transfer(newTbale);
}

private void transfer(Entry[] newTable) {
Entry[] copyFrom = table;
int newLength = newTable.length;

for (int j=0; j<table.length; j++)
{
Entry e = copyFrom[j];

if(e!=null)
{
copyFrom[j] = null;

do
{
Entry next = e.next;

// 根據(jù)新的容量計(jì)算e在新數(shù)組中的位置
int i = indexFor(e.hash, newLength);
// 將e插入到newTable[i]指向的鏈表的頭部
e.next = newTable[i];
newTable[i] = e;//給新數(shù)組賦值

//拿到下一個(gè)繼續(xù)執(zhí)行程序
e = next;

}
while(e!=null);

}
}

}

public V get(Object key)
{
if(key==null)
{
return getForNullKey();
}

int hash = hash(key);
int i = indexFor(hash, table.length);

for (Entry<K,V> e = table[i]; e!=null; e = e.next )
{
Object k = null;

if(hash==e.hash&&( (k=e.k)==key) || (key.equals(k)) )
{
return e.v;
}
}
return null;

}

private V getForNullKey() {
for (Entry<K,V> e = table[0];e!=null;e = e.next)
{
if(e.k == null)
{
return e.v;
}
}
return null;
}
}

1.jdk HashMap 設(shè)計(jì)思路

以下內(nèi)容是我結(jié)合了網(wǎng)友的資料自己整理下

http://blog.csdn.net/lyandyhk/article/details/51147012

https://www.zhihu.com/question/20733617

1.擾動(dòng)函數(shù)

以下這段代碼叫做擾動(dòng)函數(shù) jdk8有所優(yōu)化

jdk 1.7

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

jdk 1.8

static int hash(int h) {
   int h;

   return (key==null):0:(key.hashCode())^(h>>16);
}

從上面代碼看出來(lái)key.hashCode 是int類型長(zhǎng)度-2147483648到2147483648 顯然這個(gè)長(zhǎng)度數(shù)組內(nèi)存是放不下 40億

所以這個(gè)散列值不能直接拿來(lái)用,，用之前還要對(duì)數(shù)組的長(zhǎng)度取摸運(yùn)算

static int indexFor(int h, int length) {
        return h & (length-1);
    }

為什么數(shù)組的長(zhǎng)度要是2的整數(shù)冪,？ 因?yàn)樵O(shè)計(jì)組成的二進(jìn)制長(zhǎng)度只有低位掩碼

（HashMap的初始大小和擴(kuò)容都是以2的次方來(lái)進(jìn)行的,，換句話說(shuō)length-1換成二進(jìn)制永遠(yuǎn)是全部為1,，

比如容量為16,，則length-1為1111）

h中對(duì)應(yīng)位取0,對(duì)應(yīng)位結(jié)果為0，h對(duì)應(yīng)位取1,，對(duì)應(yīng)位結(jié)果為1,。這樣就有兩個(gè)結(jié)果），但是如果length-1中某一位為0,，則不論h中對(duì)應(yīng)位的數(shù)字為幾,，

對(duì)應(yīng)位結(jié)果都是0，這樣就讓兩個(gè)h取到同一個(gè)結(jié)果,，這就是hash沖突了,，恰恰length-1又是全部為1的數(shù)，所以結(jié)果自然就將hash沖突最小化了

列如初始長(zhǎng)度16-1

15 的二進(jìn)制數(shù)00000000 00000000 00001111 假設(shè)與其他二進(jìn)制數(shù)做&運(yùn)算

列如下面做位運(yùn)算

11110000 00000000 00001111

00000000 00000000 00001111

0111結(jié)果就是保留低四位 但是這樣做 還是有碰撞

擾動(dòng)函數(shù)在這個(gè)時(shí)候 價(jià)值就體現(xiàn)出來(lái)

h = hashCode()

hash碼 高位16 和地低位的16 做了一個(gè)異或 以此來(lái)加大低位的隨機(jī)性

但明顯Java 8覺(jué)得擾動(dòng)做一次就夠了,，做4次的話,，多了可能邊際效用也不大，所謂為了效率考慮就改成一次了,。

h%length與h&（length-1）得到是同一個(gè)值

1.length（2的整數(shù)次冪）的特殊性導(dǎo)致了length-1的特殊性（二進(jìn)制全為1）
2.位運(yùn)算快于十進(jìn)制運(yùn)算,，hashmap擴(kuò)容也是按位擴(kuò)容，所以相比較就選擇了后者

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購(gòu)買(mǎi)等信息,，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請(qǐng)點(diǎn)擊一鍵舉報(bào),。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：涅槃沉殤 > 《jdk_Collection_HashMap》

舉報(bào)/認(rèn)領(lǐng)