如果我們的hashMap源碼單純的用數(shù)組實現(xiàn)，那么它們的增加和查找的時間復雜度為o(n)，因為在增加的時候要遍歷一次查詢key是否存在，在查找的時候要遍歷一次查找key。但是HashMap使用了散列表來存儲數(shù)據(jù)，可以使得增加和查找的時間復雜度為o(1)。
散列表
散列表示意圖
數(shù)組的各個下標相當于一個個桶，通過hashCode(key)就可以拿到每個桶的下標，桶里面的數(shù)據(jù)用鏈表存儲，因此如果此時桶里只有一個鏈節(jié)點就只要o(1),有兩個節(jié)點就只要o(2)，一個桶裝的鏈表節(jié)點太多還可以轉(zhuǎn)換成紅黑樹。這就是散列表的好處。
源碼分析
如下是我自己寫的簡易版的hashMap:
public class HashMapSample<K,V> {
/**
* 散列表(桶)
*/
public MapEntry[] tables;
/**
*存放的個數(shù)
*/
transient int size;
/**
* 擴容閾值
*/
int threshold = 12;
/**
* 加載因子
*/
final float loadFactor = 0.75f;
public class MapEntry<K,V>{
K key;
V value;
MapEntry<K,V> next; //鏈表
int hash;
public MapEntry(int hash,K key,V value,MapEntry<K,V> next){
this.hash=hash;
this.key=key;
this.value=value;
this.next=next;
}
}
private int getIndext(int hash,int length) {
//大小為2的冪次方,因為&操作符是:兩個1為1，其他為0。2的冪次方-1的二進制全是1，可避免過度哈希沖突
return hash&length-1;
}
//哈希code得到哈希值
private int hash(K key) {
int h = 0;
return key==null?0:(h=key.hashCode()^(h>>>16));
//兩對象hash相等，兩個對象可能相等；兩個對象hash不等，則倆對象一定不等
//原理: value>16,是對象的32位地址向右移了16位，剩下的16位可能相等
}
/**
* Get區(qū)域
* @param key
* @return
*/
public V get(K key){
if(key == null){
return null;
}
//判斷有沒有該key
MapEntry<K,V> mapEntry =getEntry(key);
return mapEntry==null?null:mapEntry.value;
}
private MapEntry<K,V> getEntry(K key) {
//判斷同一個桶是否有這個key
int hash=hash(key);
int indext = getIndext(hash,tables.length);
for(MapEntry<K,V> mapEntry = tables[indext];mapEntry!=null;mapEntry=mapEntry.next){
Object k;
if(mapEntry.hash == hash && ((k=mapEntry.key)==key || key.equals(k))){
return mapEntry;
}
}
return null;
}
/**
* Put區(qū)域
* @param key
* @param value
* @return
*/
public V put(K key,V value){
if(tables == null){
tables=new MapEntry[16];
}
if(key==null){
return null;
}
//1.找到table的位置
int hash = hash(key);
int index = getIndext(hash,tables.length);
//2.判斷有沒有重復key
for(MapEntry<K,V> table = tables[index];table!=null;table=table.next){
Object k;
if(table.hash == hash && ((k=table.key)==key || key.equals(k))){
V oldValue = table.value;
table.value=value;
return oldValue;
}
}
//3.添加一個新的mapEntry
addEntry(hash,key,value,index);
return null;
}
/**
* 添加一個新的entry
* @param hash
* @param key
* @param value
* @param index
*/
private void addEntry(int hash,K key,V value,int index){
//判斷要不要擴容
if(size>=threshold && tables[index] != null){
resize(size<<1);
//跟新添加的index
index = getIndext(hash,tables.length);
}
//真正的執(zhí)行添加
createEntry(hash,key,value,index);
}
private void createEntry(int hash, K key, V value, int index) {
MapEntry<K,V> newMapEntry = new MapEntry<>(hash,key,value,tables[index]);
newMapEntry.next=tables[index];
tables[index]=newMapEntry;
}
private void resize(int newCapacity) {
MapEntry<K,V>[] newTable = new MapEntry[newCapacity];
//重新計算index
transform(newTable);
tables = newTable;
threshold =(int)(newCapacity*loadFactor);
}
private void transform(MapEntry<K,V>[] newTable) {
//重新計算index
int newCapacity = newTable.length;
for (MapEntry<K,V> e:tables){
//這里的節(jié)點會變成逆序排序，如1-2-3變成3-2-1
//在多線程執(zhí)行時會造成死循環(huán)，如兩個對象的next相互調(diào)用
while (null != e){
MapEntry<K,V> next = e.next;
int index = getIndext(e.hash,newCapacity);
//先把newTable[index]的值存到e.next
e.next= newTable[index];
//把e存到第一個newTable[index]
newTable[index] = e;
//給e繼續(xù)遍歷舊table的鏈節(jié)點
e=next;
}
}
}
}
加載因子：為什么是0.75？不是1
因為：如果加載因子太小，就會導致太快的擴容(擴容要進行遍歷一次重新計算index)。如果加載因子太大，比如100，就是導致散列表的每個桶存放太多的節(jié)點。為什么不是1，是因為用一個空間換時間的概念。
為什么hashMap的大小是2的冪次方
因為使用hash&length-1這個公式把得到的hash值&(求%)時2的冪次方-1的二進制全都是1，對哈希值的影響小。可避免過度的哈希碰撞。
hashcode的計算原理
利用對象的地址(32位)，然后右移16位，即取后面的16位的二進制作為hash值。所以hash值相等，兩對象可能不等；hash值不相等，兩對象一定不相等。
初始化大小
hashMap的初始化的大小為16，因為擴容對性能比較消耗，所以我們在知道數(shù)據(jù)大小的情況下要盡量不擴容，我們可以手動初始化大小為:count*0.75+1
多線程下在hashMap中put導致的問題
數(shù)據(jù)丟失，死循環(huán)：每個子線程都有自己的工作內(nèi)存，通過拷貝需要的部分在主內(nèi)存的資源到子線程的工作內(nèi)存，子線程修改好后就將資源更新到主內(nèi)存。hashMap就在主內(nèi)存，所以會造成子線程的獲取資源的不同步。
1.死循環(huán)，在擴容時舊表的元素重新計算index時，多線程情況下，鏈節(jié)點可能會形成環(huán)，從而造成死循環(huán)。
2.多線程同時對同一鏈表增加數(shù)據(jù)，更新后可能會導致數(shù)據(jù)丟失，前面存儲的數(shù)據(jù)被覆蓋。不同鏈表的增加數(shù)據(jù)，更新后不會影響。
解決方案：1.hashTable、2.Collections.synchronizedMap() 3.ConcurrentHashMap :前兩個方法都是鎖住方法，conCurrentHashMap利用：分段鎖 Lock , 分段鎖 （synchronized，CAS）。
當put方法synchronized時，其他線程也不可以get()操作。
image.png
hashTable、ConcurrentHashMap的分析：
1.hashTable是將整個方法加上synchronized，整個方法鎖住比較消耗性能，因為整個hash表都被鎖住了，其他線程只能阻塞等待重新去搶資源。一個線程在 put 的時候，另外一個線程不能再 put 和 get 必須進入等待狀態(tài)。
2.concurrentHashMap則是把需要改變的鏈表鎖住，而不是把整個hash表鎖住，其他線程的就可以訪問hash表里未被鎖住的鏈表。這樣多線程就不會同時改動同一個鏈表造成數(shù)據(jù)丟失和死循環(huán)，也提高了性能。
concurrentHashMap源碼：
// volatile 保證可見性
transient volatile Node<K,V>[] table;
// 新增元素的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 二次 hash
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果 tab 為空，初始化 tab
if (tab == null || (n = tab.length) == 0){
tab = initTable();
}
// 當前 tab 的 index 鏈表為 null
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 鎖住當前 tab 的 index 鏈表（分段鎖）
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
// ......
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
// CAS 操作
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 遍歷當前列表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
synchronized 底層實現(xiàn)原理
// 1.對于普通同步方法，鎖是當前實例對象。this
public synchronized void method(){
}
// 2.對于靜態(tài)同步方法，鎖是當前類的Class對象。this.class
public static synchronized void method(){
}
// 3.對于同步方法塊，鎖是Synchonized括號里配置的對象。object
public static synchronized void method(){
synchronized(object){
}
}
其實 synchronized 同步的代碼塊，虛擬機在同步代碼塊開始前會插入一條 monitorenter 指令，在代碼塊的末尾會插入一條 monitorexit 指令。而每個對象的 Mark Word 頭信息里都會存儲 Monitor 信息，也就是當前對象的鎖信息，當然 Mark Word 頭信息還包含對象的 hashCode 和 GC 的分代年齡
image.png
LinkedHashMap分析
hashMap不是一個有序的map，所以LinkedHashMap出現(xiàn)了。
hashMap用散列表"數(shù)組+單鏈表實現(xiàn)",LinedList用"雙向鏈表實現(xiàn)"實現(xiàn)順序存儲數(shù)據(jù)。LinedHashMap就是用"hashMap+LinkedList"的散列表的雙鏈回環(huán)實現(xiàn)。
小demo
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("apple", "蘋果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
輸出：
apple=蘋果
watermelon=西瓜
banana=香蕉
peach=桃子
還可以再根據(jù)訪問順序再排序：
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
map.put("apple", "蘋果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
map.get("banana");
map.get("apple");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
輸出：
watermelon=西瓜
peach=桃子
banana=香蕉
apple=蘋果
LinkedHashMap源碼實現(xiàn)
先總結(jié)：
- LinkedHashMap繼承自HashMap,它的新增(put)和獲取(get)方法都是復用父類的HashMap的代碼，只是自己重寫了put給get內(nèi)部的某些接口來搞事情。
- LinkedHashMap的數(shù)據(jù)存儲和HashMap的結(jié)構(gòu)一樣采用(數(shù)組+單向鏈表)的形式，只是在每次節(jié)點Entry中增加了用于維護順序的before和after變量維護了一個雙向鏈表來保存LinkedHashMap的存儲順序，當調(diào)用迭代器的時候不再使用HashMap的的迭代器，而是自己寫迭代器來遍歷這個雙向鏈表即可。
第一：給entry加上befor,after這個前指針：
next是用于維護HashMap指定table位置上連接的Entry的順序的，before、After是用于維護Entry插入的先后順序的(為了維護雙向鏈表)。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before;
Entry<K,V> after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
...
}
第二：初始化
public LinkedHashMap() {
super();
accessOrder = false; //LinkedHashMap特有的元素
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init(); //此方法LinkedHashMap進行了重寫
}
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
}
可以看到header就是我們雙鏈表的表頭。
LinkedHashMap添加元素
HashMap的put方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
////1.找到table的位置
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//查看是否有相同的Key
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;
}
}
//沒有相同的key
modCount++;
//這個方法先檢查要不要擴容，再添加entry
addEntry(hash, key, value, i);
return null;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//設置accessOrder為true才執(zhí)行，重排序
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
private void remove() {
//如果這個entry沒有前后節(jié)點則不執(zhí)行。
this.before.after = after;
this.after.before = before;
}
private void addBefore(Entry<K,V> existingEntry) {
//表頭
after = existingEntry;
//通過雙向鏈表的表頭找到最后一個元素
before = existingEntry.before;
before.after = this; //把最新的元素排到最后
after.before = this; //更新表頭的前指針
}
LinkedHashMap中重寫了addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
createEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed, else grow capacity if appropriate
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
get方法
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
3. 利用LinkedHashMap實現(xiàn)LRU緩存
就是利用LinedHashMap把accessOrder設置為ture，在(put/get)重排序雙鏈表，這樣表頭就是"最近最少使用數(shù)據(jù)"即LRU
LinkedHashMap的刪除頭結(jié)點的方法：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> var1) {
return false; //默認實現(xiàn)空
}
簡易版的lru
public class LRUCache extends LinkedHashMap
{
public LRUCache(int maxSize)
{
super(maxSize, 0.75F, true);
maxElements = maxSize;
}
protected boolean removeEldestEntry(java.util.Map.Entry eldest)
{
//邏輯很簡單，當大小超出了Map的容量，就移除掉雙向隊列頭部的元素，給其他元素騰出點地來。
return size() > maxElements;
}
private static final long serialVersionUID = 1L;
protected int maxElements;
}
