56 手写LRU缓存淘汰算法与HashMap如何降低Hash冲突

HashMap底层是有序存放的吗？
无序、散列存放
遍历的时候从数组0开始遍历每个链表，遍历结果存储顺序不保证一致。
如果需要根据存储顺序保存，可以使用LinkedHashMap底层是基于双向链表存放
LinkedHashMap基于双向链表实现
HashMap基本单向链表实现

LinkedHashMap实现缓存淘汰框架

LRU(最近少使用)缓存淘汰算法
LFU(最不经常使用算法)缓存淘汰算法
ARC(自适应缓存替换算法)缓存淘汰算法
FIFO（先进先出算法）缓存淘汰算法
MRU(最近最常使用算法)缓存淘汰算法

LinkedHashMap基于双向链表实现，可以分为插入或者访问顺序两种，采用双链表的形式保证有序
可以根据插入或者读取顺序

LinkedHashMap是HashMap的子类，但是内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于双向链表中。LinkedHashMap支持两种顺序插入顺序 、 访问顺序

插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序
执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
其中参数accessOrder就是用来指定是否按访问顺序，如果为true，就是访问顺序,false根据新增顺序

package com.taotao.hashmap001;

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

/**
 *@author tom
 *Date  2020/9/21 0021 19:48
 *缓存淘汰策略  访问顺序  get/put操作后其对应的键值会移动到末尾
 */
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、保证不会发生数组越界
首先我们要知道的是，在HashMap，数组的长度按规定一定是2的幂。因此，数组的长度的二进制形式是：10000…000, 1后面有偶数个0。 那么，length - 1 的二进制形式就是01111.111, 0后面有偶数个1。最高位是0, 和hash值相“与”，结果值一定不会比数组的长度值大，因此也就不会发生数组越界。一个哈希值是8，二进制是1000，一个哈希值是9，二进制是1001。和1111“与”运算后，结果分别是1000和1001，它们被分配在了数组的不同位置，这样，哈希的分布非常均匀。