Java 集合 HashMap 源码 学习 (JDK-1.8)

小组开小讲堂,在小讲堂上听了HashMap这部分内容,决定看源码再巩固一下。顺便分享给大家。
我参考的是的是JDK 1.8 HashMap的源码

在这之前,先问大家几个问题

  1. new一个HashMap的默认长度是多少
  2. 默认加载因子
  3. HashMap的底层存储
  4. 为什么HashMap的大小必须是2的幂次方
  5. key的Hash方法
  6. hashCode碰撞时怎么处理
  7. 扩容时怎么处理
  8. HashMap的最大长度

首先看一下HashMap的常量和方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/**
* 默认加载因子0.75
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;


/**
* 默认容量 16
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


/**
* 默认构造方法
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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;
this.threshold = tableSizeFor(initialCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 默认的初始容量是16 - 2的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 最大容量,必须是2的幂且小于2的30次方,传入容量过大将被这个值替换
// 1 << 30,也就是2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//
static final int TREEIFY_THRESHOLD = 8;

//
static final int UNTREEIFY_THRESHOLD = 6;

//
static final int MIN_TREEIFY_CAPACITY = 64;

一个静态内部类Node
static class Node<K,V> implements Map.Entry<K,V>

内部类KeySet
final class KeySet extends AbstractSet

内部类Values
final class Values extends AbstractCollection

内部类EntrySet
final class EntrySet extends AbstractSet<Map.Entry<K,V>>

抽象类HashIterator
abstract class HashIterator

内部类KeyIterator
final class KeyIterator extends HashIterator implements Iterator

final class ValueIterator extends HashIterator
implements Iterator

// 构造方法,传入初始容量和加载因子
// 方法会对初始容量进行校验,大于0,小于2的30次方
// 方法会对加载因子进行校验,大于0,并且部位NaN
public HashMap(int initialCapacity, float loadFactor)

// 构造方法,传入初始容量
// 同上
// 使用默认加载因子0.75
public HashMap(int initialCapacity)

// 构造方法
// 同上
// 使用默认初始容量16,默认加载因子0.75
public HashMap()

// 构造方法
// 传入map
// 使用默认加载因子0.75
public HashMap(Map<? extends K, ? extends V> m)

// 根据key计算hash值
static final int hash(Object key)

//
static Class<?> comparableClassFor(Object x)

//
static int compareComparables(Class<?> kc, Object k, Object x)

// Returns a power of two size for the given target capacity.
static final int tableSizeFor(int cap)

// Implements Map.putAll and Map constructor
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

// Returns the number of key-value mappings in this map.
public int size()

// Returns true if this map contains no key-value mappings.
public boolean isEmpty()

// Returns the value to which the specified key is mapped,
// or null if this map contains no mapping for the key.
public V get(Object key)

// Implements Map.get and related methods
final Node<K,V> getNode(int hash, Object key)

// Returns true if this map contains a mapping for the specified key.
public boolean containsKey(Object key)

// Associates the specified value with the specified key in this map.
// If the map previously contained a mapping for the key, the old
// value is replaced.
public V put(K key, V value)

// Implements Map.put and related methods
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

Hashmap继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。
它的key、value都可以为null,映射不是有序的。      
Hashmap不是同步的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
Map map = Collections.synchronizedMap(new HashMap());

HashMap 中两个影响其性能的重要参数:“初始容量” 和 “加载因子”。
容量: 是哈希表中桶的数量,初始容量 只是哈希表在创建时的容量
加载因子: 是哈希表在其容量自动增加之前可以达到多满的一种尺度(默认0.75)。 
当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(扩容,即重建内部数据结构,桶数X2)。
加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.

HashMap数据结构

HashMap数据结构
Hashmap本质是数组加链表。
通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样,然后再计算出数组下标,
如果多个key对应到同一个下标,就用链表串起来,新插入的在前面。

长度必须是2的幂次方

这里的h是”int hash = hash(key.hashCode());”, 也就是根据key的hashCode再次进行一次hash操作计算出来的 .
length是Entry数组的长度 .
一般我们利用hash码, 计算出在一个数组的索引, 常用方式是”h % length”, 也就是求余的方式 .
可能是这种方式效率不高, SUN大师们发现, “当容量一定,是2^n时,h & (length - 1) == h % length” . 按位运算特别快 .

1
2
3
4
5
6
/** 
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}

对于length = 16, 对应二进制”1 0000”, length-1=”0 1111”
假设此时h = 17 .
(1) 使用”h % length”, 也就是”17 % 16”, 结果是1 .
(2) 使用”h & (length - 1)”, 也就是 “1 0001 & 0 1111”, 结果也是1 .
我们会发现, 因为”0 1111”低位都是”1”, 进行”&”操作, 就能成功保留”1 0001”对应的低位, 将高位的都丢弃, 低位是多少, 最后结果就是多少 .
刚好低位的范围是”0~15”, 刚好是长度为length=16的所有索引 .

线程安全

Map m = Collections.synchronizeMap(hashMap);

ConcurrentHashMap

References

[1] 深入解析HashMap、HashTable
[2] HashMap和Hashtable的区别
[3] JAVA中HashMap和Hashtable区别
[4] Differences between HashMap and Hashtable?
[5] HashMap的工作原理
[6] Java集合之HashMap源码解析 | gyl-coder
[7] Java集合之HashMap源码解析
[8] HashMap的长度为什么设置为2的n次方
[8] HashMap深度解析(一)
[9] HashMap深度解析(二)
[10] Java集合框架源码解析之HashMap