linkedhashmap图解

IMG_20190117_111300.jpg

上图分析
1.和hashmap单链表结构相比，linkedhashmap是双链表，首尾相连。
2.若涉及访问顺序，则如图2方法插入数据。

其他关于linkedhashmap，lru总结：

hashmap1.8结构：数组+红黑树+链表
LinkedHashMap1.8结构，数组+红黑树+双向链表。
LinkedHashMap是继承于HashMap，是基于HashMap和双向链表来实现的。
HashMap无序；LinkedHashMap有序，可分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)。

1.无论是树结构还是双头node，添加完，linkNodeLast(p);
2.访问顺序，实现lru核心方法：accessOrder=true；
void afterNodeAccess(Node<K,V> e)
if (accessOrder && (last = tail) != e) {//判断如果是队尾就不用变动
3.查询还是用的hashmap的方法（如果是红黑树，就用树的查询方法），如果是访问顺序，就重排双向链表结构

父类hashmap其他属性----------

HashMap诞生的原由(优点)，即查找快，插入删除也快

数组
数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；
链表
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。
哈希表
那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便

HashMap扩容：

当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中，如果没有默认值，初始化：16

hashmap最理想的状况是：只有数组，时间复杂度o(1)

在Java jdk8中对HashMap的源码进行了优化，在jdk7中，HashMap处理“碰撞”的时候，都是采用链表来存储，当碰撞的结点很多时，查询时间是O（n）。
在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）

你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。

通过treeifyBin（）将链表改为红黑树

构造函数

默认不传，resize
传size，会增加2n，size<2n

  static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

增，改

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal:-------------------
1.为size为null，就resize；
if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

2.key相等就++size，++modCount;判断是否超过域值：resize();
 if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);

3.已有hash，比较key,判断是否TreeNode；否则查找相同hash的链表末尾，添加数据，如果当中超过域值，treeifyBin(tab, hash)。
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

查

public V get(Object key) {

删

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

resize

1.如果 >= MAXIMUM_CAPACITY，不改变内部数组大小
如果老的lenth>16,并且老的lenth*2<MAXIMUM_CAPACITY,新的阈值*2
否则，else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;

否则，初始化阈值为0.75*16，新size为16
newCap = DEFAULT_INITIAL_CAPACITY; 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16

2.如果阈值>0和size==0的时候，新的size=老阈值？？
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
}
3.设置新阈值
4.创建新的tab，释放老的tab空间，
if (e.next == null)
    newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else{
    循环
    if ((e.hash & oldCap) == 0) {
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
}
else {
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}

}

遍历

EntrySet：：set
node：：map.entry

三种HashIterator

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}