一、什么是HashMap
HashMap是Java集合框架中的一个类，它实现了Map接口，用于存储键值对，其中键和值均可以为null。HashMap提供了O(1)的时间复杂度来实现put()和get()方法的添加和查询操作。具体实现方式是通过将键对象的hashCode值映射到存储数组的索引位置来进行存储。
二、HashMap的存储结构
HashMap的基本存储结构是一个Entry数组，Entry类就是HashMap中存储每个键值对的容器。下面是Entry类的定义：
class Entry {
final int hash;
final K key;
V value;
Entry next;
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
}
可以看到每个Entry对象都包含了一个int类型的hash值，表示当前键对象的hash值。通过hashCode()方法可以把键对象映射为一个int值，这个int值被称为散列码（hash code）。
Entry还包含了一个next属性，用于指向桶中的下一个键值对，如果同一个桶中有多个键值对，就会形成一个链表。
三、Hash算法
在HashMap中，键值对是根据它们的hashCode()和equals()方法来存储并获取的。hashCode()方法生成了一个int范围内的散列码，这个散列码会被用来计算出在Entry数组中存储的索引位置。由于可能存在不同的键对象hash值相同的情况，因此同一个桶里可能存在多条链表，需要遍历链表来查找真正的键值对。
在默认情况下，HashMap的hash算法如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先，如果键对象为null，则直接返回0作为hash值。如果键对象不为null，则将hashCode()方法的返回值赋值为h。接着，将h右移16位并将h与其异或（^）后的结果返回为最终的hash值。
四、解决哈希冲突
哈希冲突是指不同的键对象在通过hash算法之后生成了相同的hash值，导致它们应该被存储在同一个桶中，从而引发链表的形成。在存储键值对时，当一个新的键值对需要存储时，HashMap会通过计算key对象的hash值来得到存储在数组中的位置，如果该位置已经有其他键值对存在，新的键值对就需要放在同一个桶中，否则将直接存储在该位置上，此过程被称为哈希冲突解决，具体实现方法有两种：链表法和开放寻址法。
五、扩容
在 HashMap 的底层是基于数组和链表实现的，因此在存储的键值对会越来越多的时候，HashMap 底层会进行扩容以保证查询效率。当HashMap达到一定的负载因子时（默认为0.75），会触发扩容操作。扩容的过程就是将原来的Entry数组扩大为原来的两倍，同时将原来的键值对重新计算hash值，然后重新存储在新的数组中。
六、应用场景
HashMap在Java中被广泛应用，它适用于需要搜索、插入和删除元素频繁的场景。比如，在Web框架的缓存中，使用HashMap缓存数据能够有效地提高查询性能。在开发过程中，需要注意多线程并发访问的问题，可以使用ConcurrentHashMap来替代HashMap。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/194185.html
微信扫一扫 
支付宝扫一扫 