前言
做什么都怕进入狗咬尾巴的怪圈，上次看hashmap源码还是2012年，这次出去面试时被问到了hashmap的问题，整体思路还是记得的，巴拉巴拉一堆。回来再看一下源码，温习一下
想要了解hashmap，就得先知道一下他的数据结构理论
哈希数据结构
哈希表（Hash table，也叫散列表），是根据key而直接进行访问的数据结构。也就是说，它通过把key映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的做法其实很简单，就是把key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
哈希函数
哈希查找第一步就是使用哈希函数将键映射成索引。这种映射函数就是哈希函数。如果我们有一个保存0-M数组，那么我们就需要一个能够将任意键转换为该数组范围内的索引（0~M-1）的哈希函数
R.W.Floyed给出的衡量散列思想的三个标准：
- 一个好的hash算法的计算应该是非常快的
- 一个好的hash算法应该是冲突极小化， 如果存在冲突，应该是冲突均匀化。
哈希冲突
通过哈希函数，我们可以将键转换为数组的索引(0-M-1)，但是对于两个或者多个键具有相同索引值的情况，我们需要有一种方法来处理这种冲突。
拉链法
一种比较直接的办法就是，将大小为M 的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法
该方法的基本思想就是选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率。对采用拉链法的哈希实现的查找分为两步，首先是根据散列值找到等一应的链表，然后沿着链表顺序找到相应的键。
实现基于拉链表的散列表，目标是选择适当的数组大小M，使得既不会因为空链表而浪费内存空间，也不会因为链表太而在查找上浪费太多时间。拉链表的优点在于，这种数组大小M的选择不是关键性的，如果存入的键多于预期，那么查找的时间只会比选择更大的数组稍长，另外，我们也可以使用更高效的结构来代替链表存储。如果存入的键少于预期，索然有些浪费空间，但是查找速度就会很快。所以当内存不紧张时，我们可以选择足够大的M，可以使得查找时间变为常数，如果内存紧张时，选择尽量大的M仍能够将性能提高M倍。
线性探测法
线性探测法是开放寻址法解决哈希冲突的一种方法，基本原理为，使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突。如下图所示：
对照前面的拉链法，在该图中，”Ted Baker” 是有唯一的哈希值153的，但是由于153被”Sandra Dee”占用了。而原先”Snadra Dee”和”John Smith”的哈希值都是152的，但是在对”Sandra Dee”进行哈希的时候发现152已经被占用了，所以往下找发现153没有被占用，所以存放在153上，然后”Ted Baker”哈希到153上，发现已经被占用了，所以往下找，发现154没有被占用，所以值存到了154上。
开放寻址法中最简单的是线性探测法：当碰撞发生时即一个键的散列值被另外一个键占用时，直接检查散列表中的下一个位置即将索引值加1，这样的线性探测会出现三种结果：
- 命中，该位置的键和被查找的键相同
- 未命中，键为空
- 继续查找，该位置和键被查找的键不同。
线性探查（Linear Probing）方式虽然简单，但是有一些问题，它会导致同类哈希的聚集。在存入的时候存在冲突，在查找的时候冲突依然存在。
hashmap 源码分析
hashmap原理角度看就是基于哈希数据结构的一种实现，解决冲突的办法是使用拉链法
从源码基于JDK1.7看1
2
3public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap是基于哈希表的Map接口的非同步实现，它提供所有可选的映射操作，并允许使用null键和null值。
此集合不保证映射的顺序，特别不保证其顺序永久不变。
初始化
1 | public HashMap(int initialCapacity, float loadFactor) { |
两个重要的初始化参数，[初始容量，负载因子]
这个JDK7大版本里面的小版本对hashmap改动好好几次。
这个源码是基于JDK7.0_80的。有些版本在构造函数里面就确保容量是2的N次方，但这个版本没有，很简单的赋值
初始容量16，负载因子0.751
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
2的N次方
很多算法书上都认为想要降低key冲突，最好容量为素数。为什么java却取了个2的N次方呢。
为了将各元素的hashCode保存至长度为Length的key数组中，一般采用取模的方式，即index = hashCode % Length。不可避免的，存在多个不同对象的hashCode被安排在同一位置，这就是我们平时所谓的“冲突”。
如果仅仅是考虑元素均匀化与冲突极小化，似乎应该将Length取为素数（尽管没有明显的理论来支持这一点，但数学家们通过大量的实践得出结论，对素数取模的产生结果的无关性要大于其它数字）。为此，Craig Larman and Rhett Guthrie《Java Performence》中对此也大加抨击。
为了弄清楚这个问题，Bruce Eckel（Thinking in JAVA的作者）专程采访了java.util.hashMap的作者Joshua Bloch,此设计的原因
取模运算在包括Java在内的大多数语言中的效率都十分低下，而当除数为2的N次方时，取模运算将退化为最简单的位运算，其效率明显提升（按照Bruce Eckel给出的数据，大约可以提升5～8倍）1
2
3
4
5
6
7/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！
put操作
1 | /** |
当table == EMPTY_TABLE时，先填充table1
2
3
4
5
6
7
8
9
10
11/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
这儿看到了2的N次方，没有跟之前一样使用while循环1
2
3int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
threshold的值=容量*负载因子
看下roundUpToPowerOf2()1
2
3
4
5
6private 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;
}
主要是Integer.highestOneBit1
2
3
4
5
6
7
8
9public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
这个方法单纯的使用位运算，性能自然提高
解析下这个方法，这个方法的作用是求构成一个整数的最大的位所代表的整数的值
接下来举个简单的例子，128来讲二进制是1000 0000。下面以他为例子算下：
移1位
1000 0000
0100 0000
|————-
移2位
1100 0000
0011 0000
|————
移4位
1111 0000
0000 1111
|————
移8位
1111 1111
0000 0000
|————
移动16位
1111 1111
0000 0000
|————
1111 1111
最终的结果如你所看到的，后面的位全部填充为1，把后面的位全部减掉就得到了最高的位代表的整数。
回到put方法，如果key==null，putForNullKey(value);说明hashmap支持key为null1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
* Offloaded version of put for null keys
*/
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
这个逻辑比较简单
- 第一步，如果找到之前有key为null的key,进行一下value替换，返回oldValue
- 如果没有为null的key,那进行addEntry() 添加元素的主要方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
新添加元素时，先看下有没有达到threshold && bucketIndex元素不为null
如果成立，那就需要resize，这是个耗性能的操作，所以在初始化时，一般计算好元素多少，给一个合适的初始容量
按照上面的条件，一个合适的容量应该这样计算了
我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.751000 < 1000, 也就是说为了让0.75 size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。
先看createEntry1
2
3
4
5void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
这个很简单，新建一个Entry指向bucketIndex，老元素e，被指向新元素的next。
这儿也看出hashmap是使用的拉链法
看Entry,就是一个链表，一个元素接着另一个元素1
2
3
4
5
6
7
8
9
10
11
12static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
resize方法
耗性能的地方，重新散列，看看这个方法的实现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//在put方法里,当容量达到threshold时，进行双倍的扩容。
resize(2 * table.length);
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
如果容量已经达到MAX_VALUE,那就不扩容了，只能处理冲突
transfer(),这是核心方法，把以前的元素，按新的capacity，计算的hashCode，重新放置元素。
这儿看到e.next=newTable[i],明显使用的是链表头部插入法
get方法
1 | public V get(Object key) { |
get很好理解了，跟算法一致，先hash找bucket，如果有冲突的元素，再使用equals来判定
hashSeed
1 | /** |
initHashSeedAsNeeded在inflateTable中被调用过，这个hashSeed到底有什么用？
hashSeed就好像我们加密时使用的密钥，在StackOverfolw上是这样描述hashSeed的：
The seed parameter is a means for you to randomize the hash function. You should provide the same seed value for all calls to the hashing function in the same application of the hashing function. However, each invocation of your application (assuming it is creating a new hash table) can use a different seed, e.g., a random value.
Why is it provided?
One reason is that attackers may use the properties of a hash function to construct a denial of service attack. They could do this by providing strings to your hash function that all hash to the same value destroying the performance of your hash table. But if you use a different seed for each run of your program, the set of strings the attackers must use changes.
虽然seed近似随机，但在同一个HashMap中必须保证每次的计算Hash值的时候使用的同一个seed，也就相当于保证我们在一个密码系统中加密时，使用同一个密钥。同时使用seed可以抵御攻击，因为每个应用的seed都会一样。
对于安全方面的了解几乎是0，有机会再学习了。
ConcurrentModificationException
hashmap不是线程安全的1
2
3
4
5
6
7
8
9
10 private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
这个内部遍历类使用了Fail-Fast机制1
2
3
4
5
6
7
8/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
modCount为HashMap的一个实例变量，并且被声明为volatile，表示任何线程都可以看到该变量被其它线程修改的结果
（根据JVM内存模型的优化，每一个线程都会存一份自己的工作内存，此工作内存的内容与本地内存并非时时刻刻都同步，因此可能会出现线程间的修改不可见的问题）
使用Iterator开始迭代时，会将modCount的赋值给expectedModCount，在迭代过程中，通过每次比较两者是否相等来判断HashMap是否在内部或被其它线程修改
在并发条件下，还是要使用并发包下的ConcurrentHashmap，有时间也得写一写
总结
(1) 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
