Java HashMap底层实现解析：1.7到1.8的演变

版权申诉

5星 · 超过95%的资源 16 浏览量更新于2024-07-04 收藏 429KB PDF 举报

"这篇文档详细探讨了Java集合框架中的HashMap数据结构，主要聚焦于JDK 1.7的实现，同时也涉及1.8及以后版本的改进，包括1.8引入的红黑树优化。文章深入解析了HashMap的底层实现，包括数组和链表的组合以及1.8版本后引入的红黑树数据结构，旨在帮助读者理解HashMap的工作原理和性能特点。" HashMap在Java中是一个常用的容器，用于存储键值对。它基于Map接口，允许null键和null值，但键的唯一性保证了每个键只能对应一个值。HashMap内部使用了一个 Entry 类型的数组来存储键值对，数组中的每个元素都是一个链表的头节点。这种设计使得HashMap能够快速定位键值对，通常在O(1)的时间复杂度内完成。在JDK 1.7中，当链表的长度超过一定阈值（通常是8）时，该链表会转换为一个红黑树，以降低查找、插入和删除操作的时间复杂度至O(log n)。这个阈值和负载因子（默认为0.75）共同决定了何时进行数组扩容和链表转树的操作。负载因子是HashMap当前元素数量与初始容量或当前容量的比值，当达到这个比例时，HashMap会自动扩容以保持效率。 HashMap的基本属性包括默认初始容量（16）、默认负载因子（0.75）以及一个空的Entry数组。随着元素数量增加，size变量记录HashMap中元素的数量，threshold变量则表示触发扩容的临界值。在实际使用中，可以通过构造函数自定义初始容量和负载因子。链表作为HashMap的重要组成部分，文中也进行了基础介绍。链表是一种非连续内存存储的数据结构，根据指针连接节点。链表分为单向链表、单向循环链表、双向链表和双向循环链表四种类型，每种都有其特定的结构和操作特性。例如，单向链表仅能向前遍历，而双向链表可以前后移动。这篇文档深入解析了HashMap的内部机制，对于理解Java集合框架的高效实现以及优化数据存储和检索有极大帮助。无论是开发者还是学习者，都能从中获益，更好地运用HashMap并解决实际问题。

} catch(IllegalArgumentException failed) {

throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);

}

ALTERNATIVE_HASHING_THRESHOLD = threshold; //返回

}

//HashCode的初始值为 0

transient int hashSeed = 0;

//构造⽅法，指定初始容量和负载因⼦

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);

this.loadFactor = loadFactor; //设置负载因⼦

threshold = initialCapacity; //初始容量

init(); //不做任何操作

}

//构造⽅法，指定了初始容量

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

//⽆参构造⽅法，使⽤默认的容量⼤⼩和负载因⼦，并调⽤其他的构造⽅法

public HashMap() {

this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

}

//构造函数，参数为指定的Map集合

public HashMap(Map<? extends K, ? extends V> m) {

this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,

DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

inflateTable(threshold);

putAllForCreate(m);

}

//选择合适的容量值，最好是number的2的幂数

private static int roundUpToPowerOf2(int number) {

// assert number >= 0 : "number must be non-negative";

return number >= MAXIMUM_CAPACITY

? MAXIMUM_CAPACITY

: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;

}

//扩充表，HashMap初始化时是⼀个空数组，此⽅法执⾏重新复制操作，创建⼀个新的Entry[]

private void inflateTable(int toSize) {

// Find a power of 2 >= toSize

int capacity = roundUpToPowerOf2(toSize); //capacity为2的幂数，⼤于等于toSize

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

table = new Entry[capacity]; //新建数组，并重新赋值

initHashSeedAsNeeded(capacity); //修改hashSeed

}

// internal utilities

剩余19页未读，继续阅读

_webkit

粉丝: 30
资源: 1万+

Java HashMap底层实现解析：1.7到1.8的演变

ConcurrentHashMap的实现原理(JDK1.7和JDK1.8).pdf

常见的数据结构（栈、队列、数组、链表和红黑树） 数组和链表.pdf

HashMap底层实现：数组+链表+红黑树解析

JDK8 HashMap底层实现优化：数组+链表+红黑树详解

Java用数组和链表的方式简单实现HashMap的增删改功能 数组和链表.pdf

HashMap深度解析：JDK1.8后的数组+链表+红黑树实现

JDK1.8 HashMap：数组+链转红黑树优化

HashMap采用了数组+链表+红黑树的数据结构,怎么理解

hashMap是一个双列集合,他在1.7之前的底层是链表加数组,而在1.8之后变成了链表加数组加红黑树

HashMap深度解析：数组、链表与红黑树的秘密

最新资源

常见的数据结构（栈、队列、数组、链表和红黑树）数组和链表.pdf

Java用数组和链表的方式简单实现HashMap的增删改功能数组和链表.pdf