StackTc
2018-01-29 17:39
采纳率: 61.9%
浏览 2.1k
已采纳

从源码中分析HashMap的get跟put方法

话不多说直接上代码

put

public V put(K key, V value) {
        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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        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;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

#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) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

问题所在

对于2个方法的逻辑看的不是很懂虽然大概知道,先通过hash去找,如果找不到一样的hash就新建Entry,如果找到一样的判断key是否也相等,如果相等则覆盖value,如果不想等说明是key不相同但是hash相同,那么生成Entry赋值给父的next。本人的逻辑理解是这样的,但是对源码还是看不懂。
1. ,put方法中

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        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;
                }
            }

这段逻辑不是很懂。

2.get方法中

if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

这一段不是很理解,求解释。越详细越好。在写笔记看到这里突然卡住了,求支招。哈哈哈。

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • 私奔Sven 2018-01-30 03:26
    已采纳
    1. if ((tab = table) == null || (n = tab.length) == 0)
      1. n = (tab = resize()).length;
      2. if ((p = tab[i = (n - 1) & hash]) == null)
      3. tab[i] = newNode(hash, key, value, null);
      4. else {
      5. Node e; K k;
      6. if (p.hash == hash &&
      7. ((k = p.key) == key || (key != null && key.equals(k))))
      8. e = p;
      9. else if (p instanceof TreeNode)
      10. e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
      11. else {
      12. for (int binCount = 0; ; ++binCount) {
      13. if ((e = p.next) == null) {
      14. p.next = newNode(hash, key, value, null);
      15. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      16. treeifyBin(tab, hash);
      17. break;
      18. }
      19. if (e.hash == hash &&
      20. ((k = e.key) == key || (key != null && key.equals(k))))
      21. break;
      22. p = e;
      23. }
      24. } 解读这一段源码:
    2. java1.8中,map的结构是由Node[] + 链表组成的,和之前的主要区别是,链表部分,当超过8个元素会转成TreeNode对象,由TreeBin封装,也就是链表转换为树形结构便于存储和查找。不是线程安全类,但是如果多线程操作会报出ConCurrentxxxException。

    下面按行数来说:
    1. 如果当前Node[] 为null 或者 Node数组元素个数为0 执行下面一行代码(省略大括号)
    2. resize() 方法返回一个扩容后的Node[],扩容的机制为所需容量的两倍,是原有的1.5倍,这个计算是由负载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; 来决定的(具体的可以看一下resize()方法,如果有困难我们再讨论一次)。 Node数组元素个数n 赋值为扩容后的长度。
    4. 「 (n - 1) & hash] 」定位数组下标位置的经典算法,你可以自己写一个main方法来做几个实验。n=16的话,计算结果肯定在0~15之间。p为计算后取到的一个Node节点 判断是否为null (if else 省略大括号)
    5. 如果上述判断为true,那么当前节点赋值为一个新建节点 newNode(x,x,x,x); 这个不用说吧。也是一个经典数据结构。
    6. 如果4 中判断结果为false,证明当前下标为i的位置存在节点,那么进行下列操作。
    7、8、9. 如果当前node节点的hash 和 节点中key属性值 双等或值等(也就是进行新旧值替换),则将当前节点赋值给e。
    10、11. 如果当前节点为TreeNode节点,则将当前操作元素添加到TreeNode[]中(图中,单独的hash,key,value都是当前操作元素的值)。
    12. 如果上述都不成立,直接执行下列代码(到这步的意思是,不会是覆盖操作,当前节点也不是treeNode,只能是将当前节点拼接在列表末端)。
    13-23. 这是一个看似无限循环的算法,这有几个退出点,按顺序来,第一个break,代表找到了列表末端,把当前元素添加到末端即可。第二个break,是找到新旧值覆盖的元素,进行替换。

    14行为常规列表遍历。
    15行为如果找到最后一个元素了,直接新建元素,将最后一个元素与新元素逻辑关联。
    16行 判断当前个数,是否大于或者等于7,如果是,则将列表转化为TreeBin包装类,其实列表转树的界限是8,但是数组下标是从0开始,所以是TREEIFY_THRESHOLD - 1。
    17行就是转化方法了。

    用有道笔记纯手打!

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • StackTc 2018-01-29 17:40

    还有问下,为什么别人的博客里面写的源码,跟我本地看的不一样,它的简单,我的好复杂。

    评论
    解决 无用
    打赏 举报
  • StackTc 2018-01-30 01:27

    还有哈希表 为什么比数据查找速度快

    评论
    解决 无用
    打赏 举报
  • yizishou 2018-01-30 11:01

    首先你要知道HashMap最基本的原理,就是把要存储的所有键做Hash,映射到一个数组中去。

    但是有可能两个甚至更多的键映射到了同一个位置,因此HashMap需要解决的最核心的问题就来了,就是“哈希冲突”。

    jdk7及以前的做法比较简单,如果出现哈希冲突,就在出现冲突的数组位置上创建一个链表,存储所有冲突的对象。这样的问题是,如果冲突的对象很多,那么这个链表会很长,会导致HashMap的性能大大下降。

    因此在jdk8发布的时候做了一个优化,在冲突较少的时候依然使用链表,冲突较多的时候,就把链表转换成一棵红黑树。

    这也就是你在看代码的时候看到的Node(链表节点)和TreeNode(红黑树节点)。

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题