目录7. 源码解读 7.2 JDK1.源码解读8. 集合源码解读9. [源码注释]()
1. 基于集合方式实现
public class ArraylistHashMap {private List> entries = new ArrayList>();class Entry {K k;V v;Entry next;public Entry(K k, V v) {this.k = k;this.v = v;}}public void put(K k, V v) {entries.add(new Entry<>(k, v));}public V get(K k) {for (Entry entry :entries) {if (entry.k.equals(k)) {return entry.v;}}return null;}public static void main(String[] args) {ArraylistHashMap arraylistHashMap = new ArraylistHashMap<>();arraylistHashMap.put("demo", "123");arraylistHashMap.put("123", "demo");System.out.println(arraylistHashMap.get("123"));}}
根据key查询时间复杂度为o(n),效率非常低 。
2. 基于数组+链表方式实现(Jdk)
.7底层是如何实现的 基于数组+链表实现
同一个链表中存放的都是值可能相同，但是内容值却不同
public class ExtHashMap {private Entry[] objects = new Entry[10000];class Entry {public K k;public V v;Entry next;public Entry(K k, V v) {this.k = k;this.v = v;}}public void put(K k, V v) {int index = k == null ? 0 : k.hashCode() % objects.length;Entry oldEntry = objects[index];// 判断是否存在if (oldEntry == null) {objects[index] = new Entry<>(k, v);} else {// 发生hash碰撞则存放到链表后面oldEntry.next = new Entry<>(k, v);}}public V get(K k) {//if (k == null) {//for (Entry oldEntry = objects[0]; oldEntry != null; oldEntry = oldEntry.next) {//if (oldEntry.k.equals(k)) {//return oldEntry.v;//}//}//}int index = k == null ? 0 : k.hashCode() % objects.length;for (Entry oldEntry = objects[index]; oldEntry != null; oldEntry = oldEntry.next) {if (oldEntry.k == null || oldEntry.k.equals(k)) {return oldEntry.v;}}return null;}public static void main(String[] args) {ExtHashMap hashMap = new ExtHashMap<>();hashMap.put("a", "a");hashMap.put(97, "97");hashMap.put(null, "nulldemo");System.out.println(hashMap.get(97));}}
3. 底层是有序存放的吗？
无序、散列存放
遍历的时候从数组0开始遍历每个链表，遍历结果存储顺序不保证一致 。
如果需要根据存储顺序保存，可以使用底层是基于双向链表存放
基于双向链表实现
基本单向链表实现
4. 实现缓存淘汰框架
LRU(最近少使用)缓存淘汰算法
LFU(最不经常使用算法)缓存淘汰算法
ARC(自适应缓存替换算法)缓存淘汰算法
FIFO（先进先出算法）缓存淘汰算法
MRU(最近最常使用算法)缓存淘汰算法
基于双向链表实现，可以分为插入或者访问顺序两种，采用双链表的形式保证有序
可以根据插入或者读取顺序
是的子类，但是内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于双向链表中 。支持两种顺序插入顺序 、 访问顺序
插入顺序：先添加的在前面，后添加的在后面 。修改操作不影响顺序
执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序 。
其中参数就是用来指定是否按访问顺序，如果为true，就是访问顺序,false根据新增顺序
public class LruCache extends LinkedHashMap {/*** 容量*/private int capacity;public LruCache(int capacity) {super(capacity, 0.75f, true);this.capacity = capacity;}/*** 如果超过存储容量则清除第一个** @param eldest* @return*/@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size() > capacity;}public static void main(String[] args) {LruCache lruCache = new LruCache<>(3);lruCache.put("a", "a");lruCache.put("b", "b");lruCache.put("c", "c");// ca elruCache.get("a");//caelruCache.put("e", "demo");lruCache.forEach((k, v) -> {System.out.println(k + "," + v);});}}