參考
參考
參考Yikun
參考Java7 HashMap分析
參考CSDN
HashMap是一個(gè)散列鏈表，它由數(shù)組作為容器，每一個(gè)元素是一個(gè)鏈表。在創(chuàng)建HashMap的時(shí)候會(huì)根據(jù)默認(rèn)的臨界域創(chuàng)建一個(gè)長度是n的2次方的數(shù)組，因?yàn)樵氐奈恢糜蒱ash和lenght共同決定
當(dāng)length是n^2時(shí)，可以更好的減少碰撞。在插入元素時(shí)首先會(huì)遍歷容器是否有相同的元素。如果有會(huì)覆蓋之前的元素。如果沒有在當(dāng)前位置鏈表頭結(jié)點(diǎn)放置新的元素，如果原先的位置有元素，那么新元素指向老的元素形成鏈表。在查找元素的時(shí)候會(huì)遍歷數(shù)組中的每一個(gè)鏈表以及鏈表的子元素。找到對(duì)應(yīng)的元素
一、基本參數(shù)
DEFAULT_INITIAL_CAPACITY：默認(rèn)容量
DEFAULT_LOAD_FACTOR：默認(rèn)的負(fù)載因子,表示散列鏈表的使用度，數(shù)越大那么使用度越高。
entry：鏈表對(duì)象
table：鏈表的容器是一個(gè)數(shù)組
threshold：臨界點(diǎn)，當(dāng)達(dá)到這個(gè)臨界點(diǎn)的時(shí)候進(jìn)行擴(kuò)容，它等于負(fù)載因子*容量大小
二、創(chuàng)建一個(gè)HashMap
1.首先會(huì)判斷初始容量的大小是否符合條件，不能太大也不能太小
2.創(chuàng)建一個(gè)Entry的數(shù)組
3.根據(jù)默認(rèn)的臨界點(diǎn)，計(jì)算一個(gè)最合適的容量盡量減少碰撞保證capacity(lenght)是n的次方。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
threshold = initialCapacity;
init();
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
//計(jì)算一個(gè)合理的容量 capacity是n的2次方
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
二、Entry
next：保存當(dāng)前table位置 下一個(gè)entry元素
value：是值
二、put方法
1.如果是空健，創(chuàng)建一個(gè)空元素entry返回
2.如果不是空，那么根據(jù)key的length計(jì)算出index---在數(shù)組中存放的位置。
3.如果當(dāng)前位置有元素，看for循環(huán)中HashMapEntry<K, V> e = tab[index]; e != null，那么判斷它們的hash值，和健的值是否相等。如果相等新的值會(huì)覆蓋舊的值，并且返回給客戶端之前的值
4.如果table已經(jīng)滿了將當(dāng)前的table擴(kuò)大2倍。
5.如果沒有覆蓋新的元素，那么獲取當(dāng)前table位置鏈表的頭結(jié)點(diǎn)，新的元素就放置在頭結(jié)點(diǎn)的位置，并且它的next指向原來元素，如果原來這個(gè)位置上有元素，那么形成鏈表
- int index=hash & (table.length - 1)，這里的table.length==capacity==n^2。查看Java7的的資料 當(dāng)table.length - 1=15和14時(shí)，length是16和15。16是4^2而15不是。所以在table.length-1=14時(shí)發(fā)生的碰撞情況很多。
注意修改了addEntry修改了table[index]的指向。
@Override public V put(K key, V value) {
if (key == null) {
如果是空健，那么創(chuàng)建一個(gè)entry對(duì)象
return putValueForNullKey(value);
}
計(jì)算hash值
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
//遍歷數(shù)組中的元素
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
//加入元素的key的hash值和數(shù)組中現(xiàn)有元素的key的hash值和內(nèi)容相同，那么替換它
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++;
addNewEntry(key, value, hash, index);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
三.get方法獲取數(shù)據(jù)
1.首先如果key是空鍵，判斷是否有對(duì)應(yīng)的entry。如果有返回entry存儲(chǔ)的值。
2.如果不是空值，根據(jù)hash算法以及數(shù)組長度計(jì)算出index
3.取出數(shù)組對(duì)應(yīng)的index位置保存的entry，遍歷這個(gè)entry（因?yàn)樗且粋€(gè)鏈表），一次循環(huán)后，循環(huán)值e=e.next(),再進(jìn)行循環(huán)，當(dāng)e的hash值和key的值相同時(shí)取出對(duì)應(yīng)的值
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
四、HashMap的查找
1.遍歷數(shù)組中所有存儲(chǔ)的entry，然后遍歷該位置的鏈表，確認(rèn)是否有元素
@Override public boolean containsValue(Object value) {
HashMapEntry[] tab = table;
int len = tab.length;
if (value == null) {
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (e.value == null) {
return true;
}
}
}
return entryForNullKey != null && entryForNullKey.value == null;
}
// value is non-null
for (int i = 0; i < len; i++) {
for (HashMapEntry e = tab[i]; e != null; e = e.next) {
if (value.equals(e.value)) {
return true;
}
}
}
return entryForNullKey != null && value.equals(entryForNullKey.value);
}
HashMap的優(yōu)缺點(diǎn)
1.它的查找性能很高，根據(jù)Hash算法計(jì)算出key在整個(gè)table數(shù)組中的位置，遍歷這個(gè)數(shù)組中的鏈表找到指定的元素，不需要去一個(gè)一個(gè)對(duì)比。
2.在插入時(shí)需要查詢該位置是否有相同元素。如果發(fā)生hash碰撞會(huì)形成鏈表，所以它的插入效率沒有數(shù)組高
3.它不是同步的，如果同時(shí)操作同一個(gè)HashMap會(huì)造成數(shù)據(jù)不一致。
