面試題：
- hashmap談一談
- hashmap的set和get的時間復(fù)雜度是多少？為什么是O(1), hashmap 在jdk1.8是線程安全的嗎？
為什么是線程安全的？concureenthashmap了解嗎？他是如何實現(xiàn)線程安全的？- HashMap
查詢時間復(fù)雜度，有沖突呢
HashCode 函數(shù)設(shè)計
如何用HashMap 加鎖 保證線程安全，不可以用JUC下類- HashMap 的插入時間復(fù)雜度
- Java中HashMap與HashTable區(qū)別
- Java中HashMap底層數(shù)據(jù)結(jié)構(gòu)
- hashmap底層結(jié)構(gòu)，紅黑樹什么時候退化，如何擴容
- hashmap的默認(rèn)數(shù)組長度是多少，hashmap中的取余操作是怎么做的
- HashMap為什么是非線程安全的
- HashMap有了解嗎？HashMap的時間復(fù)雜度？HashMap中Hash沖突是怎么解決的？鏈表的上一級結(jié)構(gòu)是什么？Java8中的HashMap有什么變化？紅黑樹需要比較大小才能進行插入，是依據(jù)什么進行比較的？其他Hash沖突解決方式？
- hashmap如何解決hash沖突，為什么hashmap中的鏈表需要轉(zhuǎn)成紅黑樹？
- hashmap擴容時每個entry需要再計算一次hash嗎？
- hashmap的數(shù)組長度為什么要保證是2的冪？
- hashmap什么時候會觸發(fā)擴容？
0、1.7的實現(xiàn)由數(shù)組加上鏈表實現(xiàn)
1、Entry結(jié)構(gòu)
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
table = new Entry[capacity];
table
2、public V put(K key, V value)操作
1、首先判斷table是否為空，如果空，就去創(chuàng)建size為capacity的Entry數(shù)；
2、不為空，判斷key是否為null，如果為null，就putForNullKey(value)；
3、如果不為null，就計算key的hash值，再根據(jù)hash值和 table.length計算對應(yīng)在數(shù)組中的下標(biāo)；
4、根據(jù)下標(biāo)去看對應(yīng)的鏈上是否有key相同的節(jié)點，如果有就把該節(jié)點的值覆蓋掉，返回舊的值；
5、如果對應(yīng)下標(biāo)為null，或者找不到相同key的節(jié)點，就使用頭插法，將新的new Entry<>(hash, key, value, e)，放在table[bucketIndex]上。
6、5中還涉及到table擴容的問題。
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
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;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
1、觸發(fā)擴容
如果size 的大小大于等于了capacity * loadFactor ，就會觸發(fā)擴容，容量變?yōu)樵瓉淼膬杀叮?/p>
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
if ((size >= threshold) && (null != table[bucketIndex]))
2、hashmap擴容時每個entry需要再計算一次hash嗎？
不是，首先key為null的entry就不需要重新計算，其次rehash幾乎不會觸發(fā)
3、Hashmap的默認(rèn)數(shù)組長度是多少，hashmap中的取余操作是怎么做的
默認(rèn)16, 取余h & (length-1)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
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);
}
