前言
HashMap和List這兩個(gè)類是我們?cè)贘ava語(yǔ)言編程時(shí)使用的頻率非常高集合類外莲〔皇ǎ“知其然降铸，更要知其所以然”。HashMap認(rèn)識(shí)我已經(jīng)好多年了摇零，對(duì)我在工作中一直也盡心盡力的提供幫助推掸。我從去年開(kāi)始就想去它家拜訪來(lái)著，可是經(jīng)常因?yàn)楦鞣N各樣的原因讓其遺忘在路過(guò)的風(fēng)景中驻仅。（文章大部分源碼基于jdk1.7）谅畅。
HashMap概述：
HashMap是基于哈希表實(shí)現(xiàn)的鍵值對(duì)的集合滑蚯，繼承自AbstractMap并的Map接口的非同步實(shí)現(xiàn)薯定。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵媳瞪。此類不保證映射的順序粘优，特別是它不保證該順序恒久不變仇味。
HashMap的特殊存儲(chǔ)結(jié)構(gòu)使得在獲取指定元素的前需要經(jīng)過(guò)哈希運(yùn)算，得到目標(biāo)元素在哈希表中的位置雹顺，然后再進(jìn)行少量的比較即可得到元素丹墨，這使得HashMap的查找效率很高。
HashMap的特點(diǎn)
- 底層實(shí)現(xiàn)JDK1.8之前是數(shù)組加鏈表嬉愧，之后是數(shù)組加紅黑樹(shù)带到。
- key是用Set進(jìn)行存儲(chǔ)的，所以不允許重復(fù)（可以允許null作為key）英染。
- 元素的存儲(chǔ)是無(wú)序的揽惹，每次重新擴(kuò)容元素位置可能改變。
- 插入四康、獲取的時(shí)間復(fù)雜度基本是O(1)（提前試有適當(dāng)?shù)墓：瘮?shù)搪搏，讓元素均勻分布分布）。
- 兩個(gè)關(guān)鍵因子：出事容量闪金，加載因子疯溺。
HashMap的數(shù)據(jù)結(jié)構(gòu)
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
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;
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**********部分代碼省略**********/
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**********部分代碼省略**********/
}
/**********部分代碼省略**********/
}
HashMap中主要存儲(chǔ)著一個(gè)Entry的數(shù)組table论颅，Entry就是數(shù)組中的元素，Entry實(shí)現(xiàn)了Map.Entry所以其實(shí)Entry就是一個(gè)key-value對(duì)囱嫩，并且它持有一個(gè)指向下一個(gè)元素的引用恃疯，這樣構(gòu)成了鏈表（在java8中Entry改名為Node，因?yàn)樵贘ava8中Entry不僅有鏈表形式還有樹(shù)型結(jié)構(gòu)墨闲，對(duì)應(yīng)的類為T(mén)reeNode）今妄。
HashMap的構(gòu)造
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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 HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
主要有兩個(gè)參數(shù)，【initialCapacity】初始容量鸳碧、【loadFactor】加載因子盾鳞。這兩個(gè)屬性在類定義時(shí)候都賦有默認(rèn)值分別為16和0.75。table數(shù)組默認(rèn)值為EMPTY_TABLE瞻离，在添加元素的時(shí)候判斷table是否為EMPTY_TABLE來(lái)調(diào)用inflateTable腾仅。在構(gòu)造HashMap實(shí)例的時(shí)候默認(rèn)【threshold】閾值等于初始容量。當(dāng)構(gòu)造方法的參數(shù)為Map時(shí)套利，調(diào)用inflateTable(threshold)方法對(duì)table數(shù)組容量進(jìn)行設(shè)置：
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
//更新閾值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
//返回一個(gè)比初始容量大的最小的2的冪數(shù),如果number為2的整數(shù)冪值那么直接返回推励，最小為1，最大為2^31肉迫。
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;
}
//返回一個(gè)不大于i的2的整數(shù)次冪
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);//i的二進(jìn)制右邊2位為1 吹艇。
i |= (i >> 2);//i的二進(jìn)制右邊4位為1。
i |= (i >> 4);//i的二進(jìn)制右邊8位為1昂拂。
i |= (i >> 8);//i的二進(jìn)制右邊16位為1受神。
i |= (i >> 16);//i的二進(jìn)制右邊32位為1。
//這樣5次移位后再進(jìn)行與操作格侯，i的所有非0低位全部變成1鼻听；
return i - (i >>> 1);//i減去所有底位的1，只留一個(gè)高為的1
}
為什么桶的容量要是2的指數(shù)联四，后面會(huì)講到這樣有助于添加元素時(shí)減少哈希沖突撑碴。
HashMap的存取實(shí)現(xiàn)
HashMap的put方法
- 獲取key的hashcode
- 二次hash
- 通過(guò)hash找到對(duì)應(yīng)的index
- 插入鏈表
//HashMap添加元素
public V put(K key, V value) {
//table沒(méi)有初始化size=0，先調(diào)用inflateTable對(duì)table容器進(jìn)行擴(kuò)容
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//在hashMap增加key=null的鍵值對(duì)
if (key == null)
return putForNullKey(value);
//計(jì)算key的哈希值
int hash = hash(key);
//計(jì)算在table數(shù)據(jù)中的bucketIndex
int i = indexFor(hash, table.length);
//遍歷table[i]的鏈表朝墩，如果節(jié)點(diǎn)不為null醉拓，通過(guò)循環(huán)遍歷鏈表的下一個(gè)元素
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//找到對(duì)應(yīng)的key，則將value進(jìn)行替換
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//沒(méi)有找到對(duì)應(yīng)的key的Entry收苏，則需要對(duì)數(shù)據(jù)進(jìn)行modify,modCount加一
modCount++;
//將改key亿卤，value添加入table中
addEntry(hash, key, value, i);
return null;
}
//添加Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
//當(dāng)前桶的長(zhǎng)度大于于閾值，而且當(dāng)前桶的索引位置不為null鹿霸。則需要對(duì)桶進(jìn)行擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) {
//對(duì)桶進(jìn)行擴(kuò)容
resize(2 * table.length);
//重新計(jì)算hash值
hash = (null != key) ? hash(key) : 0;
//重新計(jì)算當(dāng)前需要插入的桶的位置
bucketIndex = indexFor(hash, table.length);
}
//在bucketIndex位置創(chuàng)建Entry
createEntry(hash, key, value, bucketIndex);
}
//創(chuàng)建Entry
void createEntry(int hash, K key, V value, int bucketIndex) {
//找到當(dāng)前桶的當(dāng)前鏈表的頭節(jié)點(diǎn)
Entry<K,V> e = table[bucketIndex];
//新創(chuàng)建一個(gè)Entry將其插入在桶的bucketIndex位置的鏈表的頭部
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
獲取key的hashcode并進(jìn)行二次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();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
為什么這么進(jìn)行二次hash排吴，目的是唯一的就是讓產(chǎn)生的hashcode散列均勻。在網(wǎng)絡(luò)上也找了一些關(guān)于hash值獲取的介紹懦鼠，下邊是我找到感覺(jué)比較靠譜的一篇文章中關(guān)于hash算法的解析：
假設(shè)h^key.hashCode()的值為：0x7FFFFFFF钻哩，table.length為默認(rèn)值16屹堰。
上面算法執(zhí)行
得到i=15
其中h^(h>>>7)^(h>>>4) 結(jié)果中的位運(yùn)行標(biāo)識(shí)是把h>>>7 換成 h>>>8來(lái)看。
即最后h^(h>>>8)^(h>>>4) 運(yùn)算后hashCode值每位數(shù)值如下：
8=8
7=7^8
6=6^7^8
5=5^8^7^6
4=4^7^6^5^8
3=3^8^6^5^8^4^7 ------------> 3^4^5^6^7
2=2^7^5^4^7^3^8^6 ---------> 2^3^4^5^6^8
1=1^6^4^3^8^6^2^7^5 ------> 1^2^3^4^5^7^8
算法中是采用(h>>>7)而不是(h>>>8)的算法街氢，應(yīng)該是考慮1扯键、2、3三位出現(xiàn)重復(fù)位^運(yùn)算的情況珊肃。使得最低位上原h(huán)ashCode的8位都參與了^運(yùn)算荣刑，所以在table.length為默認(rèn)值16的情況下面，hashCode任意位的變化基本都能反應(yīng)到最終hash table 定位算法中近范，這種情況下只有原h(huán)ashCode第3位高1位變化不會(huì)反應(yīng)到結(jié)果中，即：0x7FFFF7FF的i=15延蟹。
從整個(gè)二次hash的解析過(guò)程來(lái)看评矩，通過(guò)多次位移和多次與操作獲取的hashc。每當(dāng)key的hashcode有任何變化的時(shí)候都能影響到二次hash后的底位的不同阱飘，這樣在下邊根據(jù)hash獲取在桶上的索引的時(shí)候最大減少哈希沖突斥杜。
獲取hash在桶上的索引：
當(dāng)我們想找一個(gè)hash函數(shù)想讓均勻分布在桶中時(shí)，我們首先想到的就是把hashcode對(duì)數(shù)組長(zhǎng)度取模運(yùn)算沥匈，這樣一來(lái)蔗喂，元素的分布相對(duì)來(lái)說(shuō)是比較均勻的。但是高帖，“溺侄”運(yùn)算的消耗還是比較大。而JDK中的實(shí)現(xiàn)hash根數(shù)組的長(zhǎng)度-1做一次“&”操作散址。
//找到當(dāng)前的hash在桶的分布節(jié)點(diǎn)位置
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);
}
這里需要講一下為什么index=h&(length-1)呢乖阵？因?yàn)镠ashMap中的數(shù)組長(zhǎng)度為2的指數(shù)。（lenth-1）的值恰好是數(shù)組能容納的最大容量预麸，且在二進(jìn)制下每位都是1瞪浸。所以在經(jīng)過(guò)二次hash之后所獲取的code，就能通過(guò)一次與操作（取hash值的底位）讓其分布在table桶中吏祸。
HashMap的get方法
在理解了put之后对蒲，get就很簡(jiǎn)單了。大致思路如下：
bucket里的第一個(gè)節(jié)點(diǎn)贡翘，直接命中蹈矮；
- 如果有沖突，則通過(guò)key.equals(k)去查找對(duì)應(yīng)的entry
- 若為樹(shù)鸣驱，則在樹(shù)中通過(guò)key.equals(k)查找含滴，O(logn)；
- 若為鏈表丐巫，則在鏈表中通過(guò)key.equals(k)查找谈况，O(n)勺美。
//HashMap的get方法
public V get(Object key) {
//獲取key為null的value
if (key == null)
return getForNullKey();
//獲取key對(duì)應(yīng)的Entry實(shí)例
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//獲取Entry
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//計(jì)算key的hash值
int hash = (key == null) ? 0 : hash(key);
//根據(jù)hash調(diào)用indexFor方法找到當(dāng)前key對(duì)應(yīng)的桶的index，遍歷該節(jié)點(diǎn)對(duì)應(yīng)的鏈表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//判斷當(dāng)前Entry的hash碑韵、key的hash和Entry的key赡茸、key是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
HashMap的擴(kuò)容
當(dāng)HashMap中的元素越來(lái)越多的時(shí)候，因?yàn)閿?shù)組的長(zhǎng)度是固定的所以hash沖突的幾率也就越來(lái)越高祝闻，桶的節(jié)點(diǎn)處的鏈表就越來(lái)越長(zhǎng)占卧，這個(gè)時(shí)候查找元素的時(shí)間復(fù)雜度相應(yīng)的增加。為了提高查詢的效率联喘，就要對(duì)HashMap的數(shù)組進(jìn)行擴(kuò)容（這是一個(gè)常用的操作华蜒，數(shù)組擴(kuò)容這個(gè)操作也會(huì)出現(xiàn)在ArrayList中。）豁遭，而在HashMap數(shù)組擴(kuò)容之后叭喜，最消耗性能的地方就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計(jì)算其在新數(shù)組中的位置，并放進(jìn)去蓖谢，這就是resize捂蕴。
當(dāng)HashMap中的元素個(gè)數(shù)超過(guò)閾值時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容闪幽，【loadFactor】加載因子的默認(rèn)值為0.75啥辨，【threshold】閾值等于桶長(zhǎng)乘以loadFactor這是一個(gè)折中的取值。也就是說(shuō)盯腌，默認(rèn)情況下溉知，數(shù)組大小為16，那么當(dāng)HashMap中元素個(gè)數(shù)超過(guò)160.75=12的時(shí)候腕够，就把數(shù)組的大小擴(kuò)展為 216=32着倾，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置燕少，
//HashMap擴(kuò)容
void resize(int newCapacity) {
//引用備份
Entry[] oldTable = table;
//原來(lái)桶的長(zhǎng)度
int oldCapacity = oldTable.length;
//判斷是否已經(jīng)擴(kuò)容到極限
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根據(jù)容器大小創(chuàng)新的建桶
Entry[] newTable = new Entry[newCapacity];
//
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//重置桶的引用
table = newTable;
//重新計(jì)算閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//用于初始化hashSeed參數(shù).
//其中hashSeed用于計(jì)算key的hash值卡者，它與key的hashCode進(jìn)行按位異或運(yùn)算。
//這個(gè)hashSeed是一個(gè)與實(shí)例相關(guān)的隨機(jī)值客们，主要用于解決hash沖突崇决。
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;
}
//桶中數(shù)據(jù)的遷移
void transfer(Entry[] newTable, boolean rehash) {
//新的痛長(zhǎng)
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
//遍歷桶的沒(méi)一個(gè)節(jié)點(diǎn)的鏈表
while(null != e) {
Entry<K,V> next = e.next;
//重新計(jì)算哈希值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//找到當(dāng)前Entry在新桶中的位置
int i = indexFor(e.hash, newCapacity);
//將Entry添加在當(dāng)桶中的bucketIndex處的鏈表的頭部
e.next = newTable[i];
//將產(chǎn)生的新鏈表賦值為桶的bucketIndex處
newTable[i] = e;
//遍歷當(dāng)前鏈表的下一個(gè)節(jié)點(diǎn)
e = next;
}
}
}
- 假設(shè)hash算法就是最簡(jiǎn)單的 key mod table.length（也就是數(shù)組的長(zhǎng)度）。
- 最上面的是old hash 表底挫，其中的Hash表的 size = 2, 所以 key = 3, 7, 5恒傻，在mod 2以后碰撞發(fā)生在 table[1]
- 接下來(lái)的三個(gè)步驟是 Hash表 resize 到4，并將所有的 <key,value> 重新resize到新Hash表的過(guò)程
在HashMap進(jìn)行擴(kuò)容的時(shí)候有一個(gè)點(diǎn)大家發(fā)現(xiàn)沒(méi)建邓，所有Entry的hash值是不需要重新計(jì)算的盈厘。因?yàn)閔ash值與（length - 1）取的總是hash值的二進(jìn)制右邊底位，擴(kuò)容一次向左多取一位二進(jìn)制官边。
有關(guān)HashMap的思考
- 什么時(shí)候會(huì)使用HashMap沸手？他有什么特點(diǎn)外遇？
是基于Map接口的實(shí)現(xiàn)，存儲(chǔ)鍵值對(duì)時(shí)契吉，它可以接收null的鍵值跳仿，是非同步的，HashMap存儲(chǔ)著Entry(hash, key, value, next)對(duì)象捐晶。
- 你知道HashMap的工作原理嗎菲语？
通過(guò)hash的方法，通過(guò)put和get存儲(chǔ)和獲取對(duì)象惑灵。存儲(chǔ)對(duì)象時(shí)山上，我們將K/V傳給put方法時(shí)，它調(diào)用hashCode計(jì)算hash從而得到bucket位置英支，進(jìn)一步存儲(chǔ)佩憾，HashMap會(huì)根據(jù)當(dāng)前bucket的占用情況自動(dòng)調(diào)整容量(超過(guò)Load Facotr則resize為原來(lái)的2倍)。獲取對(duì)象時(shí)潭辈，我們將K傳給get鸯屿，它調(diào)用hashCode計(jì)算hash從而得到bucket位置澈吨，并進(jìn)一步調(diào)用equals()方法確定鍵值對(duì)把敢。如果發(fā)生碰撞的時(shí)候，Hashmap通過(guò)鏈表將產(chǎn)生碰撞沖突的元素組織起來(lái)谅辣，在Java 8中修赞，如果一個(gè)bucket中碰撞沖突的元素超過(guò)某個(gè)限制(默認(rèn)是8)，則使用紅黑樹(shù)來(lái)替換鏈表桑阶，從而提高速度柏副。
- 你知道get和put的原理嗎？equals()和hashCode()的都有什么作用蚣录？
通過(guò)對(duì)key的hashCode()進(jìn)行hashing割择，并計(jì)算下標(biāo)( n-1 & hash)，從而獲得buckets的位置萎河。如果產(chǎn)生碰撞荔泳，則利用key.equals()方法去鏈表或樹(shù)中去查找對(duì)應(yīng)的節(jié)點(diǎn)
- 你知道hash的實(shí)現(xiàn)嗎？為什么要這樣實(shí)現(xiàn)虐杯？
在通過(guò)hashCode()的高位與底位進(jìn)行異或玛歌，主要是從速度、功效擎椰、質(zhì)量來(lái)考慮的支子，這么做可以在bucket的n比較小的時(shí)候，也能保證考慮到高低bit都參與到hash的計(jì)算中达舒，同時(shí)不會(huì)有太大的開(kāi)銷值朋。
- 如果HashMap的大小超過(guò)了負(fù)載因子(load factor)定義的容量叹侄，怎么辦？
如果超過(guò)了負(fù)載因子(默認(rèn)0.75)吞歼，則會(huì)重新resize一個(gè)原來(lái)長(zhǎng)度兩倍的HashMap圈膏，并且重新調(diào)用hash方法。
JDK1.8對(duì)HashMap的改進(jìn)
代碼實(shí)現(xiàn)的不同之處
//鏈表切換為紅黑樹(shù)的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹(shù)切花為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
//紅黑樹(shù)上的節(jié)點(diǎn)個(gè)數(shù)滿足時(shí)對(duì)整個(gè)桶進(jìn)行擴(kuò)容
static final int MIN_TREEIFY_CAPACITY = 64;
//紅黑樹(shù)
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
/*************部分代碼省略*****************/
}
//獲取key的hashCode,并進(jìn)行二次hash篙骡。二次hash只是將hashcode的高16位于第16位進(jìn)行異或
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//resize時(shí)hash沖突使用的是紅黑樹(shù)
final Node<K,V>[] resize() {
/*************部分代碼省略*****************/
}
性能的提升
哈希碰撞會(huì)對(duì)hashMap的性能帶來(lái)災(zāi)難性的影響稽坤。如果多個(gè)hashCode()的值落到同一個(gè)桶內(nèi)的時(shí)候，這些值是存儲(chǔ)到一個(gè)鏈表中的糯俗。最壞的情況下尿褪，所有的key都映射到同一個(gè)桶中，這樣hashmap就退化成了一個(gè)鏈表——查找時(shí)間從O(1)到O(n)得湘，而使用紅黑樹(shù)代替鏈表查找時(shí)間會(huì)變?yōu)镺(logn)杖玲。
參考文章：
主題：HashMap hash方法分析
文章到這里就全部講述完啦，若有其他需要交流的可以留言哦~淘正！~摆马！
