HashMap底層是有序存放的嗎？
無序、散列存放
遍歷的時(shí)候從數(shù)組0開始遍歷每個(gè)鏈表，遍歷結(jié)果存儲順序不保證一致。
如果需要根據(jù)存儲順序保存，可以使用LinkedHashMap底層是基于雙向鏈表存放
LinkedHashMap基于雙向鏈表實(shí)現(xiàn)
HashMap基本單向鏈表實(shí)現(xiàn)

LinkedHashMap實(shí)現(xiàn)緩存淘汰框架

LRU(最近少使用)緩存淘汰算法
LFU(最不經(jīng)常使用算法)緩存淘汰算法
ARC(自適應(yīng)緩存替換算法)緩存淘汰算法
FIFO（先進(jìn)先出算法）緩存淘汰算法
MRU(最近最常使用算法)緩存淘汰算法

LinkedHashMap基于雙向鏈表實(shí)現(xiàn)，可以分為插入或者訪問順序兩種，采用雙鏈表的形式保證有序
可以根據(jù)插入或者讀取順序

LinkedHashMap是HashMap的子類，但是內(nèi)部還有一個(gè)雙向鏈表維護(hù)鍵值對的順序，每個(gè)鍵值對既位于哈希表中，也位于雙向鏈表中。LinkedHashMap支持兩種順序插入順序 、 訪問順序

插入順序：先添加的在前面，后添加的在后面。修改操作不影響順序
執(zhí)行g(shù)et/put操作后，其對應(yīng)的鍵值對會移動(dòng)到鏈表末尾，所以最末尾的是最近訪問的，最開始的是最久沒有被訪問的，這就是訪問順序。
其中參數(shù)accessOrder就是用來指定是否按訪問順序，如果為true，就是訪問順序,false根據(jù)新增順序

package com.taotao.hashmap001;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 *@author tom
 *Date  2020/9/21 0021 19:48
 *緩存淘汰策略  訪問順序  get/put操作后其對應(yīng)的鍵值會移動(dòng)到末尾
 */
public class LruCache<K,V>extends LinkedHashMap<K,V> {
    /**
     * 容量
     */
    private int  capacity;

    public LruCache(int capacity){
        super(capacity,0.75f,true);
        this.capacity=capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
       return  size()>capacity;
    }

    public static void main(String[] args) {
        LruCache<String,String> lruCache=new LruCache<>(3);
 lruCache.put("a","a");
 lruCache.put("b","b");
 lruCache.put("c","c");
 lruCache.put("d","d");
 lruCache.forEach((k,v)->{
     System.out.println("k= "+k);
 });

    }
}

hashMap 如何降低hash沖突概率：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
((p = tab[i = (n - 1) & hash])

1、保證不會發(fā)生數(shù)組越界
首先我們要知道的是，在HashMap，數(shù)組的長度按規(guī)定一定是2的冪。因此，數(shù)組的長度的二進(jìn)制形式是：10000…000, 1后面有偶數(shù)個(gè)0。 那么，length - 1 的二進(jìn)制形式就是01111.111, 0后面有偶數(shù)個(gè)1。最高位是0, 和hash值相“與”，結(jié)果值一定不會比數(shù)組的長度值大，因此也就不會發(fā)生數(shù)組越界。一個(gè)哈希值是8，二進(jìn)制是1000，一個(gè)哈希值是9，二進(jìn)制是1001。和1111“與”運(yùn)算后，結(jié)果分別是1000和1001，它們被分配在了數(shù)組的不同位置，這樣，哈希的分布非常均勻。