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

【56|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 *Date2020/9/21 0021 19:48 *缓存淘汰策略访问顺序get/put操作后其对应的键值会移动到末尾 */ public class LruCacheextends LinkedHashMap { /** * 容量 */ private intcapacity; public LruCache(int capacity){ super(capacity,0.75f,true); this.capacity=capacity; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { returnsize()>capacity; }public static void main(String[] args) { LruCache 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，它们被分配在了数组的不同位置，这样，哈希的分布非常均匀。