Java－通俗易懂地理解HashMap的原理

短命女 2022-12-23 15:29 128阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

**一、HashMap的节点**

HashMap是一个集合，键值对的集合，集合中每个元素（这里我们称每个元素为节点）用Node<K,V>表示。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }

Node是一个内部类。这里的key为键，value为值，next指向下一个元素。可以看出HashMap中的元素不是一个单纯的键值对，**还包含下一个元素的引用**。

**二、HashMap的数据结构**

HashMap的数据结构为**数组＋（链表或红黑树）**。为什么采用这种结构来存储元素呢？

**数组的特点：查询效率高，插入、删除效率低**。

**链表的特点：查询效率低，插入、删除效率高**。

在HashMap底层使用数组＋（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询、插入和删除的效率都很高。

**三、HashMap存储元素的过程**

第一步：计算出键的HashCode值，该值用来定位要将这个元素存放到数组中的什么位置。

**什么是HashCode？**

在Object类中有一个方法：

public native int hashCode();

该方法用native修饰，所以是一个本地方法。所谓本地方法就是非Java代码写成的方法，本地方法的代码通常用C或C++写成，在Java中可以去调用它。

调用这个方法会生成一个int型的整数，我们叫它哈希码，哈希码和调用它的对象的地址和内容有关。

**哈希码的特点是：**

**对于同一对象，如果没有被修改（使用equals比较返回true），那么无论何时它的HashCode值都是相同的；**

**对于两个对象，即使使用equals比较返回false，它们的HashCode值也有可能是相等的。**

明白了HashCode，我们再来看元素如何通过HashCode定位到要存储在数组的哪里。通过HashCode值与数组长度取模，我们可以得到元素存储的下标。这里要分两种情况：

1、数组索引为下标的地方是空的，这种情况很简单，直接将元素放进去就好了。

2、已经有元素占据了索引为下标的位置，这种情况下我们需要判断一下该位置的元素和当前元素是否相等，使用equals来比较（如果使用默认的规则是比较两个对象的地址，也就是两者需要是同一个对象才相等，当然我们也可以重写equals方法来实现我们自己的比较规则，最常见的是通过比较属性值来判断是否相等）。**如果两者相等则直接覆盖**，**如果不等则在已有元素后面使用链表的结构存储该元素。**每个元素节点都有一个next属性指向下一个节点，这里就由数组结构变成了数组＋链表结构，那么红黑树又是怎么回事呢？

因为链表中元素太多的时候会影响查找效率，所以当链表的元素个数达到8的时候，使用链表存储就转变成了使用红黑树存储，原因就是**红黑树是平衡二叉树，在查找性能方面要比链表高。**

**四、HashMap中的两个重要参数**

HashMap中有两个重要的参数：**初始容量大小和加载因子。**初始容量大小是创建时给数组分配的容量大小，默认值为16。**用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用resize方法将数组容量增加到原来的两倍，专业术语叫做扩容。在扩容的时候会生成一个新的数组，原来的所有数据都需要重新计算哈希码值重新分配到新的数组中，所以扩容的操作非常消耗性能。**

创建HashMap时我们可以通过设置合理的初始容量大小来达到尽量少的扩容的目的。加载因子也可以设置（默认值为0.75），但是除非特殊情况不建议设置。

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter