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，它们被分配在了数组的不同位置，这样，哈希的分布非常均匀。
网友评论