1.HashMap的数据结构

由数组和链表实现

数组：
数组存储区间是连续的，占用内存严重，故时间复杂度大。但数组的二分时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；

链表：
链表存储区间离散，占用内存比较宽松，故空间复杂度小，时间复杂度大，达O(N)。链表的特点是：寻址困难，插入和删除比较容易。

哈希表（Hash Table）
结合数组和链表的特点，做出寻址容易，插入和删除也容易.

哈希表有多种不同的实现方法，下面是常用的拉链法，如图：
![Uploading QQ图片20170516092933_183614.png . . .]

从上图可见，哈希表是由数组和链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。比如12%16=12,28%16=12,108%16=12,140%16=12,16为数组的长度，hash(key)%len=数组的index

HashMap里面实现一个静态内部类Map.Entry，其重要的属性有key,value,next,从属性key，value我们就能看出Entry就是HashMap键值对实现的一个基础的bean，并持有一个指向下一个数组的引用，构成了链表。我们上面说的HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面保存的内容都保存在Entry[]里面。

/** 
 * The table, resized as necessary. Length MUST Always be a power of two. 
 */  
transient Entry[] table;

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
...
}

transient声明是个实例变量，当对象存储时，它不需要维持。transient关键字标记的成员变量不需要序列化过程。

2.HashMap的存储实现

1）put存储

疑问：如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？
　　这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

public V put(K key, V value) {
        //HashMap允许存放null键和null值
        //当key为null时，调用putForKey方法，将value放置在数组第一个位置。
        if (key == null)
            return putForNullKey(value);
        //根据key的keyCode重新计算hash值
        int hash = hash(key.hashCode());
        //搜索指定hash值在对应table中的索引
        int i = indexFor(hash, table.length);
        //如果i索引处的Entry不为null，通过循环不断遍历e元素的下一个元素
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            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;
            }
        }
        //如果i索引处的Entry为null，表明此处还没有Entry。
        modCount++;
        //将key、value添加到索引处
        addEntry(hash, key, value, i);
        return null;
    }

从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

void addEntry(int hash, K key, V value, int bucketIndex) {
             // 获取指定 bucketIndex 索引处的 Entry 
        Entry<K, V> e = table[bucketIndex];
             // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
        table[bucketIndex] = new Entry<K, V>(hash, key, value, e); // 参数e是Entry.next
             // 如果 Map 中的 key-value 对的数量超过了极限 
        if (size++ >= threshold)
             // 把 table 对象的长度扩充到原来的2倍。
            resize(2 * table.length);

    }

HashMap里面包含一些优化方面的实现，比如，Entry[]长度一定后，随着map数据的越来越长，这样同一个index的链就睡很长，会不会影响性能？HashMap里面设置一个因子，随着map的size越来越大，Entry[]会以一定的规则加长长度。

static int indexFor(int hash, int length){
        return hash ＆ (length-1)

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

在 HashMap 构造器中有如下代码：

int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;  

这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方。

2）get

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        //先定位到数组元素，再遍历该元素处的链表
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
}

归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。