JCF-HashMap&HashSet

本贴最后更新于 1625 天前,其中的信息可能已经沧海桑田

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 表在极端情况下会退化成线性表,性能极低。

HashMap

hashMap.png

  • Important Variables

    // 初始容量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 值的高位抹掉,剩下的就是余数。

      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 是加入到链表末尾,之前的版本网上说是在链表头部插入。(尚未验证????)

      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() 实现

      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 实现。

// 虚拟值
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() 方法决定了这些对象是否是“同一个对象”。

Reference

  • JCF
    1 引用
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖 • 1 关注
  • Hash
    5 引用 • 10 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...