一、基本介绍

  • HashMap是一个散列表，其主要作用是来存放键值对的映射。
  • 其实现了Map、Cloneable、Serializable接口，继承了AbstractMap类
  • HashMap是线程不安全的，线程安全的有HashTable和ConcurrentHashMap。但是HashTable基本被淘汰，因为它内部的方法都被synchronized修饰过了，所以其效率会比HashMap低很多。同时HashTable的并发性也不如ConcurrentHashMap，因为ConcurrentHashMap采用的是分段锁的思想。

  • HashMap的key跟value都可以为null，但是key只能有一个。

    二、底层数据结构

  • 数组 + 链表

数组结构的声明：
transient Node<K,V>[] table;
Node类含有的属性：

  1. final int hash; //key的hash值
  2. final K key;
  3. V value;
  4. Node<K,V> next;//指向下一个节点的指针

三、HashMap的参数介绍

  1. int initialCapacity ：初始化容量

默认初始化容量为16，之后每次扩容都会扩容为原来的两倍
如果指定了初始容量，

  1. final float loadFactor ：负载因子

默认值是0.75

  1. int threshold ：阈值

threshold = loadFactor * initCapacity

  1. int size ：当前map中实际键值对对数量

当size > threshold时，就会调用resize()方法进行扩容

四、初始化过程

  1. 调用无参构造器初始化

    1. public HashMap() {
    2.  //负载因子设置为默认值
    3.  this.loadFactor = DEFAULT_LOAD_FACTOR; 
    4. }

  2. 调用有参构造器初始化 ```java //初始化容量 public HashMap(int initialCapacity) { //会调用另外一个构造器初始化 this(initialCapacity, DEFAULT_LOAD_FACTOR); } //初始化容量和负载因子 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)

    1.  throw new IllegalArgumentException("Illegal initial capacity: " +
    2.                                     initialCapacity);

    //容量大于2^30时，会将容量设置为2^30 if (initialCapacity > MAXIMUM_CAPACITY)

    1.  initialCapacity = MAXIMUM_CAPACITY;

    //isNaN，NaN = Not a Number，传入的float可能不是一个数字 //float = 0.0f / 0.0f时不会报错 if (loadFactor <= 0 || Float.isNaN(loadFactor))

    1.  throw new IllegalArgumentException("Illegal load factor: " +
    2.                                     loadFactor);

    this.loadFactor = loadFactor; //此处将阈值设为了大于等于initialCapacity的最小的2的幂次方 //整个初始化过程，并没有设置容量参数 this.threshold = tableSizeFor(initialCapacity); } /**

  • Returns a power of two size for the given target capacity. */ 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; } ```

    五、插入过程

    ```java //put方法 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

//hash方法，目的是为了防止传入对象的hash方法实现较差，这里做一个扰动 static final int hash(Object key) { int h; //会调用对象的hashCode方法，再进行扰动 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

//putVal方法 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //table是map中存放Node节点的数组 //第一次put操作时，table为null，启动扩容操作 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //其中n为当前map的容量 //通过(n - 1) & hash算出当前节点应该放入的位置，并获取到数组中该节点的值 //n为2的幂次方，例如16 = 0001 0000； 15 = 0000 1111；由于高位全为0，低位全为1，所以(n - 1) & hash 等价于 hash % n //扩展，(n - 1) & n 可以消除掉n中的一个1，通过循环可以求解出一个数2进制中1的个数 //如果当前位置没有节点，就直接放入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; //先判断hash值是否相等，再判断key对象是否一致，再判断key不等于null的情况下，key中的内容是否与数组中的元素内容相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断数组中的节点是否属于TreeNode类型，就是看该节点是否以及变成了红黑树 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { //遍历链表中的所有节点 for (int binCount = 0; ; ++binCount) { //如果遍历到链表尾部 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //当该节点为第8个节点时，会触发将当前连标的节点转化为红黑树 //但是如果当前的map容量小于64时，不会触发链表转换成红黑树，而是选择扩容操作。 //因为此时的hash碰撞率高的原因很大一部分是应为数组容量过小 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //如果当前size大于阈值，那么就触发扩容操作 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

```

六、扩容过程

  1. HashMap每次扩容都会将容量扩大为原来的2倍，HashMap的容量最大为2^30，因为int型的最大值为2^31 - 1。

  2. 由于通过构造函数初始化时，并没有设置初始容量，而是将阈值设为了我们传入的初始容量参数。这些都会在第一次扩容操作时，设置好容量，并将阈值设置为capacity * loadFactor

    七、使用注意点

  3. 如果提前知道了会往HashMap中存放的元素数量，可以事先定义好HashMap的容量，可以避免频繁扩容导致的性能下降。

  4. 如果知道预期会使用的容量大小expectedCapacity，可以通过(expectedCapacity / loadFactor) + 1计算出应该将初始容量设置为多少，如果不确定初始值大小，就设置16。

例如想放12个元素，那么（12 / 0.75）+ 1 = 17，HashMap最终会创建一个容量为32的数组，虽然浪费了空间，但是不会因为扩容而损失性能，不过HashMap本身就是一个空间换时间的结构。