Slient Blog

HashMap面试

2018-04-10

重要参数

  • 容量(Capacity) bucket的大小，也就是数组的大小。
  • 负载因子（Load factor）bucket填满程度的最大比例。
  • modCount，修改或者删除的次数总数。
  • threshold，临界值，比 capacity * load factor 大的最小二进制值，一般来表示bucket容量；
  • 当bucket中的entries的数目大于 capacity * load factor 时候，需要调整bucket的大小为当前的2倍。

存储结构

put函数的基本实现：

  1. 对key的hashCode()做二次函数(),然后计算index；
  2. 如果没碰撞直接放到y方向数组里面(当前index位置上不存在数据)；
  3. 如果发生了碰撞，以链表的形式存放在以数组上的节点为根节点的x方向链表里面；
  4. 如果碰撞太多导致链表过长(大于默认大小 8 )，就把链表转化为红黑树；
  5. 如果节点存在的话就替换 valude(保证key的唯一性);
  6. 如果数组满了(超过了 load factor * current capacity)需要 resize；
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
65
66
67
68
69
70
71
public V put(K key, V value) {
       // 对key的hashCode()做hash
       return putVal(hash(key), key, value, false, true);
}
// h = k.hashCode 1111 1111 1111 1111 1111 0000 1110 1010
// h =            1111 1111 1111 1111 1111 0000 1110 1010
// h >>> 16       0000 0000 0000 0000 1111 1111 1111 1111
// hash=h^h>>>16  1111 1111 1111 1111 0000 1111 0001 0101
// 数组的长度n-1   0000 0000 0000 0000 0000 0000 0000 1111
// (n-1)&hash     0000 0000 0000 0000 0000 0000 0000 0101
// 结果 index     0101 = 5
static final int hash(Object key) {
    int h;
    //hashCode的高16位异或低16位
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断当前map是否为空，为空择创建长度为n的纵向数组
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            //通过取余运算计算当前节点的index，如果该节点位置上不存在数据，则根据<k,v>直接创建新节点放到当前位置（没有发生碰撞）
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
             //如果当前index已经有数据，继续判断（发生了碰撞）
            Node<K,V> e; K k;
            //当前key已经存在的情况，最终的结果是直接用newValude覆盖oldValue
            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);
                        //如果链表的长度大于默认值（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;
                }
            }
            //更新value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //操作数加1
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

get函数的实现

  1. 通过 key查找，如果不存在冲突，返回结果；
  2. 如果有冲突，则通过key.equals(k)去查找对应的entry

    若为树，则在树中通过key.equals(k)查找，O(logn)；

    若为链表，则在链表中通过key.equals(k)查找，O(n)。
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
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;
   }

Resize()函数的实现//扩容机制

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

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

eg:当我们从bucket容量从16扩展到32时候(0,1的变化可以认为是随机的)


再重新计算hash之后，因为n变成原来的2倍，n-1在高位多一个1，重新计算后的index

下面看看示意图

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
final Node<K,V>[] resize() {
       Node<K,V>[] oldTab = table;
       int oldCap = (oldTab == null) ? 0 : oldTab.length;
       int oldThr = threshold;
       int newCap, newThr = 0;
       if (oldCap > 0) {
           //如果超过了默认的最大值，不进行处理
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           }
           //没有超过的话就变成原来的2倍
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
               newThr = oldThr << 1; // double threshold
       }
       else if (oldThr > 0) // initial capacity was placed in threshold；之前没有进行初始化，进行初始化，用我们自己定义的大小
           newCap = oldThr;
       else { // 使用jdk默认的大小进行初始化
           newCap = DEFAULT_INITIAL_CAPACITY;
           newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
       if (newThr == 0) {//计算新的resize上线，因为table的容量发生了变化，不过有上面的步骤，很难执行这步
           float ft = (float)newCap * loadFactor;
           //判断是否越界
           newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                     (int)ft : Integer.MAX_VALUE);
       }
       //新的容量上限生成
       threshold = newThr;
       @SuppressWarnings({"rawtypes","unchecked"})
       //开始进行移动
           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;
                   //如果当前节点并且不是链表的头结点，红黑树的根节点
                   if (e.next == null)
                       newTab[e.hash & (newCap - 1)] = e;
                       // 重新映射时，需要对红黑树进行拆分
                   else if (e instanceof TreeNode)
                       ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                   else { // 链表移动
                       Node<K,V> loHead = null, loTail = null;
                       Node<K,V> hiHead = null, hiTail = null;
                       Node<K,V> next;
                       do {//遍历链表，并将链表节点按原顺序进行分组
                           next = e.next;
                           if ((e.hash & oldCap) == 0) {//不需要移动的节点
                               if (loTail == null)
                                   loHead = e;
                               else
                                   loTail.next = e;
                               loTail = e;
                           }
                           else {//需要移动的节点
                               if (hiTail == null)
                                   hiHead = e;
                               else
                                   hiTail.next = e;
                               hiTail = e;
                           }
                       } while ((e = next) != null);
                       //将分组后的链表映射到新桶中
                       //原索引放到bucket里
                       if (loTail != null) {
                           loTail.next = null;
                           newTab[j] = loHead;
                       }
                       //原索引+oldCap放到bucket里
                       if (hiTail != null) {
                           hiTail.next = null;
                           newTab[j + oldCap] = hiHead;
                       }
                   }
               }
           }
       }
       return newTab;
   }

备注：

  1. 在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。因此在Java 8中，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题；
  2. (n - 1) & hash,在设计hash函数时，因为目前的table长度n为2的幂，而计算下标的时候，是这样实现的(使用 & 位操作，而非 % 求余)设计者认为这方法很容易发生碰撞。为什么这么说呢？不妨思考一下，在n - 1为15(0x1111)时，其实散列真正生效的只是低4bit的有效位，当然容易碰撞了。因此，设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用 O(logn) 的tree去做了。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。
  3. 什么时候会使用HashMap？他有什么特点？是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。
  4. 你知道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)，则使用红黑树来替换链表，从而提高速度。
  5. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？通过对key的hashCode()进行hashing，并计算下标( (n-1) & hash )，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点
  6. 你知道hash的实现吗？为什么要这样实现？在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的： (h =k.hashCode()) ^ (h >>> 16) ，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。
  7. 如果HashMap的大小超过了负载因子( load factor )定义的容量，怎么办？如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法。
Tags: Java
← Java异常机制 Java装箱与拆箱 →
加
使用微信添加

若你觉得我的文章对你有帮助，请添加我为好友

扫描二维码，分享此文章