当前位置:   article > 正文

HashMap(一)——HashMap put方法原理_hashmap lut

hashmap lut

1.HashMap重要成员

部分成员变量如下:
//初始值,为16,必须为2的次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;    
//当容量被占满0.75时就需要reSize扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表长度到8,就转为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 树大小为6,就转回链表
static final int UNTREEIFY_THRESHOLD = 6;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

HashMap类中有一个非常重要的字段,就是Node[] table,即哈希桶数组

transient Node<K,V>[] table;
  • 1

Node是HashMap的一个内部类,实现了Map.Entry接口,本质就是一个映射(键值对) ,起源代码如下:

static class Node&lt;K,V> implements Map.Entry&lt;K,V> {
    final int hash;
    final K key;
    V value;
    Node&lt;K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

2.HashMap的put方法

JDK7中HashMap采用的是位桶+链表的方式,即我们常说的散列链表的方式,而JDK8中采用的是位桶+链表/红黑树,本文研究的是 JDK8中的put方法。
这里写图片描述

JDK1.8 put方法源码:

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

这里我们先关注下hash函数,在HashMap中其实现如下:

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

这里用到的方法很简单,就是把key与其高16位异或。文档中有如下说明:
There is a tradeoff between speed, utility, and quality of bit-spreading.
因为没有完美的哈希算法可以彻底避免碰撞,所以只能尽可能减少碰撞,在各方面权衡之后得到一个折中方案,这里我们就不再追究了。
put方法的具体实现在putVal中,我们看下其实现:

// 参数onlyIfAbsent表示是否替换原值
// 参数evict我们可以忽略它,它主要用来区别通过put添加还是创建时初始化数据的
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)
        // resize()不仅用来调整大小,还用来进行初始化配置
        n = (tab = resize()).length;
    // (n - 1) & hash这种方式也熟悉了吧?都在分析ArrayDeque中有体现
    //这里就是看下在hash位置有没有元素,实际位置是hash % (length-1)
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 将元素直接插进去
        tab[i] = newNode(hash, key, value, null);
    else {
        //这时就需要链表或红黑树了
        // e是用来查看是不是待插入的元素已经有了,有就替换
        Node<K,V> e; K k;
        // p是存储在当前位置的元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; //要插入的元素就是p,这说明目的是修改值
        // 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);
                    // 链表比较长,需要树化,
                    // 由于初始即为p.next,所以当插入第8个元素才会树化
                    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;
            }
        }
        // e就是被替换出来的元素,这时候就是修改元素值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 默认为空实现,允许我们修改完成后做一些操作
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // size太大,达到了capacity的0.75,需要扩容
    if (++size > threshold)
        resize();
    // 默认也是空实现,允许我们插入完成后做一些操作
    afterNodeInsertion(evict);
    return null;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

总结:

HashMap在put方法中,它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候,HashMap使用Key hashCode()和哈希算法来找出存储key-value对的索引。如果索引处为空,则直接插入到对应的数组中,否则,判断是否是红黑树,若是,则红黑树插入,否则遍历链表,若长度不小于8,则将链表转为红黑树,转成功之后 再插入。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/835545
推荐阅读
相关标签
  

闽ICP备14008679号