抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

HashMap浅谈-基本方法

JAVA

发布于：2020年6月24日

HashMap的初始化过程

HashMap的初始化有两种方法：

  1. 直接使用HashMap的无参构造方法，此时初始化的容量为：DEFAULT_LOAD_FACTOR 也就是16

    1
    2
    3
    4
    5
    6
    7
    /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

  2. 传入容量参数的有参构造方法，此时的初始化容量需要进行计算

1
2
3
4
5
6
7
8
9
10
/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

​ 上一文中提到，HashMap的容量必须为2的幂次方，但是不是所有的同学在创建Map的时候都会遵守这个规则，在这种情况下，HashMap也会对传入的参数进行校准，规则是将 参数值转换为最接近、且大于等于指定参数的 2 的 幂次方的值，它确保了HashMap不管是在初始化时，或者在扩容时，它的容量一直保持的是2的幂次方的值，具体方法可以参考：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

HashMap的基本方法及原理

put方法

put方法是HashMap的一个基本方法，它的算法也是非常的复杂的，涉及到了单个节点、链表节点、红黑树节点，容量达到阈值时的自动扩容等。

它的原理主要包括下面几个方面：

  • HashMap的扩容阈值，以及扩容过程

    扩容阈值 = 当前容量 * 扩容因子

    扩容基本上分为几步：

    1、创建一个为原来两倍大的数组

    2、复制原有数组的数据，该转化为链表的转化为链表，该转化为红黑树的转化为红黑树

  • 插入键值对时如何确定落在哪个桶中（它虽然是个数组，但不是纯粹的数组）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
      /**
         * Computes key.hashCode() and spreads (XORs) higher bits of hash
         * to lower.  Because the table uses power-of-two masking, sets of
         * hashes that vary only in bits above the current mask will
         * always collide. (Among known examples are sets of Float keys
         * holding consecutive whole numbers in small tables.)  So we
         * apply a transform that spreads the impact of higher bits
         * downward. There is a tradeoff between speed, utility, and
         * quality of bit-spreading. Because many common sets of hashes
         * are already reasonably distributed (so don't benefit from
         * spreading), and because we use trees to handle large sets of
         * collisions in bins, we just XOR some shifted bits in the
         * cheapest possible way to reduce systematic lossage, as well as
         * to incorporate impact of the highest bits that would otherwise
         * never be used in index calculations because of table bounds.
         */
    static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

    ​ HashMap在计算hash值时，会将 hashCode 做一次16位右位移，然后将右移的结果和 hashCode 做异或运算，减少Hash碰撞的次数，然后将获取的值存储到对应的hash值的桶中

  • 键值的唯一性的保证机制

    1
    2
    if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))

    ​ 在java.util.HashMap#putVal中存在这样一段代码，当key的hash值相同并且key的内存位置相同或者key的值相同时，可以确认是同一个key，此时会根据条件来判断是直接将原来的key对应的value替换还是做其他的操作，以此来保证键值的唯一性。

    ​ 此处也有一定的坑，因为有一个 == 当传入的键值为引用对象时，如果没有重写引用对象的hashCode()方法，会导致同样参数的对象被认为是不同的键值，因为如果不重写hashCode()方法时，那么它就继承的是Object的hashCode()方法，Object的hashCode方法获取到的hashCode对每个对象来说都是唯一的， 可以查看下面的例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    static class HashKey {
            /**
             * Id
             */
            private Integer id;
            /**
             * hashKey
             */
            private String hashKey;
        ...
        }    
    public static void main(String[] args) {
            Map<HashKey,String> map = new HashMap<>();
            HashKey a = new HashKey(1,"10086");
            HashKey b = new HashKey(1,"10086");
            map.put(a,"1");
            map.put(b,"1");
            System.out.println(JSON.toJSONString(map));
        }
        输出结果：{{"hashKey":"10086","id":1}:"1",{"hashKey":"10086","id":1}:"1"}

    所以，如果使用对象做键值对的键值的话，一定记得重写HashCode()方法

    1
    2
    3
    4
    5
    @Override
          public int hashCode() {
              return Objects.hash(id, hashKey);
          }
    		输出结果：{{"hashKey":"10086","id":1}:"1"}

  • 发生hash碰撞（不同的键值hash值相同）时的处理机制

    虽然在hash值的计算上都是在极力避免出现hash碰撞的情况，但是hash碰撞还是有可能会发生，那么当hash值相同但是键值不同的键值对该如何存放呢，分为两种情况：

    1、在当前的hash对应的bin下面会创建成一个长度不超过8的链表

    2、当链表长度大于等于8的时候，会转化红黑树，因为红黑树的查询效率是非常高的，但是占用空间会比链表大，典型的使用空间换时间，但是换的物超所值

  • 单节点拉链法的实现过程

    1
    2
    3
    4
    5
    6
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
            }

    ​ 代码中的next就是下一个节点，当最后一个节点next为null时，代表着这个链表结束了。

    值得注意的是在JDK7之前链表使用的是头插法（不是使用的Node),当两个线程在执行resize()方法的时候可能会产生环形链表，在调用get()方法会死循环，导致OOM

  • 链表转化为红黑树的方法过程

    ​ 当链表的长度达到8时，已经是一个相对比较长的结构了，这时候查询的效率会随着链表的数量增长而降低，此时为了追求性能最大化，就会将链表转化为红黑树，这时候会产生一个问题：红黑树既然查询效率足够的高，为什么不直接采用红黑树的结构而使用链表达到8时才转变呢？

    这个其实也是有原因的，在一定的范围内，用空间换取时间效率是可取的，当链表长度比较短时，转变成红黑树，空间结构变大了，但是此时查询效率并没有因此而提高，反而得不偿失了，所以当链表达到阈值时来使用红黑树是相对比较划算的一种方案。

get方法

​HashMap设计的最主要原因就是为了提高查询效率，get方法是使用的最频繁的一个方法之一，它主要就是靠hash算法获取的值来快速定位到索引，然后返回对应的索引对应值。

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
/**
   * Implements Map.get and related methods.
   *
   * @param hash hash for key
   * @param key the key
   * @return the node, or null if none
   */
  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;
  }

​ get方法主要包含以下几个过程

​ 1、获取key的hash计算参数

​ 2、查找对应索引位置

​ 3、如果是单节点Node直接返回Node,如果是链表Node在链表中获取Node节点，如果是红黑树节点，那么调用红黑树的查询方法快速找到Node并且返回

remove方法
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
```java
    /**
     * Implements Map.remove and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to match if matchValue, else ignored
     * @param matchValue if true only remove if value is equal
     * @param movable if false do not move other nodes while removing
     * @return the node, or null if none
     */
    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;
        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;
            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);
                }
            }
            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;
    }
```

remove()方法也是个比较特殊的方法，它的作用和put()是完全相反的，基本也分为以下几个过程：

1、如果是单节点Node，那么直接将对应的Node设置为Null

2、如果是链表Node，那么将该Node删除的同时，将它前一个Node的next替换为后一个Node，保证链表的连续性

3、如果是红黑树Node，那么就需要调用红黑树的删除节点方法进行删除了，此时如果红黑树的Node值为2-6个时，会调方法转化为链表结构的Node

总结

HashMap是一个数组，但它是一个特殊的数组，包含了多种结构单元：单节点Node、Node链表、红黑树，根据实际情况互相转化，因为它的特殊性，造就了它超高的查询效率，O(1) 级别的查询效率，直接根据对应索引的位置找到对象并返回

HashMap的容量也是有规律的，为了结构的稳定性以及保障索引的散列计算更加均匀，它的容量必须是2的幂次方，即使是没有传正确的容量参数，也是会进行校准的

HashMap的扩容是达到一定阈值后会进行两倍放大，创建一个新的数组，将原来对象进行复制，并且会对单节点类型的元素重新计算他们的索引位置，如果是红黑树的话，会根据红黑树特有的方法进行扩容，在红黑树与链表之间进行动态转化

HashMap和List、Set等集合一样，不是线程安全的，它在多线程情况是不具备线程安全特性的，如果同时有多个put或者多个remove会对它的数据造成比较大的影响，多线程环境下不推荐使用HashMap，它在多线程环境的替代是ConcurrentHashMap,关于ConcurrentHashMap有时间的还可以深入了解一下。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.songbo.fun/talking-about-hashmap-basic-methods.html

JAVA

次浏览

评论