Thinking in Java之HashMap源码分析 - JAVA

欢迎讨论、交流，转载请注明出处，3Q!

前言
在前面的文章中笔者就Map接口和Map接口的实现原理:内部哈希映射技术做了一个简单的

分析，并且对hashCode方法做了一些阐述。可能有些混乱，不过理解这些是弄懂HashMap

的前提，也能帮助我们更好的解析hashMap的源码。

HashMap类设计
HashMap是基于哈希表的Map接口的非同步实现，它提供所有可选的映射操作，并允许使

用null键和null值。此集合不保证映射的顺序，特别不保证其顺序永久不变。

首先我们先看下HashMap类的头部：

[java]
public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable

public class HashMap
extends AbstractMap
implements Map, Cloneable, Serializable 对于它的分析就不多做解释了，AbstractMap类主要是帮助我们自定义自己的Map实现类。

1、底层实现
接下来我们看看HashMap的底层是如何实现的。在这之前我们先对数据结构略作分析。

在java语言中，最基本的结构分为两种：其一为数组，其二为模拟指针(引用)说白了就是

链表。所有的数据类型都可以使用上述的两种来构造。

数组的特点是：寻址容易，插入和删除困难；

链表的特点是：寻址困难，插入和删除容易；

思考下：我们能不能结合两者的优点，折中构造一种寻址容易，插入删除也较为容易的

数据结构呢？答案是肯定的了。我们可以构造一种“链表散列”的数据结构，可以理解为链表

的数组，HashMap就是基于其实现的。

从图中可以看出HashMap的底层就是一个数组结构，数组中的每一项又是一个链表。那么

究竟是不是这样呢？我们看源码吧。

[java]
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
int hash;

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
...........
}

/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
int hash;

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
...........
}
可以看出的是HashMap里面实现了一个静态内部类Entry(记录)，其重要的属性有key、value、next

而HashMap有一个属性是Entrr的数组table。Entry就是table数组中的元素，Map.Entry就会一个键值对

这个键值对持有指向下一个键值对的引用，如此就构成了链表了。

2、构造方法

[java]
/**根据指定容量和负载因子构造HashMap*/
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)
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();
}

/**根据指定的容量和默认的负载因子构造HashMap*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//默认的空的构造器

Thinking in Java之HashMap源码分析(一)