HashMap的工作原理

By | 2022年3月2日

简述Map和HashMap数据结构

Map 是一种基于键值的数据结构,我们可以使用指定的键来存储值。 我们可以稍后使用指定的键检索该值。

map 是 Java 中的一个接口,这个接口有很多实现,比如 HashMap、LinkedHashMap、TreeMap 等。

强烈建议在深入了解 HashMap 的内部工作之前,您应该通过 Java 中的 Map 接口。

HashMap 是一种基于键值对的数据结构。 它是 Java 的核心功能之一,开发人员和程序员每天都使用它来实现特定类型的功能。

HashMap 的主要用途之一是更快地访问数据。 此外,重要的是要知道 Map 不是集合框架的一部分。

为了更好地理解 HashMap 如何在内部工作,了解 hashCode() 和 equals() 方法的工作非常重要。 以下部分帮助您理解 hashCode() 方法。

hashCode

对于每个对象,JVM 都会生成一个唯一的编号,就是对象的 hashCode。 JVM 将使用 hashCode,同时将对象保存到与哈希相关的数据结构中,如 HashMap、HashSet 和 HashTables 等。

基本上,hashCode 用于对象的唯一标识,如果根据 hashCode 存储对象,那么搜索将变得非常有效。

equals

equals() 方法用于检查两个对象的等价性。 如果我们的类不包含 .equals() 方法,则将执行对象类 .equals() 方法,这始终用于引用比较(地址比较),即如果两个引用指向同一个对象,则equals() 方法返回真。

hashCode和equals的关系

现在知道了 hashCode 和 equals 方法的工作原理,那么这两种方法如何相互关联以及这两者之间的联系是什么的下一个重要概念。

  • 如果两个对象通过 .equals 方法相等,则它们的 hashCode 必须相等。
  • 如果两个对象通过 .equal() 方法不相等,则hashCode() 它们可以相等或不等。
  • 如果 2 个对象的 hashCode 不相等,那么这些对象 .equals() 方法也总是不相等。

每当我们强制重写 .equals() 方法时,为了保持 .equals() 和 hashCode() 方法之间的上述约定,我们应该重写 hashCode() 方法。

另外,在HashMap的内部工作中负载因子(Bucket)也扮演着重要的角色。 让我们了解一下 负载因子(Bucket) 是什么。

负载因子(Bucket)的工作机制

负载因子(Bucket)是一个节点数组。 每个节点是一种 LinkedList 类型的数据结构。 多个节点可以放在同一个桶内。 桶的序号是该桶的索引或位置。

有了这些基本概念后,接下来就看下他们是怎么一起工作的

我们都知道 HashMap 使用 put(K, V) 方法来插入任何新的 key-value。 但是为了调用 put(K, V) 将数据插入到 HashMap 中,会有以下几个动作

  • 它在作为内置函数的 hashCode() 函数的帮助下生成 Key 对象的哈希值。并且在这个哈希的帮助下,它确定了Bucket索引号。下面是一般语法:Index = keyObjects.hashCode() & (numberOfBuckets -1);简单的来说索引就表示在Bucket的什么位置。
  • 如果Bucket为空,那么我们将 put 中的 (K, V) 作为 Entry 添加到该存储桶的 LinkedList 中。
  • 现在,如果Bucket不是空的,那我们该怎么办?如果Bucket不是空的,那么我们只需遍历该桶的 LinkedList。这种遍历 LinkedList 的过程称为哈希冲突。
  • 遍历List中的每一个对象的key,调用equals方法,如果为true,则替换,如果为false,则追加到队尾。
Internal Working of Insertion HashMap

HashMap中的查找

HashMap的查找时间复杂度大部分情况下是O(1),不过有时候也会由于Hash函数而有所不同。

举个极端的例子,如果Hash函数取得不好,每次计算Hash值都相同,那么这个Map结构的查找其实就变成了队列的查找的复杂度了。所以说Hash函数对性能很重要。