HashMap&LinkedHashMap&Lr

1、HashMap

hashmap

1.1、 put函数的实现

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算index，并对null做处理
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 节点存在
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 该链为树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 写入
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超过load factor*current capacity，resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put函数大致的思路为：

1、对key的hashCode()做hash，然后再计算它在数组中的index;
2、如果没碰撞直接放到bucket里；
3、如果碰撞了，以链表的形式存在buckets后；
4、如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
5、如果节点已经存在就替换old value(保证key的唯一性)；
6、如果bucket满了(超过load factor*current capacity)，就要resize。

1.2、get函数的实现

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 直接命中
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 未命中
        if ((e = first.next) != null) {
            // 在树中get
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在链表中get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get大致思路如下：

0、对key的hashCode()做hash，然后再计算它在数组中的index;
1、如果hash相等并且key相等，直接命中；
2、如果有冲突，就去树中或者链表中寻找；
3、若为树；O(logn)；
4、若为链表，O(n)。

1.3、hash实现

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash实现

高16bit不变，低16bit和高16bit做了一个异或，计算下标的方式是(n - 1) & hash，异或一下，在bucket的n比较小的时，也可以让高16位和低16位都参数下标计算，有效缓解碰撞。

1.4、hashmap原理速记

hashmap是采用数组+链表的形式去存储键值对的，在java1.8中为了更快的查询，它会在链表超过一定长度时将链表转换成红黑树；它的put过程大概是这样的,,,；它的get过程大概是这样的,,,。

2、LinkedHashMap

linkedhashmap

LinkedHashMap是Hashmap+双向链表，并且依靠双向链表保持顺序。

2.1、三个重点实现的函数

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

LinkedHashMap继承于HashMap，因此也重新实现了这3个函数，顾名思义这三个函数的作用分别是：节点访问后、节点插入后、节点移除后做一些事情。

2.1.1、afterNodeAccess函数

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 如果定义了accessOrder，那么就保证最近访问节点放到最后
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

意思是如果定义了accessOrder，就把这个节点从双向链表原位置删除然后放到最后。（注意此时节点的next地址是不变的，改变的只是它的before和after地址）看似代码很乱，画图很容易理解。

2.1.2、afterNodeInsertion函数

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 如果定义了移除规则，则执行相应的移除
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

意思是 ，如果定义了移除规则removeEldestEntry，则执行相应的移除。（移除的是双向链表头结点，最近最少使用的节点）。

2.1.3、afterNodeRemoval函数

void afterNodeRemoval(Node<K,V> e) { // unlink
    // 从链表中移除节点
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

意思是节点从hash表中删除后也要从双向链表中删除。

2.2、put和get函数

put函数在LinkedHashMap中未重新实现，只是实现了afterNodeAccess和afterNodeInsertion两个回调函数，在hashmap中的put方法中有对应调用。
get函数则重新实现并加入了afterNodeAccess来保证访问顺序，下面是get函数的具体实现：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

2.3、LinkedHashMap原理速记

LinkedHashMap是Hashmap+双向链表构成的，并且依靠双向链表保持顺序。
accessorder模式下，一个节点被访问之后就会将它从双向链表的原位置删除并放到最后，当一个节点插入后，如果重写了移除规则removeEldestEntry方法，则移除双向链表的首节点，即最近最少使用的节点，以此来实现LRU。

3、LruCache

3.1、LruCache构造

public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

LruCache使用accessorder模式的LinkedHashMap构造。

3.2、put方法

public final V put(K key, V value) {
         //不可为空，否则抛出异常
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }
        V previous;
        synchronized (this) {
            //插入的缓存对象值加1
            putCount++;
            //增加已有缓存的大小
            size += safeSizeOf(key, value);
           //向map中加入缓存对象
            previous = map.put(key, value);
            //如果已有缓存对象，则缓存大小恢复到之前
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }
        //entryRemoved()是个空方法，可以自行实现
        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        //调整缓存大小(关键方法)
        trimToSize(maxSize);
        return previous;
    }

put()方法将键值对插入存储到LinkedHashMap中，然后调用 trimToSize()方法，来判断缓存是否已满，如果满了就是使用Lru算法进行删除。

trimToSize方法

public void trimToSize(int maxSize) {
        //死循环
        while (true) {
            K key;
            V value;
            synchronized (this) {
                //如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }
                //如果缓存大小size小于最大缓存，或者map为空，不需要再删除缓存对象，跳出循环
                if (size <= maxSize || map.isEmpty()) {
                    break;
                }
                //迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                //删除该对象，并更新缓存大小
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            entryRemoved(true, key, value, null);
        }
    }

trimToSize()方法不断地删除LinkedHashMap中队头的节点，即最近最少访问的节点，直到缓存大小小于最大值。

3.2、get方法

public final V get(K key) {
        //key为空抛出异常
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            //获取对应的缓存对象
            //get()方法会实现将访问的元素更新到队列头部的功能
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

调用LinkedHashMap的get方法去获取数据，并维持访问顺序。

3.2、LruCache原理速记

LruCache内部维护了一个LinkedHashMap，并使用LinkedHashMap的accessorder模式去实现Lru算法，LinkedHashMap是Hashmap+双向链表构成的，并且依靠双向链表保持顺序。accessorder模式下，一个节点被访问之后就会将它从双向链表的原位置删除并放到最后，当一个节点插入后，如果大于了LruCache的最大容量，就会移除双向链表的首节点，即最近最少使用的节点，以此来实现LRU。

4、LinkedHashMap实现LruCache

public class LRUCache <K, V>{
    private int capacity;
    private Map<K, V> cache;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new java.util.LinkedHashMap<K, V> (capacity, 0.75f, true) {
            // 定义put后的移除规则，大于容量就删除eldest
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > capacity;
            }
        };
    }
    public V get(K key) {
            return cache.get(key);
    }
    public V put(K key, V value) {
        return cache.put(key, value);
    }
}