java软件技术文档-深入java8的集合3：HashMap的实现原理.pdf

深入 java8 的集合 3：HashMap 的实现原理

一、概述

二话不说，一上来就点开源码，发现里面有一段介绍如下：

Hash table based implementation of the Map interface. This implementation provides all

of the optional map operations, and permits null values and the null key. (The HashMap

class is roughly equivalent to Hashtable, except that it is unsynchronized and permits

nulls.) This class makes no guarantees as to the order of the map; in particular, it does not

guarantee that the order will remain constant over time.

翻译一下大概就是在说，这个哈希表是基于 Map 接口的实现的，它允许 null 值和

factor too low) if iteration performance is important.

An instance of HashMap has two parameters that affect its performance: initial

capacity and load factor. The capacity is the number of buckets in the hash table, and the

initial capacity is simply the capacity at the time the hash table is created. 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.

不要急，我真的不是来翻译的。再来看看这一段，讲的是 Map 的这种实现方式为 get

操作来进行扩容。

HashMap 的大致结构如下图所示，其中哈希表是一个数组，我们经常把数组中的每

一个节点称为一个桶，哈希表中的每个节点都用来存储一个键值对。在插入元素时，

如果发生冲突（即多个键值对映射到同一个桶上）的话，就会通过链表的形式来解

决冲突。因为一个桶上可能存在多个键值对，所以在查找的时候，会先通过 key 的

哈希值先定位到桶，再遍历桶上的所有键值对，找出 key 相等的键值对，从而来获

取 value。

（因为我这里主要介绍的是 Java 对 HashMap 的实现，而不是 hash 算法，所以如果

对哈希算法不了解，建议先去学习一下！）

//最大的容量上限为 2^30

static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的负载因子为 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

//变成树型结构的临界值为 8

static final int TREEIFY_THRESHOLD = 8;

//恢复链式结构的临界值为 6

transient int size;

//哈希表被修改的次数

transient int modCount;

//它是通过 capacity*load factor 计算出来的，当 size 到达这个值时，

就会进行扩容操作

int threshold;

//负载因子