HashMap的数据结构是数组和链表+】红黑树【】JDK1.8后新加入，当链表的长度大于8时，转换为红黑树】的结合体。

数组：存储区间连续，内存占用严重。寻址容易，插入和删除困难。

链表：存储区间离散，内存占用宽松。寻址困难，插入和删除容易。

HashMap的特性：

• 采用键值对的形式存储
• 是非线程安全的
• 可以接受null的键和null的值,HashMap最多只允许一条记录的键为null，允许多条记录的值为null

HashMap的实现原理：

HashMap使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

HashMap是基于hashing的原理，使用put(key, vlaue)存储到HashMap对象中，使用get(key)从HashMap中获取对象。当使用put()传递键和值的时候，先对键调用hashCode()方法，通过返回的bucket位置来存储Node对象。需要注意的是：bucket中存储的键对象和值对象。

具体实现如下：

int hash = key.hashCode();

实际中HashMap不采用这种处理形式，因为模运算的消耗还是比较大的，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率

int index = hash % Node[].length; 

Node[index] = value;

此时会引发一个问题：当计算的hash值是一样的话，产生的index就会一样，此时如何存储？

HashMap源码可知：新建HashMap的时候，初始化一个数组，通过next指向下一个元素的引用从而构成链表。

transient Node<K,V>[] table;

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;
    }
}

从上面的源码中可以看到，链表中通过next来指向下一个引用来组成链接。

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。

当存储的对象的hashCode是一致的时候，说明此时对应的是同一个bucket，用例子来说明：

首先A存储到HashMap中，此时A的index为0，即：Node[0] = A;

这时B也进入，B的hashCode和A的相同，此时 Node[0] = B; B.next = A;

从而以此类推组成链表，新进入的放在链表的头部，后面一次通过next来连接。