键值之道:深入学习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

目录
打赏
0
0
0
0
36
分享
相关文章
|
1月前
|
Java之HashMap详解
本文介绍了Java中HashMap的源码实现(基于JDK 1.8)。HashMap是基于哈希表的Map接口实现,允许空值和空键,不同步且线程不安全。文章详细解析了HashMap的数据结构、主要方法(如初始化、put、get、resize等)的实现,以及树化和反树化的机制。此外,还对比了JDK 7和JDK 8中HashMap的主要差异,并提供了使用HashMap时的一些注意事项。
Java之HashMap详解
|
2月前
|
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
50 1
Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
【10月更文挑战第17天】Java Map新玩法:探索HashMap和TreeMap的高级特性,让你的代码更强大!
78 2
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
72 2
|
2月前
|
Java学习十六—掌握注解:让编程更简单
Java 注解(Annotation)是一种特殊的语法结构,可以在代码中嵌入元数据。它们不直接影响代码的运行,但可以通过工具和框架提供额外的信息,帮助在编译、部署或运行时进行处理。
97 43
Java学习十六—掌握注解:让编程更简单
14天Java基础学习——第1天:Java入门和环境搭建
本文介绍了Java的基础知识,包括Java的简介、历史和应用领域。详细讲解了如何安装JDK并配置环境变量,以及如何使用IntelliJ IDEA创建和运行Java项目。通过示例代码“HelloWorld.java”,展示了从编写到运行的全过程。适合初学者快速入门Java编程。
Java毕设学习 基于SpringBoot + Vue 的医院管理系统 持续给大家寻找Java毕设学习项目(附源码)
基于SpringBoot + Vue的医院管理系统,涵盖医院、患者、挂号、药物、检查、病床、排班管理和数据分析等功能。开发工具为IDEA和HBuilder X,环境需配置jdk8、Node.js14、MySQL8。文末提供源码下载链接。
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
66 5
|
2月前
|
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
68 3
在Java的Map家族中,HashMap和TreeMap各具特色
【10月更文挑战第19天】在Java的Map家族中,HashMap和TreeMap各具特色。HashMap基于哈希表实现,提供O(1)时间复杂度的高效操作,适合性能要求高的场景;TreeMap基于红黑树,提供O(log n)时间复杂度的有序操作,适合需要排序和范围查询的场景。两者在不同需求下各有优势,选择时需根据具体应用场景权衡。
36 2
AI助理

阿里云 AI 助理已上线!

快来体验一下吧。