深度解析HashMap集合底層原理
目錄
- 前置知識
- HashMap集合特點及源碼分析（JDK1.8）
- HashMap面試題
- HashMap什麼時候會轉換為紅黑樹
- HashMap為什麼要引進紅黑樹，為了解決什麼問題？
- HashMap的長度為什麼必須是2的次冪？
- 如何避免HashMap內存溢出問題
- HashMap根據key查詢的時間複雜度
- HashMapKey為null存放在什麼位置
- HashMap底層是採用單鏈表還是雙鏈表
- HashMap底層是有序存放的嗎
- LinkedHashMap 和 TreeMap底層如何實現有序的
- 為什麼HashMap不使用取模運算
- 求下標i=(n-1)&hash,為什麼（n-1）變成了奇數
- HashMap如何降低Hash衝突
- 加載因子為什麼是0.75而不是1
- Hashap存放1W條數據怎麼樣效率最高
- Hashmap1.7和Hashmap1.8的區別
前置知識
==和equals的區別
對於基本類型變量來說，只能使用 == ，因為基本類型的變量沒有方法。使用==比較是值比較
對於引用類型的變量來說，==比較的兩個引用對象的地址是否相等。所有類都是繼承objcet類，而object類是equals方法比較的也是對象的地址是否相等，如果類沒有重寫equals方法，使用 == 和equals方法效果是一樣的
為什麼要重寫equals和HashCode
HashCode方法：底層採用C語言編寫，根據對象地址轉換為整數類型
如果兩個對象的HashCode相等，對象的內容至不一定相等；hash碰撞的問題
如果使用equals方法比較兩個對象內容值相等的情況下，那麼hashcode的值也相等
因為equals默認情況下Object類採用==比較對象，那麼比較的是內存地址是否相等，當數據類型只要不是基本類型，那麼比較永遠不會相等。
set集合存儲的就是不重複的對象，底層就是hashmap，依據equals和hashcode進行判斷
時間複雜度
時間複雜度為O(n) 從頭查詢到尾部，查詢多次
時間複雜度為O(1) 查詢一次 比如根據數組下標查詢
時間複雜度為O(logn) 平方查詢 比如紅黑樹，
效率：O(1)>O(logn)>O(n)
(不帶符號右移) >>>
無符號右移就是右移之後，無論該數為正還是為負，右移之後左邊都是補上0
無符號右移運算符和右移運算符的主要區別在於負數的計算，因為無符號右移是高位補0，移多少位補多少個0
15>>>2=0000 1111 右移兩位=0000 0011=3
^異或運算
相同為0，不同為1
2^3= 0010^0011=0001=1
&（與運算）
00得0 11得1 01得0
2&3=0010&0011=0010=2
位移操作：1<<2=4，1左移兩位為什麼等於4
這裡的1是十進制，而計算機交流是用二進制，所以先要將1用二進制表示出來。
每一個符號（英文、數字或符號等）都會佔用1Bytes的記錄，每一個中文佔2Byte
而一個1Bytes佔8個bit，也就是8個二進制位
8位二進制數：28種不同狀態 0000 0000 ~1111 1111=0~255=28=256
1的二進制表示0000 0001，然後進行位移操作。
位移操作向左邊位移，後面空出來的補上0，越往左邊越大，把0000 0001向左位移2位，變成了0000 0100，二進制0000 0100轉化十進制所以為4，也可以說每左移一位是乘以2
8>>2?
0000 1000右移2位0000 0010，轉化為10進制等於2
10>>2?
0000 1010右移2位0000 0010，轉化為10進制等於2
1<<30?
0000 0001左移30位01000000 00000000 00000000 00000000，轉化為10進制等於1073741824，也就是230
HashMap集合特點及源碼分析（JDK1.8）
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
HashMap繼承了AbstractMap類，實現了Cloneable克隆接口、Serializable序列化接口、Map接口
特點：數組+鏈表+紅黑樹構成
HashMap重要的五大點
1.集合初始化
HashMap成員變量
//默認初始化hashmap容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //2的4次冪 16
//hashmap最大容量1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;//2的30次冪
//擴容因子 16*0.75=12 達到12就會進行擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表中存儲元素的數量 > 8 時，會自動轉換為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
//刪除元素時，如果一個紅黑樹中中存儲元素數量 < 6 後，會自動轉換為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//數組容量>64&鏈表長度>8 轉為紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
//闕值，用於判斷是否擴容，threshold=容量*擴容因子=16*0.75=12
int threshold;
//擴容因子實際大小
final float loadFactor;
//HashMap中元素的數量 transient表示不能被序列化
transient int size;
//集合修改次數 防止多線程篡改數據
transient int modCount;
//存儲元素的數組 單向鏈表
transient Node<K,V>[] table;
HashMap內部數據結構
鏈表
//單向鏈表 實現了Entry接口 由上面的數組構成了數組加鏈表的結構
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//構造一個節點
Node(int hash, K key, V value, Node<K,V> 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;
}
//比較兩個Node是否相等
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 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; //
boolean red;//是否紅色
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//返回當前節點
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
HashMap構造方法
指定初始容量
構造一個具有默認初始容量 (16) 和默認負載因子 (0.75)的空HashMap
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; //擴容因子0.75
}
指定填充比
構造一個具有指定初始容量和默認擴容因子 (0.75)的空HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//初始容量 擴容因子默認0.75
}
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;//負載因子
this.threshold = tableSizeFor(initialCapacity);
}
//獲得的是大於cap的最小的2的冪，例如10，10的最小的2的冪=16
static final int tableSizeFor(int cap) {
int n = cap - 1;//n=9 0000 1001
n |= n >>> 1;//|= 代表異或運算 先向右位移1位=0000 0100，0000 1001和0000 0100異或運算得到0000 1101
n |= n >>> 2;//....以此類推
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//n<0返回1，否則n大於MAXIMUM_CAPACITY的話返回最大值，小於最大值返回n + 1，全1的情況+1一定變成1後面跟一堆0的情況，這樣就確定了最終的值，當HashMap的size到達threshold這個閾值時會擴容
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
用來初始化的Map
使用與指定Map相同的映射構造一個新的HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//默認負載因子0.75
putMapEntries(m, false);
}
//將集合元素put到HashMap中
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//獲取元素大小
int s = m.size();
if (s > 0) {
//如果存儲元素的數組為空 說明這是剛構造的HashMap 那麼就要為它指定最大容量
if (table == null) {
//根據閾值和Map大小 推算出最大容量，向上取整為了取整數
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(); //先擴容
// 循環put
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//可能會觸發resize
putVal(hash(key), key, value, false, evict);
}
}
}
2.數據尋址Get
根據key獲取元素
public V get(Object key) {
Node<K,V> e;
//key的hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
詳細方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n; K k;
//如果table不等於null 數組不等於null first=賦值計算當前節點的hash值所在的數組下標位置
if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
//如果比較當前節點的和第一個節點
if (first.hash == hash &&((k = first.key) == key || (key != null && key.equals(k))))
//返回第一個結點
return first;
//如果第一個節點的下一個節點不為null
if ((e = first.next) != null) {
//判斷是否為紅黑樹
if (first instanceof TreeNode)
//處理getTreeNode()方法搜索key
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//是鏈表
do {
//遍歷比較直到找到節點或者節點為null退出循環
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
3.數據存儲Put
將元素添加進HashMap
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<K,V>[] tab;
Node<K,V> p;
//n表示table數組的長度 i表示key存放在哪個數組下標
int n, i;
//將全局table=tab判斷是否為空 或者 tab長度為0情況下 對table進行擴容
if ((tab = table) == null || (n = tab.length) == 0)
//擴容 n=16
n = (tab = resize()).length;
//i = (n - 1) & hash 計算key對應的index值 tab[i]key在數組中是否存在
if ((p = tab[i = (n - 1) & hash]) == null)
//如果key的index值沒有發生衝突
tab[i] = newNode(hash, key, value, null);
//key的index發生衝突了
else {
Node<K,V> e; K k;
//如果hash和equals比較都相同 直接覆蓋
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果當前是紅黑樹
else if (p instanceof TreeNode)
//追加到紅黑樹後面
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//當前是鏈表
else {
//循環遍歷鏈表
for (int binCount = 0; ; ++binCount) {
//如果鏈表為空 直接追加在next後面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果鏈表長度binCount大於8 數組容量大於64
if (binCount >= TREEIFY_THRESHOLD - 1)
//把鏈錶轉換為紅黑樹
treeifyBin(tab, hash);
break;
}
//查詢鏈表中是否存在該key，如果存在直接修改value值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//真正給e賦值 將新的value覆蓋為oldvalue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//只有新增才會使modCount++ 修改不會 fastclass機制防止在做遍歷的時候有集合修改類
++modCount;
//如果size>12 就會提前去擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
4.節點刪除
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}
詳細方法
//hash:key的hash值 key:要刪除的鍵值對的key value:要刪除的鍵值對的value
//matchValue 如果為true，則當key對應的鍵值對的值equals(value)為true時才刪除；否則不關心value的值
//movable 刪除後是否移動節點，如果為false，則不移動
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//節點數組tab不為空、數組長度n大於0、根據hash定位到的節點對象p
if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//如果當前節點的鍵和key相等，那麼當前節點就是要刪除的節點，賦值給node
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//獲取當前節點的下一個節點
else if ((e = p.next) != null) {
//如果是一個紅黑樹，那麼調用getTreeNode方法從樹結構中查找滿足條件的節點
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//如果是鏈表
else {
//從頭到尾逐個節點比對
do {
//e節點的鍵是否和key相等，e節點就是要刪除的節點，賦值給node變量
if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;//p指向e，讓p存儲的永遠下一次循環里e的父節點
} while ((e = e.next) != null);
}
}
//node不為空 找到了刪除的節點 如果不需要對比value值或者需要對比value值但是value值也相等
if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {
//如果是紅黑樹上的節點
if (node instanceof TreeNode)
//刪除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果是鏈表 該node節點就是首節點
else if (node == p)
//刪除 把當前節點的下一個賦值給當前表索引
tab[index] = node.next;
//不是首節點，p是node的父節點
else
// 刪除 父節點的下一個節點就是node的下一個節點
p.next = node.next;
++modCount;//HashMap的修改次數遞增
--size;//HashMap的元素個數
afterNodeRemoval(node);//保留的重寫方法 無效果
return node;//返回刪除結果
}
}
return null;
}
5.擴容原理
JDK1.7 HashMap中擴容機制resize()
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//如果舊容量已經達到了最大，將閾值設置為最大值，與1.8相同
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);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍歷原來數組中所有的鏈表
for (Entry<K,V> e : table) {
//判斷每個下標對應的鏈表存放是否為空
while(null != e) {
//這裡兩個多線程環境下都拿到 e.next可能會有死循環問題
Entry<K,V> next = e.next;
//是否需要重新計算hash值
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;
}
}
}
多線程環境下擴容造成死循環的分析過程
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> 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;
}
}
因為是採用頭插法，會導致整個鏈表順序顛倒，多線程環境下遍歷table這就容易導致死循環，因為操縱的同一個e對象
在多線程同時擴容的情況下，線程一搶先獲得CPU資源，而線程二被掛起，此時它們拿到的數據都是e=a；next=c；線程一率先執行把key計算好了並放入newTable了
這時候線程二又被喚醒，因為線程之間不是共享的，所以此時newTable也為空，需要重新給裏面賦值，但是e變量是可以被共享的。
1、線程二第一次循環還是之前拿到的數據e=a；next=c，此時newTable還為空
// e=a e.next=c
Entry<K,V> next = e.next;
//1
int i = indexFor(e.hash, newCapacity);
//e.next=null
e.next = newTable[i];
//數組1位置第一個元素賦值為 a
newTable[i] = e;
//e=c
e = next;
2、線程二第二次循環
第二次循環獲取e的數據，因為e的之前被線程一修改過變為d->c->
// e=c e.next=a
Entry<K,V> next = e.next;
//1
int i = indexFor(e.hash, newCapacity);
//e.next=null
e.next = newTable[i];
//數組1位置賦值為 c
newTable[i] = e;
//e=a
e = next;
因為e的之前被線程一修改過變為d->c->a，所以c.next等於線程一裏面的值，c.next=a
3、線程二第三次循環
//e=a； e.next=a.next=null
Entry<K,V> next = e.next;
//1
int i = indexFor(e.hash, newCapacity);
//此時newTable[i]=a->c e.next=a.next a.next=c->a 出現死循環
e.next = newTable[i];
//數組1位置賦值為 a
newTable[i] = e;
//e=null
e = next;
此時進入環形引用，無限循環中導致CPU使用率飆升
解決辦法
單線程下沒有不會有問題，多線程下採用ConCurrentHashMap
JDK1.8 HashMap中擴容機制resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//如果原來的table=null, 則為HashMap的初始化, 生成空table返回即可
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//hashmap下一次擴容的閾值
int oldThr = threshold;
//記錄新的容量和新的下一次擴容大小
int newCap, newThr = 0;
//大於0說明之前HashMap的數組不是空的
if (oldCap > 0) {
// 再對數組進行檢測 如果大於最大容量2的30次冪 直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否者進行擴容為之前的二倍基於右移 newCap是oldCap長度的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//下一次提前擴容的數量
newThr = oldThr << 1;
}
//閾值大於0 說明集合已存在 賦值給newCap
else if (oldThr > 0)
newCap = oldThr;
//如果等於0 說明剛初始化 newCap=0.75 newThr=新擴容的閾值=0.75*默認容量大小
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果下一次提前擴容的數量==0
if (newThr == 0) {
//新閾值=新容量*負載因子
float ft = (float)newCap * loadFactor;
//新數組小於最大容量 並且閾值小於最大容量
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//下一次擴容的閾值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//HashMap裏面新的擴容容量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果原表不為空，把原表中數據移動到新表中
if (oldTab != null) {
//遍歷原來的列表
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//判斷每個數組裏面是否有鏈表 有的話用一個鏈表e存起來
if ((e = oldTab[j]) != null) {
//然後將原來的鏈表賦值為null 能避免死循環
oldTab[j] = null;
//下一個節點為空 說明只包含一個元素
if (e.next == null)
//計算e在新table中的位置,放入其中
newTab[e.hash & (newCap - 1)] = e;
//判斷當前node是否是紅黑樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//鏈表情況下
else {
//hashmap擴容會把原來的鏈表拆分成 兩個鏈表
//低位鏈表的頭尾
Node<K,V> loHead = null, loTail = null;
//高位鏈表的頭尾
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//循環把鏈表拆分 放到兩個鏈表裏面
do {
next = e.next;
//散列下標不變的情況 oldCap=16
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//散列下標變的情況
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//兩個做法都是把鏈表放在新的位置
//放在新表原位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//放在新表j+oldCap位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
HashMap1.8將鏈表通過運算拆封成兩個鏈表存放到新的table中
HashMap面試題
HashMap什麼時候會轉換為紅黑樹
數組容量大於64並且鏈表長度大於8時
HashMap為什麼要引進紅黑樹，為了解決什麼問題？
鏈表查詢時間複雜度為O(n),查詢效率太低了，引用紅黑樹查詢效率可以變為O(logN)
HashMap的長度為什麼必須是2的次冪？
這樣長度一定是偶數，在計算index下標的時候(n-1)&hash，這樣（n-1）就會是奇數，奇數&hash值才會減小衝突。n取 2 的整數次冪，是為了使不同 hash 值發生碰撞的概率較小，這樣就能使元素在哈希表中均勻地散列
如何避免HashMap內存溢出問題
因為沒有重寫hashcode和equals和方法，底層默認用==比較內存地址，就會導致new出多個對象，重寫之後每次比較都會是同一個對象，會做覆蓋。
HashMap根據key查詢的時間複雜度
如果key沒有產生衝突，時間複雜度為O(1)，一次就能查到
如果key產生衝突鏈表存放為O(n)，紅黑樹存放為O(logn)
HashMapKey為null存放在什麼位置
第0個位置
int index = k == null ? 0 : k.hashCode() % objects.length;
HashMap底層是採用單鏈表還是雙鏈表
單向鏈表
HashMap底層是有序存放的嗎
單向鏈表存放無序散列，會將所有鏈表和紅黑樹都遍歷，效率非常低
LinkedHashMap 和 TreeMap底層如何實現有序的
原理：將每個index中的鏈表實現關聯，效率比HashMap要低
緩存淘汰算法底層實現原理LinkedHashMap
Redis如果緩存滿的情況下如何清理？
LUR算法:清理最近少用的key
方案1：對每個key記錄使用次數，然後排序再刪除 效率非常低
方案2：基於LinkedHashMap有序集合實現 訪問key的時候就會將key存到鏈表最後的位置
插入順序：先添加的在前面，後添加的在後面。修改操作不影響順序
執行get/put操作後，其對應的鍵值對會移動到鏈表末尾，所以最末尾的是最近訪問的，最開始的是最久沒有被訪問的，這就是訪問順序。
其中參數accessOrder就是用來指定是否按訪問順序，如果為true，就是訪問順序。
為什麼HashMap不使用取模運算
k.hashcode()%entrys.length取模會導致key衝突概率非常大
就會導致變為鏈表O(n)或者紅黑樹O(logn),需要降低Hash衝突概率，均勻的放在數組的每個下標的位置
求下標i=(n-1)&hash,為什麼（n-1）變成了奇數
擴容默認是偶數，2的n次冪。如果是偶數&（與運算）hash，index衝突概率非常大，會使數據分佈不均
所以需要變成奇數
HashMap如何降低Hash衝突
hash函數計算i=(n-1)&hash,通過奇數余hash值能夠降低hash值發生衝突的概率
加載因子為什麼是0.75而不是1
如果加載因子越大（1），空間利用率比較高16個位置都填滿了，這樣index衝突概率比較大
如果加載因子越小（0.1），達到0.1就擴容那麼空間利用率越小，能存放的位置更多，這樣index衝突概率越小
空間和時間上的平衡點：0.75
統計學概率：泊松分佈是統計學和概率學常見的離散概率分佈
Hashap存放1W條數據怎麼樣效率最高
hashmap容量=（需要存儲的元素個數/擴容因子）+1=（10000/0.75）+1=13334
目的是減少底層擴容的次數，如果沒有設置初始容量大小，hashmap需要進行7次擴容，嚴重影響性能
Hashmap1.7和Hashmap1.8的區別
Hashmap1.7基於數組+鏈表實現頭插法，寫法簡單 但是有多線程死循環問題
Hashmap1.8基於數組+鏈表+紅黑樹實現尾插法，解決了多線程死循環問題
能夠降低key對應的index的衝突概率，提高查詢率
原來的鏈表使用與運算hash&原來table長度，拆分成兩個鏈表放到新數組中，能夠將鏈表長度縮短，提高查詢效率
