hashmap类
存储结构
元素：有一个静态内部类，叫Node，实现了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
hashmap字段：
transient Node<K,V>[] table; // hashmap的存储结构
transient Set<Map.Entry<K,V>> entrySet; // 键的集合
transient int size; // 键值对数量
// This field is used to make iterators on Collection-views of the HashMap fail-fast.
transient int modCount; // hashmap发生结构改变的次数
int threshold; // size 的临界值，当 size 大于等于 threshold 就必须进行扩容操作
final float loadFactor; // 负载因子，默认0.75
transient：让某些被修饰的成员属性变量不被序列化
transient
拉链法
hashmap采用拉链法来解决冲突问题。具有相同键的值放在一个哈希桶(bin)的链表中，新插入的Node放在链表尾部(newNode赋值给p.next)。
- 负载因子默认为0.75，负载=负载因子*容量大小
- 当hashmap超过一定负载时，会进行扩容resize()，即生成一个新的、原来2倍大小的hashmap，再进行rehash()，把原hashmap中的元素重新映射到新的hashmap中
- 当哈希桶的长度超过8时，会变成红黑树
- resize()和rehash()后，如果哈希桶的长度小于6，会从红黑树变回一般的链表
// 遍历桶的代码（感兴趣的可以去看详细的源码）
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
线程不安全
hashmap的线程不安全主要是没有锁机制，可想而知，如果多个线程同时操作hashmap，就可能导致出错。
问题一：数据丢失/覆盖
假设线程A、B要同时在一个桶的尾部添加新的Node。
- 线程A已经获得了哈希桶尾部Node的引用，但A的时间片用尽，A被挂起；
- 线程B开始执行，并向桶尾部添加新Node；
- 线程A恢复执行，此时A并不知道桶尾部添加了新的Node，因此当A利用之前获得的"桶尾部引用"添加新Node时，会把线程B添加的Node覆盖掉。
问题二：扩容->循环链表->get()死循环
在Java 8 之前，哈希桶中添加新Node不是加在尾部，而是加在头部。这就导致，在resize()和rehash()的时候，由于多线程，可能会在哈希桶中形成一个循环链表。那么下一次get(key)的时候，就有可能在该遍历哈希桶时陷入死循环。
这个问题在Java 8之后大大改善
fail-fast
http://wiki.jikexueyuan.com/project/java-enhancement/java-thirtyfour.html
fail-fast是 Java 集合的一种错误检测机制。
例如：假设存在两个线程（线程 1、线程 2），线程 1 通过 Iterator 在遍历集合 A 中的元素，在某个时候线程 2 修改了集合 A 的结构（是结构上面的修改，例如增加、删除元素，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生 fail-fast 机制。
当多个线程对集合进行结构上的改变的操作时，有可能会产生 fail-fast 机制。记住是有可能，而不是一定。迭代器的 fail-fast 行为无法得到保证，它不能保证一定会出现该错误，但是 fail-fast 操作会尽最大努力抛出 ConcurrentModificationException 异常。
与 HashTable 比较
- HashTable 使用 synchronized 来进行同步，会锁住整张表，效率低。
- HashMap 允许键为null（放在table[0]的哈希桶中），Hashtable不允许。
- HashMap 的迭代器（Iterator）是 fail-fast 迭代器，而Hashtable 的迭代器（enumerator）不是 fail-fast 迭代器。
- HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。
http://www.importnew.com/7010.html
ConcurrentHashmap
使用 synchronize 关键字来保证同步（串行化）
