方圆

JCF-HashMap-and-HashSet

2019-09-29

1. Hash Concepts

哈希表的本质是一个数组,数组中每一个元素称为一个箱子(bin),箱子中存放的是键值对。

  • 存储过程

    1. 根据Key计算出它的哈希值h;
    2. 假设箱子的个数为n,这个键值应该放在第(h%n)个箱子里;
    3. 如果该箱子中已经有了键值对,使用开放寻址法(Open hash)或者拉链法(closed hash)解决冲突。
  • 拉链法
    每个箱子是一个链表,属于同一个箱子的所有键值对都会排在链表中。

  • 负载因子
    负载因子=总键值对数/箱子个数,负载因子越大,哈希表越满,越容易导致冲突,性能越低。因此当负载因子超过某个阈值(eg. 0.75)时就需要对哈希表进行扩容。

  • 哈希表扩容&rehash
    哈希表自动扩容时,一般会创建两倍于原来个数的箱子,因此即使key的哈希值h不变,对箱子个数取余(h%n) 也会发生改变,这个过程也成为重哈希(rehash)。
    哈希表扩容表面上可以降低负载因子,但可能也无法解决链表过长的问题。假设所有key的哈希值h都一样,即使扩容以后它们也分布在同一个bin的链表上,因此也不能提高性能。

  • 可能的缺陷

    1. 如果hash表中本来箱子比较多,扩容时要重新hash并移动数据,性能影响较大。
    2. 如果hash函数设计不合理,hash表在极端情况下会退化成线性表,性能极低。

2.HashMap

hashMap.png

  • Important Variables

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 初始容量16个bin,太少,容易触发扩容;太多,遍历hash表会比较慢
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // hash 表最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认负载因子,这种情况键值对数量>16*0.75=12时就会触发扩容。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当某个bin中链表长度大于8时,就转化为树
    static final int TREEIFY_THRESHOLD = 8;
    // 在hash表扩容时,如果发现链表长度小于6则会将树退化回链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 在转变成树之前,还会判断,只有键值对数量>64才会发生转换
    static final int MIN_TREEIFY_CAPACITY = 64;
    transient Node<K,V>[] table;
    transient Set<Map.Entry<K,V>> entrySet;
    transient int size;
    int threshold;
    final float loadFactor;

    上文说过,如果hash函数不合理,几是扩容也可能无法减少箱子中链表的长度,Java的处理方案是当链表太长时,转换成红黑树。转换还有一个条件是:键值对数量大于 MIN_TREEIFY_CAPACITY。这是为了避免在hash表建立初期,多个键值对七号被放入了同一个链表中,而导致不必要的转化。

    8是如何确定的: (Time-Space Trade-off)TreeNodes占用空间是普通Nodes的两倍,所以只有当bin包含足够多的节点时才会转成TreeNodes,而是否足够多就是由TREEIFY_THRESHOLD的值决定的。当bin中节点数变少时,又会转成普通的bin。当hashCode离散性很好的时候,数据均匀分布在每个bin中,几乎不会有bin中链表长度会达到阈值,树型bin用到的概率非常小。

    理想情况下,随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布,$P(k)=\frac{\lambda^k e^{-\lambda}}{k!}$ 我们可以看到,一个bin中链表长度达到8个元素的概率为0.00000006,几乎是不可能事件。

    默认resizing threshold 0.75,得到 $\lambda=0.5$ (????),尽管由于调整大小粒度而差异很大。 忽略方差,列表大小k的预期出现次数是(exp(-0.5)* pow(0.5,k)/ factorial(k))。

数量 0 1 2 3 4 5 6 7 8
概率 0.60653066 0.30326533 0.07581633 0.01263606 0.00157952 0.00015795 0.00001316 0.00000094 0.00000006
    然而JDK不能阻止用户实现不好的hash算法,只能使用红黑树做应急处理。
  • Main Methods

    • get()
      get() 首先调用hash(key)得到hash值,然后利用getNode方法获取node,然后返回node.value。算法思想是首先通过hash()函数得到对应bin的下标,然后依次遍历冲突链表,通过key.equals(k)方法来判断是否是要找的那个bin

      hash(key)&(table.length-1) = hash(key)%table.length 因为table.length 始终时2的幂,因此table.length-1二进制低位全是1,与hash(key)相与就会将hash值的高位抹掉,剩下的就是余数。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
         final Node<K,V> getNode(int hash, Object key) {
      Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      // 根据hash得到对应的bin
      if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
      // bin的链表的第一个元素是否符合
      if (first.hash == hash && ((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;
      }
    • put()
      将key和value放入到map,通过调用putVal实现。找到对应的链表之后插入,这里jdk1.8是加入到链表末尾,之前的版本网上说是在链表头部插入。(尚未验证????)

      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
      final 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;
      // map中不存在当前元组,可直接插入
      if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);
      else {// 冲突的时候
      Node<K,V> e; K k;
      // bin的第一个节点p完全equal插入的元组
      if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
      // 该bin已经是红黑树,只能继续加入
      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) // 长度过长时变为红黑树
      treeifyBin(tab, hash);
      break;
      }
      // 当前bin的链表中存在与插入元组完全equal的情况
      if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
      break;
      p = e;
      }
      }
      if (e != null) { // 存在与插入元组完全equal
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null) // 默认替换原来的value,onlyIfAbsent 是控制参数
      e.value = value;
      // 回调接口
      afterNodeAccess(e);
      return oldValue;
      }
      }
      ++modCount;
      if (++size > threshold) // 重新hash
      resize();
      // 回调接口
      afterNodeInsertion(evict);
      return null;
      }
    • remove()
      remove(Object key)根据key删除对应的元组,这里调用 removeNode()实现

      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
        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;
      // 当前bin的第一个元组p就符合
      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);
      }
      }
      // 获取的node不为空并且(不用匹配值、值完全相等、值equal)
      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) // node是当前bin的第一个节点
      tab[index] = node.next;
      else // 是否存在问题??p和node中间有节点的情况
      p.next = node.next;
      ++modCount;
      --size;
      // 回调函数
      afterNodeRemoval(node);
      return node;
      }
      }
      return null;
      }

HashSet

HashSet里面有一个HashMap(适配器模式),所有方法都是转发到HashMap实现。

1
2
3
4
5
// 虚拟值
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

Summary

  • 对于迭代比较频繁的场景,不宜将HashMap的初始大小设的过大。
    如上图所示,选择合适的哈希函数,put()get()方法可以在常数时间内完成。但在对HashMap进行迭代时,需要遍历整个table以及后面跟的冲突链表。
  • 对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。
    有两个参数可以影响HashMap的性能:初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当bin的数量超过capacity*load_factor时,容器将自动扩容并重新哈希。
  • 要将自定义的对象放入到HashMapHashSet中,需要@Override hashCode()equals()方法。
    将对象放入到HashMapHashSet中时,有两个方法需要注意:hashCode()equals()hashCode()方法决定了对象会被放到哪个bin里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章