一.什么是HashMap
一·特性
HashMap基于Map接口实现，元素以键值对的方式存储，允许键和值为null，因为key不允许重复，因此只能有一个键为null。它是无序的。HashMap是线程不安全的。
二.jdk1.7
一.数据结构
jdk1.7hashmap是一个“链表散列”的数据结构，数组+单向链表。
Entry类是一个HashMap的静态内部类。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* 创建一个新Entry，并用新的节点指向链表的头结点。
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
二.属性
//默认初始化化容量16，1左移4位即16。可以通过构造方法进行自定义。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子0.75，作用在于，当存储的容量超过阈值（存储容量和加载因子的乘积）时，要对哈希表进行扩展操作。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态
static final Entry<?,?>[] EMPTY_TABLE = {};
//空的存储实体
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//实际存储的键值对的个数
transient int size;
//实际数组容量 也叫扩容的阈值，size超过了threshold就会扩容，当table == {}时，该值为初始容量（初始容量默认为16）。
//阈值=容量*负载因子
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//map结构修改次数，用于迭代器
transient int modCount;
//默认阈值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//哈希种子(hashSeed)用于优化哈希函数，默认为0是不使用替代哈希算法
transient int hashSeed = 0;
//定义Map.Entry<K,V>集合。
private transient Set<Map.Entry<K,V>> entrySet = null;
1.为什么负载载因子是0.75 ？
源码分析：数组下标 = hash & (length-1)， 所以:
加载因子越大，内存利用率越高，index下标冲突概率也就越大；
加载因子越小，内存利用率越低，index下标冲突概率也就越小；
三.构造方法
//这个构造方法用于传入初始容量和扩容因子
public HashMap(int initialCapacity, float loadFactor) {
//传入的初始容量小于0，抛异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//当初始容量大于最大容量时，使用最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//判断加载因子必须是大于0,而且必须是数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 设置实际负载因子
this.loadFactor = loadFactor;
//设置扩容阀值=初始容量，但是在put()方法初始化数组时, 其实际值=容量*负载因子
threshold = initialCapacity;
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//用于将一个Map存入这个map中
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
小结：
1.当调运有参构造，赋予的初始容量传入的初始容量小于0，抛异常。
2.若赋予的初始容量大于最大容量时，使用最大容量 。
四.put()方法
public V put(K key, V value) {
// 判断数组是否为空
if (table == EMPTY_TABLE) {
// 初始化数组方法
inflateTable(threshold);
}
// 判断添加的key是否null
if (key == null)
return putForNullKey(value); // 如果为null, 则对应的value存放到table[0]
// 根据key计算哈希值
int hash = hash(key);
// 计算数组下标 i= hash & (length - 1)
int i = indexFor(hash, table.length);
// 获取相同hashCode对应下标的table[i]数据, 并遍历
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 判断hashcode相同并且key值相同
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 如果为true,表示key一同，覆盖
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++; //实际修改次数加1
// 如果hash不同 或者 hansh相同对象不同， 则添加元素
addEntry(hash, key, value, i);
return null;
}
//key为null的值，默认hashcode为0，放在哈希桶的第一个位置
private V putForNullKey(V value) {
//如果多次put key为null的键值对，新值会覆盖原来的值
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;
}
// 初始化hash表
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
//就是找到一个数，数是2的幂次方并且大于等于toSize，比如传入的数是13，14或15，那么初始容量就是16
int capacity = roundUpToPowerOf2(toSize);
// 重新记录阈值，阈值=容量* 扩容因子
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
// 添加entry对象
void addEntry(int hash, K key, V value, int bucketIndex) { // bucketIndex数组下标
// 判断的数组的大小是否大于等于阀值
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容后数组长度为之前的2倍
resize(2 * table.length);
// 扩容后重新计算下标
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//若容量足够，则创建1个新的数组元素（Entry） 并放入到数组中
createEntry(hash, key, value, bucketIndex);
}
// 创建Entry对象
void createEntry(int hash, K key, V value, int bucketIndex) {
// 获取原来的oldEntry对象, 如果!=null表示发生hash冲突
Entry<K,V> e = table[bucketIndex];
// 创建新的newEntry对象 并且将新对象作为链表的头结点
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
// 扩容数组
void resize(int newCapacity) {
// 保存旧数组
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 如果数组达到最大容量，return
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建一个新的数组，newCapacity=2 * table.length
Entry[] newTable = new Entry[newCapacity];
// 将旧数组的内容转换到新的数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
// 重新计算阀值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//使我们的hash算法变得更复杂一些，也就是更散列一些，均匀分布，减少hash冲突
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
//将旧表转移到新表中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//变量旧table
for (Entry<K,V> e : table) {
//按旧链表的正序遍历链表
while(null != e) {
//保存旧的哈希表对应的链表头的下一个结点
Entry<K,V> next = e.next;
//重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//重新计算索引
int i = indexFor(e.hash, newCapacity);
//将newTable[i]上的Entry对象（第一次循环null），赋值给当前结点的下一个元素，妙！
e.next = newTable[i];
//将结点赋值到新的哈希表
newTable[i] = e;
e = next;
}
}
}
private static int roundUpToPowerOf2(int number) {
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
//计算key的hash值
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
//一般的hashcode高位都是0，为尽量避免hash冲突，进行扰动处理。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//对table数组长度取模，计算索引
static int indexFor(int h, int length) {
return h & (length-1);
}
小结：
1.hash表是第一次调用put时初始化的，默认容量是16。如果自定义了，也一定是2的n次方，因为要进行容量与hash值取模，获取索引。
2.添加元素，是通过元素hashcode与数组容量取模获取索引的。
3.为均分分布和尽量避免hash冲突，取索引时采用了动扰函数处理。
4.当key为null时，在hash表索引0处。
5.当key重复，新值会覆盖旧值。
6.当传入的初始容量不是2的幂，会取这个值最近的2的幂的值，如传入13，容量会是16。
7.当数组容量到达阈值，会进行扩容，是原来的2倍。
8.扩容会进行rehash，重新计算索引，并进行hash复杂化，使之分布更均匀。
9.如果产生hash冲突，采用链表的方法。
10.hash表中的链表是采用头插的方式。
五.get()方法
public V get(Object key) {
// 判断key是否为null
if (key == null) {
return getForNullKey(); //去table[0]取值
}
//不为null，通过key获取获取对应下标的数组
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 根据key获取hashcode值
int hash = (key == null) ? 0 : hash(key);
// 通过indexFor()计算下标，然后在这个位置上循环单向链表。
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//取得table中hash值一样且key一样的Entity
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
小结：
1.通过key的hash值与容量取模计算出索引，取出元素。
六.remove()方法
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
//如果数组为空，直接返回。
if (size == 0) {
return null;
}
//根据key删除元素,然后再通过indexFor得到要删除的元素所在的位置。
//然后循环，找到要删除元素的key，这里删除使用的是链表出队的方式。
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
//说明不在链表上，删除的是第一个节点
if (prev == e)
table[i] = next;
//说明是删除的是中间节点
else
prev.next = next;
e.recordRemoval(this);
return e;
}
//指向下一个节点，继续循环查找
prev = e;
e = next;
}
return e;
}
七.迭代器
EntrySet 是HashMap中的一个内部类，以Set类型用于保存hash表键值对。
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator(); // 创建迭代器
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry)) // 比较类型
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet()); // entrySet为空时创建一个EntrySet对象
}
HashMap内部有三种迭代器
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
真正的迭代器
// hash迭代器
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
HashIterator() {
expectedModCount = modCount; // 临时存储
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
public final boolean hasNext() {
return next != null;
}
// 每次迭代都会调用次函数得到下一个Entry对象
final Entry<K,V> nextEntry() {
//如果实际修改次数和预期修改次数不一致，抛异常。
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount) // 判断
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
获取方法，见名知意，分别可以迭代不同的东西。
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
八.jdk1.7头插造成死循环
一.死循环
死循环是多线程情况下数组扩容链表头插，引起的单链表循环指向。扩容会rehash重新定位元素的下标，并采用头插法迁移到新数组中。因为是头插，所以会将链表顺序反转，这是造成死循环的根本原因。
二.情景再现
正常扩容后
三.多线程下扩容
现在有线程A和线程B进行扩容，先看扩容关键方法
1.线程A在该处挂起
此时线程A:
新数组索引0处为E，此时e=D，next=A。在元素D即将插入索引2处时，cup执行权被线程B抢。
2.线程B抢到cpu执行权，并正常扩容，并将新数组赋值给table。
由于线程B完成扩容并将自己线程的工作空间内的新数组刷回到主空间HashMap中。此时的主空间HashMap就是B线程扩容后的HashMap。
3.随后线程A获取到了cpu执行权，继续执行newTable[i] = e。此时线程A继续完成该轮循环。
继续执行该轮循环将D完成迁移。但由于e=D，next=A。
4.然后线程A执行，此时e=A，next=B。
线程A继续执行：
5.由于线程B已经将扩容好的新数组刷回了主空间，然后e=B，next=A。
最后线程A刷回主空间，将线程B赋予的值覆盖。
三.jdk1.8
待续。。。
