• 是基于哈希表的Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null 值和null 键(允许一个null键，HashTable不允许entry的键或者值为空)。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

基本结构

HashMap基本原理

• HashMap 有一个 Node<K,V>[] table 字段，即哈希桶数组，数组元素是 Node 对象，结构定义如下：

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash; // 用于计算数组索引
  final K key;
  V value;
  Node<K,V> next; // 后继节点，下一个 Node

  Node(int hash, K key, V value, Node<K,V> next) { ... }
  ...
}

• 哈希桶数组会在首次使用时初始化，默认大小是 16，并根据需要调整大小，且长度总是 2 的次幂。如果构造函数设置的初始容量不是 2 的次幂，那么使用以下方法返回一个大于且最靠近它的 2 的次幂的值：

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

• 影响 HashMap 性能的主要参数是：初始容量和负载因子。当散列表元素数超过负载因子和当前容量的乘积时，就会扩容，扩大到原来容量的两倍，并对键重新散列。
• 负载因子默认值是 0.75f，它是对时间和空间成本的一个很好的平衡，一般不用修改，较高的值会减少空间开销，但会增加查找的成本
• 初始容量过小会多次触发扩容和 rehash，所以预分配一个足够大的容量更加有效
• 不管多么合理的散列算法，也免不了链表过长的情况，从而影响 HashMap 的性能，所以，JDK8 在链表长度大于 8 时，将其转为红黑树，以利用红黑树快速增删改查的特点。

HashMap存储结构

• 其实简单的说HashMap的存储结构是由数组和链表共同完成的。

  
  

• 从上图可以看出HashMap是Y轴方向是数组，X轴方向就是链表的存储方式。

• 大家都知道数组的存储方式在内存的地址是连续的，大小固定，一旦分配不能被其他引用占用。它的特点是查询快，时间复杂度是O(1)，插入和删除的操作比较慢，时间复杂度是O(n)，链表的存储方式是非连续的，大小不固定，特点与数组相反，插入和删除快，查询速度慢。

• HashMap 基于散列表实现，使用拉链法处理碰撞，在 JDK8 中，当链表长度大于 8 时转为红黑树存储，基本结构如下：

  
  1424165-20190522103933300-1239362962.png

---

构造函数

// 默认的无参构造函数
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     * 
     * 初始容量 内部源码计算 大于当前 initialCapacity 的最小2n次方 
     * 默认的是16 
     * 例如传入的是5 那么初始的容量是8（2的3次方）
     */
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity 
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     * 
     *  第一个参数 默认容量
     *  第二个参数附载因子 默认的是0.75 （超过75%的容量就扩容）
     */
     public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

---

put

put 操作主要做了以下几件事：

• 哈希桶数组 table 为空时，通过 resize() 方法进行初始化
• 待插入的 key 已存在，直接覆盖 value
• 若不存在，将键值对插入到对应的链表或红黑树中
• 插入链表时判断是否转红黑树
• 判断是否需要扩容

---

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的hash存在的时候，进入了循环，恰恰这个时候，另外一个线程将这个Entry删除了，那么你就一直因为找不到Entry而出现死循环，最后导致的结果就是代码效率很低，CPU特别高。一定记住。

HashMap的size()解析

• HashMap的大小很简单，不是实时计算的，而是每次新增加Entry的时候，size就递增。删除的时候就递减。空间换时间的做法。因为它不是线程安全的。完全可以这么做。效力高。

HashMap的reSize()解析

• 当HashMap的大小超过临界值的时候，就需要扩充HashMap的容量了。代码如下：

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

• 从代码可以看出，如果大小超过最大容量就返回。否则就new 一个新的Entry数组，长度为旧的Entry数组长度的两倍。然后将旧的Entry[]复制到新的Entry[].代码如下：

void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

---

遍历

---

线程安全问题

• HashMap的put和get方法分析可得，put和get方法真实操作的都是Entry[] table这个数组，而所有操作都没有进行同步处理，所以HashMap是线程不安全的。如果想要实现线程安全，推荐使用ConcurrentHashMap。

总结

• HashMap是基于哈希表实现的，用Entry[]来存储数据，而Entry中封装了key、value、hash以及Entry类型的next
• HashMap存储数据是无序的
• hash冲突是通过拉链法解决的
• HashMap的容量永远为2的幂次方，有利于哈希表的散列
• HashMap不支持存储多个相同的key，且只保存一个key为null的值，多个会覆盖
• put过程，是先通过key算出hash，然后用hash算出应该存储在table中的index，然后遍历table[index]，看是否有相同的key存在，存在，则更新value；不存在则插入到table[index]单向链表的表头，时间复杂度为O(n)
• get过程，通过key算出hash，然后用hash算出应该存储在table中的index，然后遍历table[index]，然后比对key，找到相同的key，则取出其value，时间复杂度为O(n)
• HashMap是线程不安全的，如果有线程安全需求，推荐使用ConcurrentHashMap。