HashMap浅谈-基本方法

HashMap的初始化过程

HashMap的初始化有两种方法:

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

    /**
         * 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. 传入容量参数的有参构造方法,此时的初始化容量需要进行计算

/**
 * 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的幂次方的值,具体方法可以参考:

/**
 * 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、复制原有数组的数据,该转化为链表的转化为链表,该转化为红黑树的转化为红黑树

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

      /**
         * 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值的桶中

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

    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对每个对象来说都是唯一的, 可以查看下面的例子

    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()方法

    @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的时候,会转化红黑树,因为红黑树的查询效率是非常高的,但是占用空间会比链表大,典型的使用空间换时间,但是换的物超所值

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

    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算法获取的值来快速定位到索引,然后返回对应的索引对应值。

/**
   * 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方法
```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有时间的还可以深入了解一下。