Java集合类学习（一）HashMap的实现原理

HashMap介绍

HashMap是基于哈希表的Map接口的非同步实现，提供所有可选的映射操作，并允许使用null值和null键，不保证映射的顺序，特别是它不保证该顺序恒久不变

HashMap的数据结构

在java编程语言中，最基本的结构就是两种，一个是数组，另一个是模拟指针（引用），所有的数据结构都可以用这个基本结果来构造，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，这是数组和链表的结合体，如下图所示
Java集合类学习（一）HashMap的实现原理

源代码

  //存储Node的数组
  transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//对key的hashcode值进行hash运算后得到的值，存储在Node，避免重复计算
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;
        }
        }

HashMap的存取实现

（1）存储

  public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
//根据key的keyCode重新计算hash值
int hash = hash(key.hasCode());
//搜索指定hash值在对应table中索引
int i = indexFor(hash, table.length);
//如果i索引处的Entry不为null，通过循环不断遍历e元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
            Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
return oldValue;
            }
        }
        modCount++;//modCount指修改次数
//将key、value添加到i索引处
        addEntry(hash, key, value, i);
return null;
    }

就首先按照hash值（即下标）存储数组，如果发生哈希冲突（hash值相同），就在这个位置上的元素以链表的形式存储，新元素存储在头链头，HashMap中链表出现越少性能越好。

1、addEntry（）方法

void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//如果Map的key-value对的数量超过了极限，就把table对象的长度扩充到原来的2倍
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

void addEntry(int hash, K key, V value, int bucketIndex) 方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry是HashMap提供的一个包访问权限（就friendly，当前包才权限访问）的方法
从源码看出，当系统决定存储HashMap中key-value对时，是只考虑key的，而value是key的附属，key去哪value就去哪。

2、hash（）方法

//这是一个神奇的函数，用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {

        h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
    }

3、indexFor（）方法

 static int indexFor(int h, int length) {
return h & (length-1);
    }

这个方法通过 h & (length-1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化， h & (length-1)运算等价对length取模，也就h%length，但是&比%具有更高的效率。

（2）读取

 public V get(Object key) {
　　　　 //如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
        Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
 }

HashMap的resize（rehash）

当HashMap中元素越来越多，hash冲突的概率就越来越大，为了提高查询效率，就对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的情况就是：原数组中的数据必须重新计算其在新数组的位置，并放进去，这也就是resize
当HashMap中的元素个数超过数组大小length*loadFactor就进行扩容，loadFactor默认值是0.75，也就是数组大小16，当HashMap中元素个数超过16
*0.75=12的时候就进行扩容。扩展到16 *2=32，然后重新计算其在新数组的位置

HashMap的性能参数

HashMap()
构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap。
HashMap(int initialCapacity)
构造一个带指定初始容量和默认加载因子 (0.75) 的空HashMap。
HashMap(int initialCapacity, float loadFactor)
构造一个带指定初始容量和加载因子的空HashMap。

Fail-Fast机制

我们知道HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么抛出ConcurrentModificationException,这就是fail-fast策略

HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

在迭代过程，判断modCount和expectedModCount 是否相等，如果不相等就表示已经有其他线程修改Map
注意modCount声明为volatile，保证线程之间修改的可见性

秒客网