当前位置：首页 » 《休闲阅读》 » 正文

Java集合源码剖析——基于JDK1.8中HashMap的实现原理_张起灵-小哥的博客

1 人参与  2022年02月14日 13:25  分类 : 《休闲阅读》  评论

点击全文阅读


文章目录：

1.HashMap源码注释翻译

2.HashMap中的属性

3.HashMap中的方法

3.1 构造方法

3.2 get方法

3.3 put方法

3.4 remove方法

3.5 hash方法

3.6 resize方法

3.7 size方法

3.8 isEmpty方法

3.9 clear方法

3.10 containsKey方法

3.11 containsValue方法

3.12 replace方法

3.13 关于遍历map集合的三个方法

4.传统HashMap的缺点——引入红黑树

1.HashMap源码注释翻译

* Hash table based implementation of the <tt>Map</tt> interface.  This
* implementation provides all of the optional map operations, and permits
* <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
* class is roughly equivalent to <tt>Hashtable</tt>, except that it is
* unsynchronized and permits nulls.)  This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.

翻译一下大概就是在说，这个哈希表是基于 Map 接口的实现的，它允许 null 值和null 键，它不是线程同步的，同时也不保证有序。

* <p>This implementation provides constant-time performance for the basic
* operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
* disperses the elements properly among the buckets.  Iteration over
* collection views requires time proportional to the "capacity" of the
* <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
* of key-value mappings).  Thus, it's very important not to set the initial
* capacity too high (or the load factor too low) if iteration performance is
* important.

再来看看这一段，讲的是 Map 的这种实现方式为 get（取）和 put（存）带来了比较好的性能。但是如果涉及到大量的遍历操作的话，就尽量不要把 capacity 设置得太高（或 load factor 设置得太低），否则会严重降低遍历的效率。

影响 HashMap 性能的两个重要参数：“initial capacity”（初始化容量）和”loadfactor“（负载因子）。简单来说，容量就是哈希表桶的个数，负载因子就是键值对个数与哈希表长度的一个比值，当比值超过负载因子之后，HashMap 就会进行 rehash操作来进行扩容。

  • HashMap集合底层结构是 数组 + 单向链表 + 红黑树。
  • HashMap集合中的key、value均可为 null，其中key是无序不可重复的。
  • HashMap集合的默认初始化容量是16，默认加载因子是 0.75，扩容之后是原容量的2倍。
  • 如果HashMap集合中某个桶中的结点数超过了8，则单向链表结点会被替换成红黑树结点；当桶中的结点数小于6时，会将树形结点转回单向链表结点。只有当哈希表中的元素数量超过64时，才会进行树形化（即转换成红黑树这种结构）。否则只是进行扩容。

HashMap 的大致结构如下图所示，其中哈希表是一个数组，我们经常把数组中的每一个节点称为一个桶，哈希表中的每个节点都用来存储一个键值对。在插入元素时，如果发生冲突（即多个键值对映射到同一个桶上）的话，就会通过链表的形式来解决冲突。因为一个桶上可能存在多个键值对，所以在查找的时候，会先通过 key 的哈希值先定位到桶，再遍历桶上的所有键值对，找出 key 相等的键值对，从而来获取 value。

2.HashMap中的属性

//默认的初始容量为 2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大的容量上限为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的加载因子为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//变成树型结构的临界值为 8
static final int TREEIFY_THRESHOLD = 8;

//恢复链式结构的临界值为 6
static final int UNTREEIFY_THRESHOLD = 6;

//当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突
static final int MIN_TREEIFY_CAPACITY = 64;

//哈希表
transient Node<K,V>[] table;

//哈希表中键值对的个数
transient int size;

//哈希表被修改的次数
transient int modCount;

//它是通过 capacity*load factor 计算出来的，当 size 到达这个值时，就会进行扩容操作
int threshold;

//负载因子，决定了HashMap集合的数据密度
//负载因子过大，发生碰撞的几率会越高
//负载因子过小，就越容易触发扩容，扩容自然也会影响性能
//按照其他语言的参考及研究经验，会考虑将负载因子设置为0.75，此时平均检索长度接近于常数
final float loadFactor;

下面是 Node 类的定义，它是 HashMap 中的一个静态内部类，哈希表中的每一个节点都是 Node 类型。我们可以看到 Node 类中有 4 个属性，其中除了 key 和
value 之外，还有 hash 和 next 两个属性。hash 是用来存储 key 的哈希值的，next 是在构建链表时用来指向后继节点的。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<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;
    }
}

3.HashMap中的方法

3.1 构造方法

关于HashMap源码中的构造方法，无非是在更改 初始化容量、加载因子这些参数。这里就不再多说了。（主要是后面的get、put方法）

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

3.2 get方法

get方法首先是创建了一个 Node 结点对象，然后其中调用了 getNode 方法，所以我们着重来看一下这个 getNode 方法。

这个 getNode() 方法首先：如果哈希表不为空 && key 对应的桶上不为空，然后根据哈希表元素个数与哈希值求模（ 使用的公式是 (n - 1) &hash ）得到 key 所在的桶的头结点，如果头结点恰好命中（是我们要get的那个key），则直接返回。如果头结点没有命中，则继续向后续结点进行判断，如果头节点恰好是红黑树节点TreeNode，就调用红黑树节点的 getTreeNode() 方法，否则就执行 do-while 遍历链表节点。

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;
    //如果哈希表不为空 && key 对应的桶上不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        //根据哈希表元素个数与哈希值求模（ 使用的公式是 (n - 1) &hash ）得到 key 所在的桶的头结点
        (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;
}

get方法实现原理叙述：假如我们调用原型是 map.get("a")，首先会调用 a 的 hash() 方法得到 a 所对应的哈希值，然后通过哈希算法 tab[(n-1) & hash] 转换成桶下标（数组下标），通过这个桶下标快速定位到当前桶结点上，如果比对成功（hashCode、equals都返回true），则返回这个桶结点，如果当前桶结点上什么都没有则返回null。如果当前桶结点没有直接命中，它下面还挂载了其他结点，则继续判断后续结点，为红黑树结构则转为红黑树的get方法获取结点；如果不是则为普通单向链表结构，此时拿着 a 和单向链表上的每一个结点进行 equals 方法比对（因为hashCode只有比对成功才会到当前桶结点下继续比对），有一个equals返回 true 则比对成功，返回对应的结点，比对不成功最终返回 null。

3.3 put方法

put 方法的具体实现是在 putVal 方法中，所以我们重点看下面的 putVal 方法。

第一个if判断，我们一看就知道：做的是哈希表是否为空的判断，如果为空，调用 resize 方法，这个方法作用就是新创建一个哈希表。

第二个if判断：如果要插入的键值对的key对应的哈希值与当前桶结点的哈希值比对为null（不冲突），则直接为这个key创建一个新结点newNode()插入就行了。

下面走到else：与第二个if相反，走到else则说明，要插入的键值对与当前桶结点发生冲突了。if是说如果桶上结点的key与我们要插入的key重复，直接确定插入的位置就是该结点（e = p）。else if是指采用红黑树方法则调用红黑树对应的方法进行插入。else表示不是红黑树，那只能是传统的单向链表结构，只有桶上结点在上面的if中比对不成功，才会走到这个else，它执行的就是将要插入的key与当前桶下挂载的结点一一进行比对，如果比对到链表末尾还没找到重复的key，则newNode创建新结点将要插入的key添加到链表末尾。如果链表长度超过临界值，则转为红黑树。else的最后如果找到了重复的key，就break跳出。

else下面的if：就是说明此时已经找到了（我们要插入的key与桶中某个结点的key相等），那么就将要插入key对应的value值覆盖掉原先的旧值，同时返回覆盖掉的那个旧值。

最后的if则是进行是否扩容的判断。

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;
        //如果桶上节点的 key 与当前 key 重复，那你就是我要找的节点了
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果是采用红黑树的方式处理冲突，则通过红黑树的 putTreeVal 方法去插入这个键值对
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //否则就是传统的单向链表结构
        else {
            for (int binCount = 0; ; ++binCount) {
                //到了链尾还没找到重复的 key，则说明 HashMap 没有包含该键
                if ((e = p.next) == null) {
                    //创建一个新节点插入到尾部
                    p.next = newNode(hash, key, value, null);
                    //如果链的长度大于 TREEIFY_THRESHOLD 这个临界值，则把链变为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //找到了重复的 key
                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;
}

 

put方法实现原理叙述：如果哈希表为null，则创建哈希表；通过计算哈希值确定要映射到哪个桶，如果要插入的key与当前桶没有冲突，则直接插入；如果要插入的key与当前桶上结点冲突，则处理碰撞冲突（如果是红黑树则采用红黑树方法进行插入；否则就是单向链表，对当前桶上结点一一遍历，如果最终都不冲突，则将该key插入到链表末尾；如果链表长度达到临界值，则转为红黑树）；如果桶中存在重复的键，则将该键的旧值替换为要插入的新值。最终判断size是否大于阈值，大于则执行扩容操作。

3.4 remove方法

remove 方法的具体实现在 removeNode 方法中，所以我们重点看下面的 removeNode 方法。

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

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //如果当前 key 映射到的桶不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //如果桶上的节点就是要找的 key，则直接命中
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        //查找当前桶下挂载的其他结点
        else if ((e = p.next) != null) {
            //如果是以红黑树处理冲突，则构建一个树节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            //如果是以链式的方式处理冲突，则通过遍历链表来寻找节点
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //比对找到的 key 的 value 跟要删除的是否匹配
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            //通过调用红黑树的方法来删除节点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //使用链表的操作来删除桶上节点
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

3.5 hash方法

在get 方法和put方法中都需要先计算 key映射到哪个桶上，然后才进行之后的操作，计算的主要代码如下：

(n - 1) & hash

上面代码中的 n 指的是哈希表的大小，hash 指的是 key 的哈希值，hash 是通过下面这个方法计算出来的，采用了二次哈希的方式，其中 key 的 hashCode 方法是一个 native 方法：

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

这个 hash 方法先通过 key 的 hashCode 方法获取一个哈希值，再拿这个哈希值与它的高 16 位的哈希值做一个异或操作来得到最后的哈希值，计算过程可以参考下图。

为啥要这样做呢？注释中是这样解释的：如果当 n 很小，假设为 64 的话，那么 n-1 即为 63（0x111111），这样的值跟 hashCode()直接做与操作，实际上只使用了哈希值的后 6 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

正是因为与的这个操作，决定了 HashMap 的大小只能是 2 的幂次方，想一想，如果不是2的幂次方，会发生什么事情？即使你在创建HashMap的时候指定了初始大小，HashMap 在构建的时候也会调用下面这个方法来调整大小：

这个方法的作用看起来可能不是很直观，它的实际作用就是把 cap 变成第一个大于等于 2 的幂次方的数。

例如，16 还是 16，13 就会调整为 16，17 就会调整为 32。

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;
}

3.6 resize方法

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap 什么时候进行扩容呢 ？

当HashMap中的元素个数超过数组大小（数组总大小length不是数组中个数 size）*loadFactor 时 ， 就 会 进 行 数 组 扩 容 ， loadFactor 的 默 认 值
(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

在这里有一个需要注意的地方，有些文章指出当哈希表的 桶占用超过阈值时就进行扩容，这是不对的；

实际上是当哈希表中的 键值对 个数超过阈值时，才进行扩容的。

3.7 size方法

返回map集合中键值对的个数。

public int size() {
    return size;
}

3.8 isEmpty方法

判断map集合是否为空。

public boolean isEmpty() {
    return size == 0;
}

3.9 clear方法

清空map集合，首先判断哈希表是否为空，为空的情况下，将size置为0，遍历哈希表依次清空每隔键值对。

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

3.10 containsKey方法

判断map集合中是否包含指定的key。内部实现是调用了getNode方法，这个在上面将get方法的时候已经说过了。

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

3.11 containsValue方法

判断map集合中是否包含指定的value。

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

3.12 replace方法

将map集合中指定key对应的旧值替换为一个新值。

public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

3.13 关于遍历map集合的三个方法

这三个方法分别是 keySet、entrySet、forEach，源码我这里就不再多说了，下面给出的是测试代码。

@Test
public void test1() {
    Map<String,Object> map = new HashMap<>();
    map.put("1001","张起灵");
    map.put("1002","小哥");
    map.put("1003","小宋");

    System.out.println("keySet方法遍历map集合: ");
    Set<String> stringSet = map.keySet();
    Iterator<String> iterator = stringSet.iterator();
    while (iterator.hasNext()) {
        String key = iterator.next();
        Object value = map.get(key);
        System.out.println("键: " + key + ", 值: " + value);
    }

    System.out.println("======================================");

    System.out.println("entrySet方法遍历map集合: ");
    Set<Map.Entry<String,Object>> entrySet = map.entrySet();
    Iterator<Map.Entry<String,Object>> entryIterator = entrySet.iterator();
    while (entryIterator.hasNext()) {
        Map.Entry<String, Object> entry = entryIterator.next();
        String key = entry.getKey();
        Object value = entry.getValue();
        System.out.println("键: " + key + ", 值: " + value);
    }

    System.out.println("======================================");

    System.out.println("forEach方法遍历map集合: ");
    map.forEach((key,value) -> System.out.println("键: " + key + ", 值: " + value));
}

4.传统HashMap的缺点——引入红黑树

(1)JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

(2)当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

(3)针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。

HashMap 是数组+ 链表+ 红黑树（JDK1.8 增加了红黑树部分）实现的。

关于红黑树的三个关键参数。


点击全文阅读


本文链接：http://zhangshiyu.com/post/34731.html

结点  方法  红黑  
<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 成陈叔达私生子？他却被李二罢相小说全集(陈清德陈叔达)无弹窗广告阅读
  • 许修文叶清霜全文最新章节正版小说免费阅读
  • 辞不达懿黎懿楚辞全本小说（辞不达懿）全章节小说目录阅读
  • 时以琛林若薇全集小说_若是月亮不会来完结版阅读
  • 齐竹青顾乘云小说最新章节-主角顾乘云齐竹青全文免费阅读
  • 问题解决：java.nio.charset.MalformedInputException: Input length = 1
  • c#解析抖音评论提取数据第一篇源码
  • 数据结构-8.Java. 七大排序算法(中篇)
  • C++ 文件操作-写入二进制文件/读取二进制文件
  • C++奇迹之旅：左右值&amp;&amp;左右值引用&amp;&amp;move应用（文末送书）
  • 【C++】深入理解 C++ 中的继承进阶：多继承、菱形继承及其解决方案
  • 【python】掌握 Flask：轻量级 Web 开发框架解析

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1