美文网首页
linkedhashmap图解

linkedhashmap图解

作者: miky_zheng | 来源:发表于2019-01-24 23:48 被阅读0次
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(); }
}

相关文章

网友评论

      本文标题:linkedhashmap图解

      本文链接:https://www.haomeiwen.com/subject/qnepjqtx.html