文档章节

HashMap源码理解

清尘V
 清尘V
发布于 2016/04/16 17:34
字数 1634
阅读 285
收藏 3
private static int roundUpToPowerOf2(int number) {
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
  • Integer.highestOneBit方法是获取不大于本身的2^n的值,那该方法具体含义是:

  • 获取新的数组容量值,如果给定值大于等于最大的容量,则返回最大容量,否则:如果容量小于等于1,则返回1,否则返回大于等于给定值的最接近的2^n的值

  • 容量为什么要是2^n次方呢?且看如下代码:

  • static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

    • 给方法是查找h(ash)在数组的索引位置;那现在看length为什么要是2^n次方呢?点此查看

    • 保证&之后的数据不大于length

    • length-1之后,最低的n位都是1,那与h的&运算之后的值即是h的最低n位

    • 采用length-1而不是直接length是因为2^n最低一位是0,那&运算之后数据都分布在偶数位,不是随机的

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

扩容:先获取最接近并且>=指定容量的的数值作为扩容后的容量;扩容界限就是取容量*加载因子和最大容量+1的最小值;重新初始化table;扩容之后的table没有任何数据,所以在相关调用操作之后会有数据重新分配操作,比较耗时,所以在初始化一个hashmap的时候最好指定容量避免扩容操作发生

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

get方法:

  •     如果key==null,则单独获取

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}


  • 如果size==0,则直接返回null;

  • 遍历table,判断key,返回value

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}


根据key获取Entry:

  •     获取hash值

  • 获取数组索引

  • 获取数组中索引的第一个entry

  • 遍历entry,如果hash值相等并且(key相等或者equal),则返回当前entry即可

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

判断key是否存在只是调用getEntry方法判断是否为null即可

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

put方法:

  •     如果table为空数组,则先扩容到扩容界限(threshold)的数组,如果是默认的初始化方法,则threshold=容量;执行该方法之后。threshold=容量*加载因子;

  • 如果key==null,单独存入该值,putForNullKey

  • 根据hash和length获取table索引,找出第一个entry

  • 遍历entry,如果找到则重新设置新值,返回旧值,否则新添加一个entry(addEntry)

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}
  • 存入key==null的value,直接查找table的第一个位置(index=0),如果找到则重新设置新值,返回旧值,否则添加新的entry;

  • key==null的值全部在table【0】的entry上

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}


创建新的entry:

  • 先检查是否满足扩容条件:size>=threshold&&null!=table[bucketIndex];

  • 如果满足扩容,计算新的hash和数组索引(bucketIndex)

  • 创建新的entry(createEntry)

  • 注意事项:size是针对hash表里的所有数据的容量,而扩容是指数组扩容

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
  • 先获取oldTable的length,如果已是最大长度,则无需扩容,并且将threshold设为Integer.MAX_VALUE,不可扩容!

  • 创建新的Entry数组,将旧的table数据添加到newTable中(transfer)

  • 设置新的table和threshold

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

简单理解为:数据拷贝

  • 获取新的数组长度,遍历table数组;

  • 遍历每个链表:重定向到新的数组和链表中

  • 现在遍历到[1,0]即table[1]下的第一个entry,计算得出在新的i=5,则该entry的下一个是newTable[5],newTable[5]=entry

  • 从以上可以看出,新进入newTable的数据在后进入的next下

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

创建新的Entry:

  • 先根据索引(bucketIndex)获取数组中的元素(e)

  • 创建新的entry,位于链表第一个entry,而e是当前新的entry的next

public void putAll(Map<? extends K, ? extends V> m) {
    int numKeysToBeAdded = m.size();
    if (numKeysToBeAdded == 0)
        return;

    if (table == EMPTY_TABLE) {
        inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
    }

    /*
     * Expand the map if the map if the number of mappings to be added
     * is greater than or equal to threshold.  This is conservative; the
     * obvious condition is (m.size() + size) >= threshold, but this
     * condition could result in a map with twice the appropriate capacity,
     * if the keys to be added overlap with the keys already in this map.
     * By using the conservative calculation, we subject ourself
     * to at most one extra resize.
     */
    if (numKeysToBeAdded > threshold) {
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        int newCapacity = table.length;
        while (newCapacity < targetCapacity)
            newCapacity <<= 1;
        if (newCapacity > table.length)
            resize(newCapacity);
    }

    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

将一个集合添加到现有集合中:

  • 先获取要添加结合的元素数量

  • 如果现有集合是空集合,扩容:当前threshold和根据添加元素容量计算的新容量的最大值

  • 假如添加的集合元素数量>threshold,则判断当前table是否需要扩容

  • 此处是保守估计新的集合添加之后的容量:但是可以保证最多只有一次调用resize方法!

  • 如果numKeysToBeAdded <=threshold,即使在put方法导致扩容也至多有一次:扩容至两倍,那threshold也会变为两倍

  • 如果numKeysToBeAdded >threshold,如果:targetCapacity>table.length,则在put方法可能会导致resize,否则newCapacity必定大于table.length,在此处resize,put方法就不会resize了

    


参考文章:http://blog.csdn.net/eson_15/article/details/51158865

个人博客:http://www.whereta.com

© 著作权归作者所有

共有 人打赏支持
清尘V
粉丝 43
博文 107
码字总数 47780
作品 0
青岛
程序员
Java容器源码分析-HashMap vs TreeMap vs LinkedHashMap

这里我采用的分析方式是帖子博客加上自己翻看jdk源码。有些情况下写一些测试的算法小例子加深印象。我这里只描述一下自己的总结想法 上一篇文章我们研究了set接口下的几个容器,由于其Set集合...

贾浩v
2017/10/19
0
0
Java8之HashMap源码分析

高级Java架构交流群:283943715 java高级交流群 一、前言   在分析jdk1.8后的HashMap源码时,发现网上好多分析都是基于之前的jdk,而Java8的HashMap对之前做了较大的优化,其中最重要的一个...

小炎哥
2017/06/19
419
1
集合源码学习(十一):LinkedHashMap

何为LinkedHashMap LinkedHashMap是一个,具有顺序的HashMap,也就是使用Iterator进行迭代时,顺序与put进来的顺序是一致的。 先看LinkedHashMap的定义: 如上,LinkedHashMap继承自HashMap...

anLA_
2017/10/20
0
0
浅谈HashMap

HashMap结构图 image.png HashMap主要方法 final int hash(Object k) static int indexFor(int h, int length) void resize(int newCapacity) public V put(K key, V value) public V get(O......

小鱼嘻嘻
2017/10/28
0
0
详解 Java 8 HashMap 实现原理

HashMap 是 Java 开发过程中常用的工具类之一,也是面试过程中常问的内容,此篇文件通过作者自己的理解和网上众多资料对其进行一个解析。作者本地的 JDK 版本为 64 位的 1.8.0_171。参考资料...

☆★傲天★☆
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

jetbrains系产品IDEA:mac上面提示快捷键设置

原因 由于Mac上面的Ctrl+空格变成输入法切换的快捷键,在使用IDEA的过程中,代码提示很不方便,需要使用option+/这种传统eclipse上面的代码提示快捷键作为主要快捷键。 怎么修改? 移除【opt...

亚林瓜子
33分钟前
0
0
Exclipse 输出结果时换行

System.out.println(f1 + "\n" + d1 + "\n" + d2);

笑丶笑
34分钟前
1
0
怎样治疗标签不能触发onblur事件

I realize this was over a year ago, but it showed up for me in Google while trying to solve this same issue. It seems Chrome does not consider some elements, like body and ancho......

Weijuer
37分钟前
0
0
vue常见库安装

移动设备上的浏览器默认会在用户点击屏幕大约延迟300毫秒后才会触发点击事件,这是为了检查用户是否在做双击。为了能够立即响应用户的点击事件,才有了FastClick。 安装fastclick npm insta...

林夏夕
39分钟前
0
0
kafka 教程(三) kafka Java API 编程

下午写

MrPei
40分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部