HashMap原理

时间：2024-03-12 14:30:24

1. HashMap 的底层结构

  • Java7 : 数组 + 链表
  • Java8: 数组 + 链表 + 红黑树 (链表超过8则转为红黑树，小于6则变会链表) >> 加快查询.

2.HashMap参数

源码如下：

 

 

 参数解释：

　　DEFAULT_INITIAL_CAPACITY : 默认初始容量（16）， 必须是2的幂。（ 1 >> 4 也就是转化为 2进制后 0000 0001 左移4位 也就是 0001 0000， 也就是16）
　　DEFAULT_LOAD_FACTOR： 默认负载因子0.75，（超过 容量与负载因子的乘积会扩容）
　　TREEIFY_THRESHOLD : 大小为8及以上时链表会转化为红黑树 的阈值。
　　UNTREEIFY_THRESHOLD ： 大小为6及以下会转化为 链表 的阀值。


Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？

　　根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换为红黑树，小于等于6的时候就化为链表。

3. put()的实现

　　put函数大致的思路为：

　　1）对key的hashCode()做hash，然后再计算index;
　　2）如果没碰撞直接放到 tab[i]里；
　　3）如果碰撞了，以链表的形式存储， （结合第一章节的图， 化学与数学的hash冲撞后， 转为链表存在数学的下一个节点处。）；
　　4）如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
　　5）如果节点已经存在就替换old value(保证key的唯一性)
　　6）当容量将超过 负载因子与初始容量的乘积 （load factor*current capacity)，就要resize。

代码实现如下：

public V put(K key, V value) {
    // 对key的hashCode()做hash
    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;
    // tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算index，并对null做处理,
    if ((p = tab[i = (n - 1) & hash]) == null)
        //直接构造一个Node 存进 tab 以 hash运算后的为下标 里。
        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;
    // 超过load factor*current capacity，resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
put()实现

4. get()函数实现

在理解了put之后，get就很简单了。大致思路如下：
　　整个HashMap 称之为bucket （桶）

　　bucket里的第一个节点，直接命中；
　　如果有冲突，则通过key.equals(k)去查找对应的entry
　　若为树，则在树中通过key.equals(k)查找，O(logn)；
　　若为链表，则在链表中通过key.equals(k)查找，O(n)。
具体代码的实现如下：

 1 public V get(Object key) {
 2     Node<K,V> e;
 3     return (e = getNode(hash(key), key)) == null ? null : e.value;
 4 }
 5 
 6 final Node<K,V> getNode(int hash, Object key) {
 7     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
 8     if ((tab = table) != null && (n = tab.length) > 0 &&
 9         (first = tab[(n - 1) & hash]) != null) {
10         // 直接命中
11         if (first.hash == hash && // always check first node
12             ((k = first.key) == key || (key != null && key.equals(k))))
13             return first;
14         // 未命中
15         if ((e = first.next) != null) {
16             // 在树中 getTreeNode() 不做深究
17             if (first instanceof TreeNode)
18                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
19             // 在链表中 通过.next() 循环获取，知道找到满足条件的key为止
20             do {
21                 if (e.hash == hash &&
22                     ((k = e.key) == key || (key != null && key.equals(k))))
23                     return e;
24             } while ((e = e.next) != null);
25         }
26     }
27     return null;
28 }
get()代码实现

5. hash() 的实现

在对hashCode()计算hash时具体实现是这样的：

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

在get和put的过程中，计算下标时，先对hashCode进行hash操作，然后再通过hash值进一步计算下标，如下图所示：

 6.RESIZE的实现

当put时，如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例，那么就会发生resize。在resize的过程，简单的说就是把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中。resize的注释是这样描述的：

Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.

大致意思就是说，当超过限制的时候会resize，然而又因为我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

7.总结

我们现在可以回答开始的几个问题，加深对HashMap的理解：

1） 什么时候会使用HashMap？他有什么特点？
是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。

2） 你知道HashMap的工作原理吗？
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

3） 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

4） 你知道hash的实现吗？为什么要这样实现？
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

5） 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。

关于Java集合的小抄中是这样描述的：

 

 

 

 

以上部分参考：https://blog.csdn.net/weixin_41272626/article/details/107629037

 

相关文章