Java教程-Java中HashMap的工作原理
Java中HashMap的工作原理
什么是哈希
哈希是将对象转换为整数值的过程。整数值有助于索引和加快搜索速度。
什么是HashMap
HashMap是Java集合框架的一部分。它使用一种称为哈希的技术。它实现了Map接口。它以键值对的形式存储数据。HashMap包含一个节点的数组，而节点以类的形式表示。它在内部使用数组和LinkedList数据结构来存储键和值。HashMap有四个字段。
在了解HashMap的内部工作原理之前，您必须了解hashCode()和equals()方法。
- equals()：它检查两个对象是否相等。它比较键的相等性。它是Object类的方法。它可以被重写。如果重写了equals()方法，则必须重写hashCode()方法。
- hashCode()：这是Object类的方法。它以整数形式返回对象的内存引用。从该方法得到的值被用作桶号。桶号是映射中元素的地址。空键的哈希码为0。
- 桶：节点数组称为桶。每个节点都有类似LinkedList的数据结构。多个节点可以共享同一个桶。它们的容量可能不同。
在HashMap中插入键值对
我们使用put()方法将键值对插入HashMap中。HashMap的默认大小为16（0到15）。
示例
在以下示例中，我们想在HashMap中插入三个（键，值）对。
- HashMap<String, Integer> map = new HashMap<>();
- map.put("Aman", 19);
- map.put("Sunny", 29);
- map.put("Ritesh", 39);
让我们看看键值对将保存在HashMap的哪个索引处。当我们调用put()方法时，它计算键"Aman"的哈希码。假设"Aman"的哈希码为2657860。为了将键存储在内存中，我们必须计算索引。
计算索引
索引减小了数组的大小。计算索引的公式如下：
- 索引 = hashcode(键) & (n-1)
其中n是数组的大小。因此，"Aman"的索引值为：
- 索引 = 2657860 & (16-1) = 4
值4是计算出的索引值，键和值将存储在HashMap中。
哈希冲突
当两个或多个键的计算索引值相同时，就会发生哈希冲突。让我们计算另一个键"Sunny"的哈希码。假设"Sunny"的哈希码为63281940。为了将键存储在内存中，我们必须使用索引公式计算索引。
- 索引=63281940 & (16-1) = 4
值4是计算出的索引值，键将存储在HashMap中。在这种情况下，equals()方法检查两个键是否相等。如果键相同，则替换为当前值。否则，将此节点对象通过LinkedList连接到现有节点对象。因此，两个键都将存储在索引4处。
类似地，我们将存储键"Ritesh"。假设键的哈希码为2349873。索引值将为1。因此，该键将存储在索引1处。
HashMap中的get()方法
get()方法用于根据键获取值。如果不知道键，则无法获取值。当调用get(K Key)方法时，它计算键的哈希码。
假设我们要获取键"Aman"。将调用以下方法。
- map.get(new Key("Aman"));
它生成的哈希码为2657860。现在使用索引公式计算2657860的索引值。如上面计算的那样，索引值为4。get()方法搜索索引值4。它将第一个元素的键与给定的键进行比较。如果两个键相等，则返回值；否则，检查节点中是否存在下一个元素。在我们的情况下，它被发现为节点的第一个元素，并返回值19。
让我们获取另一个键"Sunny"。
键"Sunny"的哈希码是63281940。如上面计算的那样，63281940的计算索引值为4。转到数组的索引4并比较第一个元素的键与给定的键。它也会比较键。在我们的情况下，给定的键是第二个元素，节点的下一个元素为null。它将第二个元素的键与指定的键进行比较，并返回值29。如果节点的下一个元素为null，则返回null。
