HashMap

  • HashMap类使用散列表实现Map接口并扩展AbstractMap。HashMap采用哈希算法实现， 底层采用了哈希表存储数据。
  • HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。
  • HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null。
  • HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。
  • 如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap

1.8前

  • 构造方法执行的时候会创建一个长度为16的数组Entry[] table，用来存储键值对的数据

1.8后

  • 构造方法执行的时候会创建一个空的数据，在Put方法执行后通过扩容来判断是否扩容数组Node[] table名字没变 ```java HashMap的构造方法：

HashMap() //构造一个默认的散列映射 HashMap(Map<? extends K, ? extends V> m) //用m的元素初始化散列映射 HashMap(int initialCapacity) //初始化散列映射容量 HashMap(int initialCapacity, float loadFactor) //初始化散列映射的容量和填充比

填充比：它决定在散列映射向上调整大小之前，有多少能被充满。 具体说，就是当 元素个数 > 散列映射容量*填充比 时，散列映射被扩大。 没有获得填充比，默认使用0.75。

  1. 注：散列映射并不保证它的元素的顺序。因此，元素加入散列映射的顺序不一定是它们被迭代方法读出的顺序
  5. **HashMap与HashTable的区别**<br />     1. HashMap: 线程不安全，效率高。允许key或value为null。<br />     2. HashTable: 线程安全，效率低。不允许key或value为null。
  7. <a name="gOYUr"></a>
  8. ## 基本方法
  9. <a name="yf85T"></a>
  10. ### 1.存储数据过程put(key,value)
  12. 首先会将传入的 Key 做 `hash` 运算计算出 hashcode，然后根据数组长度取模计算出在数组中的 index 下标。
  14. 由于在计算中位运算比取模运算效率高的多，所以 HashMap 规定数组的长度为 `2^n` 。这样用 `2^n - 1` 做位运算与取模效果一致，并且效率还要高出许多。
  16. 由于数组的长度有限，所以难免会出现不同的 Key 通过运算得到的 index 相同，这种情况可以利用**链表**来解决，HashMap 会在 `table[index]`处形成链表，1.7 采用**头插法**将数据插入到链表中（**1.8是尾插法**）。
  17. ```java
  18. public V put(K key, V value) {
  19.         return putVal(hash(key), key, value, false, true);
  20.     }
  21. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
  22.         //tab=初始map数组;n=初始map数组得长度
  23.         //p=hash计算后map数组;i=hash计算后map数组下标位置
  24.         Node<K,V>[] tab; Node<K,V> p; int n, i;
  25.         if ((tab = table) == null || (n = tab.length) == 0)
  26.             //初始化扩容
  27.             n = (tab = resize()).length;
  28.         //计算下标 将数据 赋值给 p  (hash计算后map数组)
  29.         //1、当前下标无数据 
  30.         if ((p = tab[i = (n - 1) & hash]) == null)
  31.             //新建Node数组 赋值 给 tab数组
  32.             tab[i] = newNode(hash, key, value, null);
  33.         else {
  34.             //当前hash在Node中的位置 
  35.             Node<K,V> e; K k;
  36.             // hash 相等 && key 相等
  37.             if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
  38.                 //当前hash在Node中的位置 
  39.                 e = p;
  40.             //如果 p得类型是树节点
  41.             else if (p instanceof TreeNode)
  42.                 //添加到树节点中
  43.                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  44.             else {
  45.              //1、 当前下标有数据
  46.                 //如果 不是树节点 并且当前key 不重复 遍历插入
  47.                 for (int binCount = 0; ; ++binCount) {
  48.                     //下一个引用node 是空的
  49.                     if ((e = p.next) == null) {
  50.                         //遍历插入到 p Node节点中
  51.                         p.next = newNode(hash, key, value, null);
  52.                         //如果长度>=  (8-1)
  53.                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  54.                             //转红黑树
  55.                             treeifyBin(tab, hash);
  56.                         break;
  57.                     }
  58.                     //下一个引用不是空的；hash 和 key 相同  跳出当前循环
  59.                     if (e.hash == hash &&((k = e.key) == key || 
  60.                                           (key != null && key.equals(k))))
  61.                         break;
  62.                     //下一个引用不是空的； ash 和 key 不相同
  63.                     p = e;
  64.                 }
  65.             }
  66.             //如果 链表下一个 不是空的 但是 key 存在时，将现有得 节点加入到最后
  67.             //e不为空表示存在相同的key，替换value并返回旧值
  68.             if (e != null) { // existing mapping for key
  69.                 V oldValue = e.value;
  70.                 if (!onlyIfAbsent || oldValue == null)
  71.                     e.value = value;
  72.                 afterNodeAccess(e);
  73.                 return oldValue;
  74.             }
  75.         }
  76.         ++modCount;
  77.         //链表元素增加，并判断是否大于阈值，如果大于，则扩容
  78.         if (++size > threshold)
  79.             resize();
  80.         afterNodeInsertion(evict);
  81.         return null;
  82.     }
  85. // Create a regular (non-tree) node
  86.     Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
  87.         return new Node<>(hash, key, value, next);
  88.     }
  90.  final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
  91.                                        int h, K k, V v) {
  92.             Class<?> kc = null;
  93.             boolean searched = false;
  94.             TreeNode<K,V> root = (parent != null) ? root() : this;
  95.             for (TreeNode<K,V> p = root;;) {
  96.                 int dir, ph; K pk;
  97.                 if ((ph = p.hash) > h)
  98.                     dir = -1;
  99.                 else if (ph < h)
  100.                     dir = 1;
  101.                 else if ((pk = p.key) == k || (k != null && k.equals(pk)))
  102.                     return p;
  103.                 else if ((kc == null &&
  104.                           (kc = comparableClassFor(k)) == null) ||
  105.                          (dir = compareComparables(kc, k, pk)) == 0) {
  106.                     if (!searched) {
  107.                         TreeNode<K,V> q, ch;
  108.                         searched = true;
  109.                         if (((ch = p.left) != null &&
  110.                              (q = ch.find(h, k, kc)) != null) ||
  111.                             ((ch = p.right) != null &&
  112.                              (q = ch.find(h, k, kc)) != null))
  113.                             return q;
  114.                     }
  115.                     dir = tieBreakOrder(k, pk);
  116.                 }
  118.                 TreeNode<K,V> xp = p;
  119.                 if ((p = (dir <= 0) ? p.left : p.right) == null) {
  120.                     Node<K,V> xpn = xp.next;
  121.                     TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
  122.                     if (dir <= 0)
  123.                         xp.left = x;
  124.                     else
  125.                         xp.right = x;
  126.                     xp.next = x;
  127.                     x.parent = x.prev = xp;
  128.                     if (xpn != null)
  129.                         ((TreeNode<K,V>)xpn).prev = x;
  130.                     moveRootToFront(tab, balanceInsertion(root, x));
  131.                     return null;
  132.                 }
  133.             }
  134.         }

2.遍历方法

  1. Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
  2. while (entryIterator.hasNext()) {
  3.   Map.Entry<String, Integer> next = entryIterator.next();
  4.   System.out.println("key=" + next.getKey() + " value=" + next.getValue());
  5. }
  1. Iterator<String> iterator = map.keySet().iterator();
  2. while (iterator.hasNext()){
  3.   String key = iterator.next();
  4.   System.out.println("key=" + key + " value=" + map.get(key));
  5. }
  1. map.forEach((key,value)->{
  2.     System.out.println("key=" + key + " value=" + value);
  3. });

强烈建议使用第一种 EntrySet 进行遍历。
第一种可以把 key value 同时取出，第二种还得需要通过 key 取一次 value，效率较低, 第三种需要 JDK1.8 以上，通过外层遍历 table，内层遍历链表或红黑树。

HashMap底层实现

HashMap底层实现采用了 数组+单向链表+红黑树
数据结构中由数组和链表来实现对数据的存储，他们各有特点。
(1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。
(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。
结合数组和链表的优点(即查询快，增删效率也高)=“哈希表”。 哈希表的本质就是“数组+链表”。

1. 存储结构

内部包含了一个 Entry 类型的数组 table。

  1. // HashMap的核心数组结构，也称之为“位桶数组”
  2. transient Entry[] table;

一个Entry对象存储了：
1. key：键对象
2.value：值对象
3. next:下一个节点
4. hash: 键对象的hash值
其中有两个重要的参数：

  • 容量（capacity），始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍
  • 负载因子（loadFactor）

容量的默认大小是 16，负载因子是 0.75，当 HashMap 的 size > 16*0.75 时就会发生扩容(容量和负载因子都可以自由调整)。

显然每一个Entry对象就是一个单向链表结构。
数组中的每个位置被当成一个桶，一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值相同的 Entry。
image.png

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.     //包含了四个字段
  3.         final int hash;
  4.         final K key;
  5.         V value;
  6.     //next指向下一个节点，说明是链表结构
  7.         Node<K,V> next;
  9.         Node(int hash, K key, V value, Node<K,V> next) {
  10.             this.hash = hash;
  11.             this.key = key;
  12.             this.value = value;
  13.             this.next = next;
  14.         }
  16.         public final K getKey()        { return key; }
  17.         public final V getValue()      { return value; }
  18.         public final String toString() { return key + "=" + value; }
  20.         public final int hashCode() {
  21.             return Objects.hashCode(key) ^ Objects.hashCode(value);
  22.         }
  24.         public final V setValue(V newValue) {
  25.             V oldValue = value;
  26.             value = newValue;
  27.             return oldValue;
  28.         }
  30.         public final boolean equals(Object o) {
  31.             if (o == this)
  32.                 return true;
  33.             if (o instanceof Map.Entry) {
  34.                 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
  35.                 if (Objects.equals(key, e.getKey()) &&
  36.                     Objects.equals(value, e.getValue()))
  37.                     return true;
  38.             }
  39.             return false;
  40.         }
  41.     }

2. 拉链法的工作原理

  1. HashMap<String, String> map = new HashMap<>();
  2. map.put("K1", "V1");
  3. map.put("K2", "V2");
  4. map.put("K3", "V3");
  • 新建一个 HashMap，默认大小为 16；
  • 插入 键值对，先计算 K1 的 hashCode 为 115，使用除留余数法得到所在的桶下标 115%16=3。
  • 插入 键值对，先计算 K2 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6。
  • 插入 键值对，先计算 K3 的 hashCode 为 118，使用除留余数法得到所在的桶下标 118%16=6，插在 后面。

应该注意到是 1.7 采用头插法将数据插入到链表中（1.8是尾插法）方式进行链表的插入

查找需要分成两步进行：

  • 计算键值对所在的桶
  • 在链表上顺序查找，时间复杂度显然和链表的长度成正比

    3.hash

    1. static final int hash(Object key) {
    2.       int h;
    3.       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    4.   }
    5. public final int hashCode() {
    6.           return Objects.hashCode(key) ^ Objects.hashCode(value);
    7.       }

    4.扩容

    除了初始化的时候会指定 HashMap 的容量，在进行扩容的时候，其容量也可能会改变。HashMap 有扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件就是当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。

在 HashMap 中，threshold = loadFactor * capacity。loadFactor 是装载因子，表示 HashMap 满的程度，默认值为 0.75f，设置成 0.75 有一个好处，那就是 0.75 正好是 3/4，而 capacity 又是 2 的幂。所以，两个数的乘积都是整数。

对于一个默认的 HashMap 来说，默认情况下，当其 size 大于 12(16*0.75) 时就会触发扩容。下面是 HashMap 中的扩容方法(resize)中的一段：

  1. if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  3.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  5.     newThr = oldThr << 1; // double threshold
  6. }

从上面代码可以看出，扩容后的 table 大小变为原来的两倍，这一步执行之后，就会进行扩容后 table 的调整，这部分非本文重点，省略。

可见，当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容，扩容成原容量的2倍，即从16扩容到32、64、128 …

所以，通过保证初始化容量均为 2 的幂，并且扩容时也是扩容到之前容量的2倍，所以，保证了 HashMap 的容量永远都是2的幂。

5.链表转换红黑树

根据泊松分布，在负载因子默认为 0.75 的时候，单个 hash 槽内元素个数为 8 的概率小于百万分之一，所以将7作为一个分水岭，等于 7 的时候不转换，大于等于 8 的时候才进行转换，小于等于 6 的时候就化为链表。

与 HashTable 的比较

  • HashMap 是非线程安全的，HashTable 使用 synchronized 来进行同步，是线程安全的。
  • HashMap 要比 HashTable 效率高一点。Hashtable 基本被淘汰，不要在代码中使用它。
  • HashMap 可以插入键为 null 的 Entry；HashTable 中插入的键只要有一个为 null，直接抛出 NullPointerException。
  • HashMap 的迭代器是 fail-fast 迭代器。
  • HashMap 不能保证随着时间的推移 Map 中的元素次序是不变的。
  • HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间；Hashtable 没有这样的机制。
  • HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍；Hashtable 容量默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。在初始化时如果给定了容量初始值，HashMap 会将其扩充为2的幂次方大小；Hashtable 会直接使用初始值。

    与 HashSet 的比较

    HashSet 底层就是基于HashMap实现的。(HashSet 的源码非常非常少，因为除了 clone() 方法、writeObject()方法、readObject()方法是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。)
HashMap HashSet
HashMap实现了Map接口 HashSet实现了Set接口
HashMap储存键值对 HashSet存储对象
调用put()向map中添加元素 调用add()方法向Set中添加元素
HashMap使用键（Key）计算Hashcode HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false
HashMap相对于HashSet较快，因为它是使用唯一的键获取对象 HashSet较HashMap来说比较慢