java 1.7 hashmap源码_jdk1.7hashMap源码分析
jdk1.7的map接口結構：
jdk1.8的map接口結構：
hashMap繼承關系：
hashTable繼承結構：
concurrentHashMap繼承關系：
哈哈，我比較懶，不想畫圖，自行腦補三者關系。
幾個關鍵字說明：
//map 初始化容量，即數組大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//承載量=容量*加載因子
int threshold;
//加載因子
final float loadFactor;
//map結構變更過的次數
transient int modCount;
//聲明的表，初始化為空
transient Entry[] table = (Entry[]) EMPTY_TABLE;
// key-map鍵值對的個數，不能大于承載量
transient int size;
Map param = new HashMap<>();
new一個對象，我們看看hashmap做了什么:
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
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;//初始化承載量，16
init();//供子類擴展的方法
}
可以看出，只初始化了加載因子和承載量。
下面分析，put() 和 remove方法。
put():
public V put(K key, V value) {
if (table == EMPTY_TABLE) {//初始化數組，容量為16
inflateTable(threshold);//初始化table數組，源碼在下面
}
if (key == null)
return putForNullKey(value);//如果key為空，則
int hash = hash(key);//根據key求出hash值
int i = indexFor(hash, table.length);//求出在數組中的位置
for (HashMap.Entry e = table[i]; e != null; e = e.next) {//遍歷鏈表找出對應的key，覆蓋原有的value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果沒找到，則新增一個Entry,結構改變，modCount加一
modCount++;
addEntry(hash, key, value, i);//源碼解釋在下面
return null;
}
//取hash值得算法
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
private V putForNullKey(V value) {
for (Entry e = table[0]; e != null; e = e.next) {//遍歷鏈表，如果找到key值為null，將value賦值給對應的key
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//如果沒找到，鏈表會增加一個節點，結構變化了，modCount加一
modCount++;
addEntry(0, null, value, 0);//添加一個key為null，值為value的Entry,源碼向下看
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {//判斷是不是需要擴容，擴容以后需要重新算hash值和數組下標位置
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);//源碼向下看
}
createEntry(hash, key, value, bucketIndex);//源碼向下看
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);//查找entry在數組中存放的位置
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];//bucketIndex位置值賦值給e
table[bucketIndex] = new Entry<>(hash, key, value, e);//new 一個Entry放在bucketIndex
size++;
}
remove():
public V remove(Object key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final HashMap.Entry removeEntryForKey(Object key) {
if (size == 0) {//size表示hashmap中 HashMap.Entry對象的個數,如果為零，表示空map
return null;
}
int hash = (key == null) ? 0 : hash(key);//根據key求出hash值
int i = indexFor(hash, table.length);//求出元素在哪個數組位置
HashMap.Entry prev = table[i];//取出對應的鏈表
HashMap.Entry e = prev;//遍歷用，存儲遍歷元素的前一個元素或者當前entry
while (e != null) {
HashMap.Entry next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {//遍歷鏈表，找到對應的key
modCount++;//找到對應的元素，map結構改變一次，modCount加一
size--;//HashMap.Entry對象的個數減一
if (prev == e)//如果當前entry就是要找的，直接將下一個entry放在數組對應位置，(要刪除元素在鏈表頭部)
table[i] = next;
else
prev.next = next;//從中間刪除節點，直接讓被刪元素上一個entry指向它的下一個entry
e.recordRemoval(this);//這個不知道干嘛的
return e;
}
//如果當前節點不是要找的元素，繼續遍歷鏈表
prev = e;
e = next;
}
return e;
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);//初始化容量，默認為16
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//初始化承載量
table = new Entry[capacity];//初始化table數組
initHashSeedAsNeeded(capacity);//這個暫時不做解釋
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;//初始化table容量，保證容量是2的冪次
}
//擴容 當元素數量>=承載量時，進行擴容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {//容量為2的冪次，最大為2的30次方，所以一直擴容肯定有等于最大冪次的時候
threshold = Integer.MAX_VALUE;//這時就把Integer的最大值給承載量
return;
}
Entry[] newTable = new Entry[newCapacity];//創建新的table
transfer(newTable, initHashSeedAsNeeded(newCapacity));//判斷新的table中的元素是否需要重新求hash值，源碼在下面
table = newTable;//數組擴容賦值給table
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//算出新的承載量
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {// 遍歷舊表，如果需要重新求hash值就進行rehash操作
while(null != e) {
Entry next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
//這段沒看懂，大體意思是初始化好數據，如果需要則作為是否進行rehash的條件
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
所以，1.7和1.8的hashmap到底有哪些不同呢：
1.hash的取值算法不同
2.求數組下標的算法不同
3.1.8的實體是Node繼承了entry，鏈表長度大于8的時候轉換為紅黑樹。
總結
以上是生活随笔為你收集整理的java 1.7 hashmap源码_jdk1.7hashMap源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python 线性规划问题_一学高数，线
- 下一篇： linux的虚拟机部署项目,在虚拟机上部