Java HashMap源码解析与性能优化详解

49 浏览量更新于2024-09-01 收藏 198KB PDF 举报

在Java编程中，HashMap是一种常用的数据结构，它是基于哈希表实现的，提供了快速查找、插入和删除操作。本文将深入剖析HashMap的源码以及性能优化的关键点，主要针对Java 8及后续版本的HashMap。 HashMap的核心存储结构基于数组和链表（或称为开放地址法中的红黑树，从Java 8起，默认容量大于64时会采用红黑树）。当你想要存储一个元素时，首先通过key的哈希函数计算得到一个索引，这个索引对应数组中的一个位置。如果没有元素，就直接将新元素存入；如果有元素，则通过链表或红黑树的方式解决哈希冲突，链表中的每个节点包含一个Entry对象，存储key-value对。 HashMap的主要内部变量包括： 1. DEFAULT_INITIAL_CAPACITY：表示默认的初始容量，即数组长度，其值为16。 2. MAXIMUM_CAPACITY：定义了HashMap的最大容量，等于2的30次方。 3. DEFAULT_LOAD_FACTOR：表示装载因子，当哈希表的元素数量超过此值与当前容量的乘积时，就需要进行扩容，默认值为0.75。 4. table：实际的哈希数组，存储键值对。 5. size：键值对的数量。 6. threshold：扩容的阈值，等于负载因子乘以当前容量。 7. loadFactor：装载因子的具体数值。在HashMap的源码优化方面，Java 8引入了以下改进： - 避免了大量的resize操作：之前的HashMap在装载因子达到一定程度时，会频繁地进行数组的扩大和重新哈希。Java 8之后，当元素数量达到阈值时，HashMap会选择是否立即扩大容量，而不是立刻进行resize，这大大减少了不必要的内存消耗和计算时间。 - 使用红黑树替代链表：当链表长度超过一定阈值（8），为了提高查询性能，HashMap会将链表转换为红黑树。这样，查找时间复杂度从O(n)降低到了O(log n)。 - 优化哈希算法：虽然Java的HashMap使用了开放寻址法，但在Java 8中，对于较大的初始容量，可能会使用更复杂的哈希函数来提高碰撞的均匀性。理解HashMap的源码对于优化程序性能至关重要。通过对装载因子、数据结构选择以及性能优化策略的掌握，开发者可以在保证高效访问的同时，避免因过度填充而导致的性能下降。在实际编程中，合理设置初始容量、监控装载因子并适时调整，可以帮助我们充分利用HashMap的优势，提升代码的执行效率。

剖析剖析Java中中HashMap数据结构的源码及其性能优化数据结构的源码及其性能优化

主要介绍了Java中HashMap数据结构的源码及其性能优化,文中以Java 8后HashMap的性能提升来讨论了HashMap的一些优化点,需要的朋友可以参考下

存储结构存储结构

首先，HashMap是基于哈希表存储的。它内部有一个数组，当元素要存储的时候，先计算其key的哈希值，根据哈希值找到元素在数组中对应的下标。如果这个位置没有元素，就直接把当前元素放进

去，如果有元素了(这里记为A)，就把当前元素链接到元素A的前面，然后把当前元素放入数组中。所以在Hashmap中，数组其实保存的是链表的首节点。下面是百度百科的一张图：

如上图，每个元素是一个Entry对象，在其中保存了元素的key和value，还有一个指针可用于指向下一个对象。所有哈希值相同的key(也就是冲突了)用链表把它们串起来，这是拉链法。

内部变量内部变量

//默认初始容量

static final int DEFAULT_INITIAL_CAPACITY = 16;

//最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

//默认装载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//哈希表

transient Entry<K,V>[] table;

//键值对的数量

transient int size;

//扩容的阈值

int threshold;

//哈希数组的装载因子

final float loadFactor;

在上面的变量中，capacity是指哈希表的长度，也就是table的大小，默认为16。装载因子loadFactor是哈希表的“装满程度”，JDK的文档是这样说的：

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load

factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

大体意思是：装载因子是哈希表在扩容之前能装多满的度量值。当哈希表中“键值对”的数量超过当前容量(capacity)和装载因子的乘积后，哈希表重新散列(也就是内部的数据结构重建了)，并且哈希表的容

量大约变为原来的两倍。

从上面的变量定义可以看出，默认的装载因子DEFAULT_LOAD_FACTOR 是0.75。这个值越大，空间利用率越高，但查询速度(包括get和put)操作会变慢。明白了装载因子之后，threshold也就能理解

了，它其实等于容量*装载因子。

构造器构造器

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " +

loadFactor);

// Find a power of 2 >= initialCapacity

int capacity = 1;

while (capacity < initialCapacity) //计算出大于指定容量的最小的2的幂

capacity <<= 1;

this.loadFactor = loadFactor;

threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

table = new Entry[capacity]; //给哈希表分配空间

useAltHashing = sun.misc.VM.isBooted() &&

(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);

init();

}

构造器有好几个，最终都会调用上面的这个。它接受两个参数，一个是初始容量，还有一个是装载因子。刚开始先判断值合不合法，有问题的话会抛出异常。重要的是下面的capacity的计算，它的逻辑

是计算出大于initialCapacity的最小的2的幂。其实目的就是要让容量能大于等于指定的初始容量，但这个值还得是2的指数倍，这是一个关键的问题。这么做的原因主要是为了哈希值的映射。先来看一下

HashMap中有关哈希的方法：

final int hash(Object k) {

int h = 0;

if (useAltHashing) {

if (k instanceof String) {

return sun.misc.Hashing.stringHash32((String) k);

}

h = hashSeed;

}

h ^= k.hashCode();

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

static int indexFor(int h, int length) {

return h & (length-1);

}

hash()方法重新计算了key的哈希值，用了比较复杂的位运算，具体逻辑我也不清楚，反正肯定是比较好的方法，能减少冲突什么的。

下面的indexFor()是根据哈希值得到元素在哈希表中的下标。一般在哈希表中是用哈希值对表长取模得到。当length(也就是capacity)为2的幂时，h & (length-1)是同样的效果。并且，2的幂一定是偶数，

那么减1之后就是奇数，二进制的最后一位一定是1。那么h & (length-1)的最后一位可能是1，也可能是0，可以均匀地散列。如果length是奇数，那么length-1就是偶数，最后一位是0。此时h & (length-1)

的最后一位只可能是0，所有得到的下标都是偶数，那么哈希表就浪费了一半的空间。所以HashMap中的容量(capacity)一定要是2的幂。可以看到默认的DEFAULT_INITIAL_CAPACITY=16和

MAXIMUM_CAPACITY=1<<30都是这样的。

Entry对象对象

HashMap中的键值对被封装成Entry对象，这是HashMap中的一个内部类，看一下它的实现：

static class Entry<K,V> implements Map.Entry<K,V> {

final K key;

下载后可阅读完整内容，剩余4页未读，立即下载

weixin_38725426

粉丝: 6
资源: 936

Java HashMap源码解析与性能优化详解

HashMap原理分析及性能优化

邓俊辉版java 数据结构源码

java数据结构源码

hashmap的源码分析

HashMap底层源码分析

在JDK1.8中，HashMap如何利用扰动函数优化哈希值分布并解决冲突？请结合源码分析其内部实现。

HashMap 源码分析

hashmap源码详细分析

hashmap源码分析

数组和链表在HashMap中的应用，要求新手能看懂，结合代码分析，注释详细

最新资源