键值之道:深入学习Java中强大的HashMap(二)

简介: 键值之道:深入学习Java中强大的HashMap

键值之道:深入学习Java中强大的HashMap(一)https://developer.aliyun.com/article/1480891


接下来我们再来看看核心的方法 putVal:

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)
    // 第一次新增元素的时候进行扩容到默认 16
    n = (tab = resize()).length;
  // 计算索引下标查询对应下标下的数据
  if ((p = tab[i = (n - 1) & hash]) == null)
    // 未发生碰撞那么直接创建新节点放入指定下标位置
    tab[i] = newNode(hash, key, value, null);
  else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      // 存在相同的 key:内存地址相等或者 equals 方法为true
      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);
          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;
      }
    }
    if (e != null) { // existing mapping for key
      // hash值一样,key也一样那么直接进行替换
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

大概逻辑如下:

  1. 先通过 hash 值计算出 key 映射到哪个桶
  2. 如果桶上没有碰撞冲突,则直接插入
  3. 如果出现碰撞冲突了,则需要处理冲突
  1. 如果该桶使用红黑树处理冲突,则调用红黑树的方法插入数据
  2. 否则采用传统的链式方法插入。如果链的长度达到临界值,则把链转变为红黑树
  1. 如果桶中存在重复的键,则为该键替换新值 value
  2. 如果 size 大于阈值 threshold,则进行扩容

扩容 resize

  • capacity 即容量,默认16。
  • loadFactor 加载因子,默认是0.75
  • threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

一般情况下,当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。HashMap的容量是有上限的,必须小于 1<<30。

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;
    }
    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 {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    // 计算新的临界值
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) {
    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) {
    // ...复制老数组中的元素到新数组,遍历所有的元素进行 rehash,非常耗时间,所以尽量少的出现扩容操作
  }
  return newTab;
}

JDK8 因为巧妙的设计,性能有了大大的提升,由于数组的容量是以 2 的幂次方扩容的,那么在扩容时,新的位置要么在原位置,要么在原长度+原位置的位置。

数组长度变为原来的 2 倍,表现在二进制上就是多了一个高位参与数组下标确定。此时,一个元素通过 hash 转换坐标的方法计算后,恰好出现一个现象:最高位是 0 则坐标不变,最高位是 1 则坐标变为“10000+原坐标”,即“原长度+原坐标”。因此,在扩容时,不需要重新计算元素的 hash 了,只需要判断最高位是 1 还是 0 就好了。

如果我们确切的知道我们有多少键值对需要存储,那么我们在初始化 HashMap 的时候就应该指定它的容量,以防止 HashMap 自动扩容,影响使用效率。

当我们明确知道 HashMap 中元素的个数的时候,把默认容量设置成 initialCapacity/ 0.75F + 1.0F 是一个在性能上相对好的选择,但是,同时也会牺牲些内存。

比如如果我们要存入100个数据,那么将容量可以设置成 100/0.75+1 约等 135。

删除 remove

public V remove(Object key) {
  Node<K,V> e;
  return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

remove 方式实际将删除逻辑转交 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;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      // 直接根据 key 匹配到目标节点
      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;
}

删除方法就是首先先找到元素的位置,如果是链表就遍历链表找到元素之后删除。如果是用红黑树就遍历树然后找到之后做删除,树小于 6 的时候要转回链表。

查找 get

public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}

调用 get 查找方法,通过元素的 key 找到 value,get 方法实际上将查找逻辑转交 getNode 方法处理。

final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  // 如果哈希表不为空并且 key 对应的桶上不为空
  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;
}

调用红黑树的查找使用的是 getTreeNode 的 find 方法。

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
  TreeNode<K,V> p = this;
  do {
    int ph, dir; K pk;
    TreeNode<K,V> pl = p.left, pr = p.right, q;
    if ((ph = p.hash) > h)
      p = pl;
    else if (ph < h)
      p = pr;
    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
      return p;
    else if (pl == null)
      p = pr;
    else if (pr == null)
      p = pl;
    else if ((kc != null ||
              (kc = comparableClassFor(k)) != null) &&
             (dir = compareComparables(kc, k, pk)) != 0)
      p = (dir < 0) ? pl : pr;
    else if ((q = pr.find(h, k, kc)) != null)
      return q;
    else
      p = pl;
  } while (p != null);
  return null;
}
  • 查找红黑树,由于之前添加时已经保证这个树是有序的了,因此查找时基本就是折半查找,效率更高
  • 这里和插入时一样,如果对比结点的哈希值和要查找的哈希值相等,就会判断key是否相等,相等就直接返回。不相等就从子树中递归查找

遍历 HashMap

分别遍历 Key 和 Value

for (String key : map.keySet()) {
  System.out.println(key);
}
for (Object vlaue : map.values() {
  System.out.println(value);
}

使用 Iterator 迭代器迭代(推荐)

Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
  Map.Entry<String, Object> entry = iterator.next();
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
}

通过 get 方式

Set<String> keySet = map.keySet();
for (String str : keySet) {
  System.out.println(str);
  System.out.println(map.get(str));
}

笔记大部分摘录自《Java核心技术卷I》,含有少数本人修改补充痕迹。

参考文章:http://985.so/b7m3vhttp://985.so/b023nhttp://985.so/b0xnv

相关文章
|
4天前
|
Java
【JAVA学习之路 | 进阶篇】Record(记录)与密封类(sealed)
【JAVA学习之路 | 进阶篇】Record(记录)与密封类(sealed)
|
4天前
|
Java
【JAVA学习之路 | 进阶篇】方法引用与构造器引用
【JAVA学习之路 | 进阶篇】方法引用与构造器引用
|
4天前
|
Java 编译器
【JAVA学习之路 | 进阶篇】Lambda表达式
【JAVA学习之路 | 进阶篇】Lambda表达式
|
4天前
|
存储 Java API
【JAVA学习之路 | 进阶篇】(处理流)转换流与对象流
【JAVA学习之路 | 进阶篇】(处理流)转换流与对象流
|
4天前
|
缓存 Java
【JAVA学习之路 | 进阶篇】节点流与缓冲流(处理流之一)
【JAVA学习之路 | 进阶篇】节点流与缓冲流(处理流之一)
|
1天前
|
Java 开发者
Java中的多线程编程:理解、实现与性能优化
【5月更文挑战第25天】 在Java中,多线程编程是实现并发执行任务的关键手段。本文将深入探讨Java多线程的核心概念,包括线程的创建、生命周期、同步机制以及高级特性。我们将通过实例演示如何有效地创建和管理线程,同时着重分析多线程环境下的性能调优策略和常见问题解决方法。文章旨在为读者提供一个全面的视角,帮助其掌握Java多线程编程的技巧,并在实际开发中避免潜在的并发问题,提升程序的性能和稳定性。
|
1天前
|
安全 Java 测试技术
Java并发编程:理解线程同步和锁
【5月更文挑战第25天】本文深入探讨了Java并发编程的核心概念,即线程同步和锁。通过详细解释这两种机制,我们能够理解它们如何帮助解决多线程环境中的竞态条件问题。此外,文章还提供了一些示例代码,以展示如何在Java中使用这些技术。
|
1天前
|
安全 Java
Java中的多线程编程:从理论到实践
【5月更文挑战第25天】本文将深入探讨Java中的多线程编程,从基础理论到实际应用,为读者提供全面的理解和实践指导。我们将首先介绍多线程的基本概念和重要性,然后详细解析Java中实现多线程的两种主要方式:继承Thread类和实现Runnable接口。接着,我们将探讨如何在多线程环境中处理共享资源,以及如何利用Java的并发工具来管理线程。最后,我们将通过一个实际的例子来演示如何在实际开发中使用多线程。
|
1天前
|
Java 调度
Java并发编程:深入理解线程池
【5月更文挑战第25天】在Java中,线程池是一种管理线程的高效方式,它可以提高系统性能并降低资源消耗。本文将深入探讨Java线程池的原理、使用及优化方法,帮助读者更好地理解和应用线程池技术。
|
1天前
|
Java 调度
Java中线程池的技术
Java中线程池的技术
9 3