摘要：源碼分析簡介的和操作的時間復雜度是常量。可以存鍵值為，是線程不安全的。數組鏈表散列的數據結構實現桶，鏈表的實現桶的實現鏈表的實現值節點的鍵節點的值下一個節點鏈表構造方法方法是線程不安全的判斷兩個元素是否相等重要屬性默認的桶初始容量。
hashmap源碼分析
簡介
hashmap的get和put操作的時間復雜度是常量。通過調用哈希函數將元素正確的分布到桶中。初始容量(capacity)的值不能設置太高，加載因子(loadfactor)不能設置的太低，否則會影響迭代的性能。
一個hashmap的實例有兩個參數將影響它的性能。初始容量、加載因子。初始容量是hashmap在創建時候桶的大小。加載因子用來確定何時進行擴容（size > 容量*加載因子）。擴容的時候也會進行對內部的數據結構進行重新構建，使桶的大小增加兩倍。
默認的加載因子（0.75）在時間和空間復雜度上提供了很好的權衡。大一點的話會減少空間但是會增加get和put的時間。
hashmap可以存鍵值為null，是線程不安全的。如果想線程安全可以使用Collections.synchronizedMap()包裝.
或者使用ConcurrentMap，這個map是線程安全的。
hashmap數據結構
hashmap是一個散列表，存儲的內容是key-value。就像我們用的字典一樣，用過字母（key）查找單詞(value)。hashmap的時間復雜度是O(longN)。
在java8之前hashmap采用的是桶+鏈表的數據結構。但是如果數據很大，鏈表的查找時間復雜度是O(n)，顯然者違背了hashmap的初衷，所以在鏈表的元素大于8的時候，java8會把鏈表旋轉為紅黑樹。
[數組 鏈表 散列（hash）
](https://blog.csdn.net/u013565...
hashmap的數據結構實現
桶，鏈表的實現
桶的實現:
transient Node[] table;
鏈表的實現:
static class Node implements Map.Entry {
final int hash;//hash值
final K key;//節點的鍵
V value;//節點的值
Node next;//下一個節點（鏈表）
Node(int hash, K key, V value, Node next) {//構造方法
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
//方法是線程不安全的
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {//判斷兩個元素是否相等
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
重要屬性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認的桶初始容量（2^4=16）。
static final int MAXIMUM_CAPACITY = 1 << 30;//最大的桶的容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認的加載因子
static final int TREEIFY_THRESHOLD = 8;//當鏈表大于這個閾值會被旋轉為紅黑樹
static final int UNTREEIFY_THRESHOLD = 6;//當做resize操作的時候，如果桶中某個節點的數量小于這個閾值，則把樹旋轉為鏈表
static final int MIN_TREEIFY_CAPACITY = 64;//當桶中的數量大于64是，才會判斷是否轉換成樹
transient Node[] table;//桶
transient int size;//hashmap的存儲的元素大小
transient int modCount;//hashmap結構被修改的次數
int threshold;//擴容閾值
final float loadFactor;//加載因子
構造方法
構造方法會創建一個空的桶，計算擴容閾值和加載因子
HashMap(int,float)
public HashMap(int initialCapacity, float loadFactor) {//桶初始化容量，加載因子
if (initialCapacity < 0)//桶初始容量不能小于0
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//如果桶初始化容量大于hashmap最大的容量，則初始化容量等于最大的容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);//計算擴容閾值
}
HashMap(int)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//加載因子為默認的0.75
}
HashMap()
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; //桶初始容量為0，加載因為0.75
}
HashMap(Map)
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//加載因子為默認的0.75
putMapEntries(m, false);//map放入桶中
}
final void putMapEntries(Map m, boolean evict) {
int s = m.size();//插入元素大小
if (s > 0) {//如果大于0 ，則繼續進行插入操作
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)//如果插入元素數量大于擴容閾值，則桶的大小擴容兩倍
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);//插入元素
}
}
}
主要的幾個方法分析
get(Obejct)
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//計算hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//根據key獲取value
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;//tab:桶 first：桶中節點的第一個元素 n:桶的長度 k:第一個節點的key
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//如果桶不為空，并且key所在的節點的第一個元素不為空
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))//如果key是節點的第一元素則返回節點的第一個元素
return first;
if ((e = first.next) != null) {//遍歷鏈表/平衡樹 查找元素
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);//在樹中查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
put(K,V)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//如果桶為空，擴容兩倍
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//如果key所在的桶第一個元素為null則直接插入桶中的第一個節點
else {//否則插入鏈表/樹
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//如果插入的元素等于桶中的第一個一個元素，直接返回桶中的第一個元素
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);//如果是樹節點，插入樹中
else {//插入鏈表中
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)//如果hashmap中的元素等于擴容閾值，則重新構造數據結構
resize();
afterNodeInsertion(evict);
return null;
}
hash（）
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
h是原始的hash返回的值是int類型，int取值范圍:-2147483648到2147483648,前后加起來大概四十億的映射空間。只要hash函數映射的比較松散，一般是很難出現碰撞的。
但是考慮到實際的內存的大小，很難放下這么大的數組。
所以為了空間上的考慮上述中的擾動函數，對原始計算出來的hash值（int 四個字節32位），右移16位，自己的高半區和低半區做異或，就是為了混合原始hash值的高位和地位，以此來加大低位的隨機性。而且混合后的地位參雜了高位的部分特征，這樣高位的信息也被變相的保留下來了。
線程安全性
hashmap線程不安全的，如果要使用安全的hashmap建議使用ConcurrentHashMap。
參考：
hash（）原理: https://www.zhihu.com/questio...
關注我的公眾號第一時間閱讀有趣的技術故事
掃碼關注：
也可以在微信搜索公眾號即可關注我：codexiulian
渴望與你一起成長進步！
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76918.html
