0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299  十分钟深入理解HashMap源码
英语文化交流 > 技术博客 > 十分钟深入理解HashMap源码
十分钟深入理解HashMap源码
时间: 分类:技术博客

十分钟深入理解HashMap源码

十分钟就要深入理解HashMap源码,看完你能懂?我觉得得再多看一分钟,才能完全掌握!

十分钟深入理解HashMap源码

终于来到比较复杂的HashMap,由于内部的变量,内部类,方法都比较多,没法像ArrayList那样直接平铺开来说,因此准备从几个具体的角度来切入。

桶结构

HashMap的每个存储位置,又叫做一个桶,当一个Key&Value进入map的时候,依据它的hash值分配一个桶来存储。

看一下桶的定义:table就是所谓的桶结构,说白了就是一个节点数组。

transient Node<K,V>[] table;
transient int size;

节点

HashMap是一个map结构,它不同于Collection结构,不是存储单个对象,而是存储键值对。
因此内部最基本的存储单元是节点:Node。

节点的定义如下:

class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

可见节点除了存储key,vaue,hash三个值之外,还有一个next指针,这样一样,多个Node可以形成一个单向列表。这是解决hash冲突的一种方式,如果多个节点被分配到同一个桶,可以组成一个链表。

HashMap内部还有另一种节点类型,叫做TreeNode:

class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
 }

TreeNode是从Node继承的,它可以组成一棵红黑树。为什么还有这个东东呢?上面说过,如果节点的被哈希到同一个桶,那么可能导致链表特别长,这样一来访问效率就会急剧下降。 此时如果key是可比较的(实现了Comparable接口),HashMap就将这个链表转成一棵平衡二叉树,来挽回一些效率。在实际使用中,我们期望这种现象永远不要发生。

有了这个知识,就可以看看HashMap几个相关常量定义了:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
  • TREEIFY_THRESHOLD,当某个桶里面的节点数达到这个数量,链表可转换成树;
  • UNTREEIFY_THRESHOLD,当某个桶里面数低于这数量,树转换回链表;
  • MIN_TREEIFY_CAPACITY,如果桶数量低于这个数,那么优先扩充桶的数量,而不是将链表转换成树;

put方法:Key&Value

插入接口:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put方法调用了私有方法putVal,不过值得注意的是,key的hash值不是直接用的hashCode,最终的hash=(hashCode右移16)^ hashCode。

在将hash值映射为桶位置的时候,取的是hash值的低位部分,这样如果有一批key的仅高位部分不一致,就会聚集的同一个桶里面。(如果桶数量比较少,key是Float类型,且是连续的整数,就会出现这种case)。

执行插入的过程:

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;

        //代码段1
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);            
        else {
            Node<K,V> e; K k;
            //代码段2
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //代码段3    
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //代码段4
                for (int binCount = 0; ; ++binCount) {
                    //代码段4.1
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //代码段4.2
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //代码段5
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //代码段6
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
  • 最开始的一段处理桶数组还没有分配的情况;
  • 代码段1: i = (n - 1) & hash,计算hash对应的桶位置,因为n是2的冥次,这是一种高效的取模操作;如果这个位置是空的,那么直接创建Node放进去就OK了;否则这个冲突位置的节点记为P;
  • 代码段2:如果节点P的key和传入的key相等,那么说明新的value要放入一个现有节点里面,记为e;
  • 代码段3:如果节点P是一棵树,那么将key&value插入到这个棵树里面;
  • 代码段4:P是链表头,或是单独一个节点,两种情况,都可以通过扫描链表的方式来做;
    • 代码段4.1:如果链表到了尾部,插入一个新节点,同时如果有必要,将链表转成树;
    • 代码段4.2:如果链表中找到了相等的key,和代码段2一样处理;
  • 代码段5:将value存入节点e
  • 代码段6:如果size超过某个特定值,要调整桶的数量,关于resize的策略在下文会讲

remove方法

了解了put方法,remove方法就容易了,直接讲解私有方法removeNode吧。

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

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;

    //代码段1
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {

        //代码段2:
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;

        //代码段3:
        else if ((e = p.next) != null) {
            //代码段3.1:
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                //代码段3.2:
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }

        //代码段4:
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {                 
            //代码段4.1:
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //代码段4.2:
            else if (node == p)
                tab[index] = node.next;
            //代码段4.3:
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}
  • 代码段1:这个if条件在判断hash对应的桶是否空的,如果是话,那么map里面肯定就没有这个key;否则第一个节点记为P;
  • 代码段2:如果P节点的key与参数key相等,找到了要移除的节点,记为node;
  • 代码段3:扫描桶里面的其他节点
    • 代码段3.1:如果桶里面这是一颗树,执行树的查找逻辑;
    • 代码段3.2: 执行链表扫描逻辑;
  • 代码段4:如果找到了node,那么尝试删除它
    • 代码段4.1:如果是树节点,执行树的节点删除逻辑;
    • 代码段4.2:node是链表头结点,将node.next放入桶就ok;
    • 代码段4.3:删除链表中间节点

rehash

rehash就是重新分配桶,并将原有的节点重新hash到新的桶位置。

先看两个和桶的数量相关的成员变量

final float loadFactor;
int threshold;
  • loadFactor 负载因子,是创建HashMap时设定的一个值,即map所包含的条目数量与桶数量的比值上限;一旦map的负载达到这个值,就需要扩展桶的数量;
  • threshold map的数量达到这个值,就需要扩展桶,它的值基本上等于桶的容量*loadFactor,我感觉就是一个缓存值,加快相关的操作,不用每次都去计算;

桶的扩展策略,见下面的函数,如果需要的容量是cap,真实扩展的容量是大于cap的一个2的冥次。
这样依赖,每次扩展,增加的容量都是2的倍数。

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

这是具体的扩展逻辑

Node<K,V>[] resize() {

     //此处省略了计算newCap的逻辑

    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;

                //分支1
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //分支2
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //分支3
                else { // preserve order
                    //此处省略了链表拆分逻辑   
                }
        }
    }
    return newTab;
}
  • 首先分配新的桶数组;
  • 扫描旧的桶,将元素迁移过来;
  • 分支1:桶里面只有一个新的节点,那么放入到新桶对应的位置即可;
  • 分支2:桶里面是一棵树,执行树的拆分逻辑
  • 分支3:桶里面是一个链表,执行链表的拆分逻辑;

由于新桶的数量是旧桶的2的倍数,所以每个旧桶都能对应2个或更多的新桶,互不干扰。 所以上面的迁移逻辑,并不需要检查新桶里面是否有节点。

可见,rehash的代价是很大的,最好在初始化的时候,能够设定一个合适的容量,避免rehash。

最后,虽然上面的代码没有体现,在HashMap的生命周期内,桶的数量只会增加,不会减少。

迭代器

所有迭代器的核心就是这个HashIterator

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
}

简单起见,只保留了next部分的代码。原理很简单,next指向下一个节点,肯定处在某个桶当中(桶的位置是index)。那么如果同一个桶还有其他节点,那么一定可以顺着next.next来找到,无论这是一个链表还是一棵树。否则扫描下一个桶。

有了上面的节点迭代器,其他用户可见的迭代器都是通过它来实现的。

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

视图

KeySet的部分代码:这并不是一个独立的Set,而是一个视图,它的接口内部访问的都是HashMap的数据。

final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
}

EntrySet、Values和KeySet也是类似的,不再赘述。

要点总结

1、key&value存储在节点中;
2、节点有可能是链表节点,也有可能是树节点;
3、依据key哈希值给节点分配桶;
4、如果桶里面有多个节点,那么要么形成一个链表,要么形成一颗树;
5、装载因子限制的了节点和桶的数量比例,必要时会扩展桶的数量;
6、桶数量必然是2的冥次,重新分配桶的过程叫做rehash,这是很昂贵的操作;

写在最后

十分钟深入理解HashMap源码

随机阅读

Copyright © 2017 英语文化交流 All Rights Reserved.