簡介
hashmap是雙鏈表格式的存盤結構<K,V>存盤資料，沒有順序性，1.7基于hash表存盤，允許空值存在，鍵中有且只允許有一個，值中也允許有空值存在，初始容量大小為16加載因子為0.75，
執行緒不安全，在并操作時存在安全問題，
常見操作解讀
初始化new
初始化的時候無參情況下，使用默認初始大小和加載因子進行初始化，
//空參構造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//構造方法
//執行構造方法之前會加載類中的變數
//初始化一個Entry物件陣列
//transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
添加操作
public V put(K key, V value) {
//是否為空Entry<K,V> table
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//key為null，hashMap專門空值設定一個存盤方法
if (key == null)
return putForNullKey(value);
//計算hash
int hash = hash(key);
//計算index，根絕key的hash和table的長度
int i = indexFor(hash, table.length);
//是否有重復的key值，通過獲取現有的table[i]是否為空來判斷
//當不同key的hash值相同時為hash沖突，hash沖突時，需要便利所有的Entry比較是否key的==和equal方法一致，
//hash一致后Entry變為為鏈狀，同一個index下有多個Entry[]資料，并把添加放置到重復index下的Entry中的最后一個
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//重復key值處理
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = https://www.cnblogs.com/JunQiang-Ma/p/e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//添加Entry
addEntry(hash, key, value, i);
return null;
}
addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) {
//當前entry的size大小大于threshold（size*0.75加載因子）并且當前表的index值已經存在
//散串列散列值計算，通常是兩種方法：鏈表法和開放地址法
//鏈表法就是將相同hash值的物件組織成一個鏈表放在hash值對應的槽位；開放地址法是通過一個探測演算法，當某個槽位已經被占據的情況下繼續查找下一個可以使用的槽位，
//1.7hashMap使用的就是鏈表法
if ((size >= threshold) && (null != table[bucketIndex])) {
//當大小超過threshold并且出現hash沖突的時候會擴容在不大于最大值的情況下是是舊表的二倍
resize(2 * table.length);
//是否重新計算hash
hash = (null != key) ? hash(key) : 0;
//給沖突的hash集合新表的長度再次計算hash
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
resize方法
void resize(int newCapacity) {
//舊表
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果已經是最大長度則直接回傳
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//遷移表
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//重新計算 閥值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
threshold方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍歷舊表對遷移新表
for (Entry<K,V> e : table) {
//在對Entry鏈表的復制程序中可能會存在環的問題，多條執行緒并發操作，遍歷Enrt表的時候會導致環的存在，新鏈表插入相比較舊鏈表而言是倒敘，因為多執行緒快慢問題可能導致，
//對有bucket鏈進行便利
while(null != e) {
//記錄舊表的下一個entry值
Entry<K,V> next = e.next;
//是否重新計算hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//計算idex值
int i = indexFor(e.hash, newCapacity);
//新表的指標反轉舊表指向
e.next = newTable[i];
//舊的enry攜帶新的指向賦值給新的槽位
newTable[i] = e;
//舊表指標往下
e = next;
}
}
}
獲取
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
getEntry方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
//hash重復的情況
//比較key的equals和==的方法
for (Entry<K,V> 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;
}
洗掉
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
removeEnryForKey方法
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
//洗掉
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
//hash相同時
if (e.hash == hash &&(k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/262784.html
標籤：Java