HashMap详解(基于JDK 1.8)

简介

• Map接口定义了映射关系,有四个常用实现类:
  • HashMap
  • Hashtable
  • LinkedHashMap
  • TreeMap
• HashMap:
  • 根据键key的hashCode值存储数据.
  • 访问速度快,遍历速度较慢.
  • 最多允许一条记录的键为null.
  • 允许多条记录的值为null.
  • 非线程安全.若要线程安全,可使用synchronizedMap或ConcurrentHashMap.
• Hashtable:
  • 继承于Dictionary类.
  • 是线程安全的.
  • 不推荐使用,需要线程安全>ConcurrentHashMap,不需要线程安全>HashMap.
• LinkedHashMap:
  • HashMap的子类.
  • 保存了记录的插入顺序.
  • 遍历顺序准从插入顺序.
• TreeMap:
  • 实现SortedMap接口.
  • 默认按照键值的升序排序.
  • 遍历后的结果是排序后的结果.
  • 使用时key必须实现Comparable接口.
• 所有Map类型的类都要求key为不可变对象,保证创建后哈希值不会发生变化.

内部实现

存储结构

• 每个键值对是由自定义的内部类Node<K,V>保存,一个键值对对应一个结点.
• 而这些键值对是使用数组+链表+红黑树的结构组织起来的.

结点Node<K,V>的属性:

final int hash; // 对应的哈希值
final K key; // 键
V value; // 值
Node<K,V> next; // 指向下一个结点的指针

存储方式

• 使用一个数组Node[] table(哈希桶数组)来存放这些键值对.
• 使用哈希表将这些键值对放在数组的对应位置.
• 为了解决冲突,采用链地址法(数组+链表):每个数组元素都是链表结构,键值对放在链表上.
• Hash碰撞概率小且哈希桶数组占用空间小==>好的Hash算法+扩容机制.

HashMap的一些字段

• int threshold

• final float loadFactor

• int modCount

• int size

• 哈希桶数组的初始化长度为16.

• 负载因子loadFactor的默认值为0.75.

• 哈希桶数组所能容纳的最大键值对个数为threshold,threshold=哈希桶数组长度*负载因子.

• 当存储的键值对个数超过threshold,则需要扩容(扩大为原来的2倍).

• 对时间效率要求高==>降低负载因子.

• 内存空间紧张==>增加负载因子(可大于1).

• size:HashMap中实际存在的键值对个数(哈希桶数组及其对应的链表).

• modCount:记录内部结构发生变化的次数(增加,删除),修改某个key对应的value不属于结构变化.

• 哈希桶数组的长度为2的幂次,目的:为了取模和扩容时优化.减少冲突==>定位时加入高位参与运算.

• 当链表长度太长(超过8),链表转换为红黑树.

具体方法(功能实现)

• 获取哈希桶数组索引位置
• put方法细节
• 扩容过程

确定哈希桶数组索引位置

• 通过hash算法获得键值对对应的位置.
• hash算法:
  • 取key的hashCode值.(h=key.hashCode())
  • 高位运算.(h^(h>>>16))
  • 取模运算.(JDK7)(h&(length-1),等价于h%length,但&运算效率高,length为哈希桶数组的长度)
• 若key为null,则对应的hash值为0.
• JDK8是通过hashCode()的高16位和低16位异或实现.==>对于哈希桶数组大小较小时也能保证高低位都参与hash运算.

put方法流程

1. 判断哈希桶数组table是否为空或null，若是，则resize()进行扩容。
2. 根据键key计算hash值，得到待插入的数组索引i。若为空，则直接插入。并跳转至步骤6；若非空，则向下执行。
3. 判断哈希桶数组中table[i]的首个元素的key是否与待插入的key一致，若相同，则直接覆盖，否则向下执行。
4. 判断table[i]是否为treeNode(即判断待插入的位置是使用红黑树还是链表保存键值对)，若是红黑树，则在树中插入键值对。
5. 若不是红黑树，则判断链表长度是否大于8，若大于，则将链表转为红黑树，在树中插入键值对。否则在链表中插入键值对。(遍历链表时，若发现key重复，则直接覆盖，从而完成插入)
6. 插入成功后，判断实际存在的键值对数量size是否超过最大容量threshold，若超过，则进行扩容。

注：

• JDK 1.7的插入是头插入，即：同一位置上的新键值对总会被放在链表的头部位置。
• JDK 1.8的插入是尾插入，则遍历链表，直到最后一个元素，将新的键值对放在链表的尾部。

扩容机制

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取旧桶的大小
        int oldThr = threshold; // 获得旧的threshold
        int newCap, newThr = 0;
        if (oldCap > 0) { // 若旧桶的大小大于0
            if (oldCap >= MAXIMUM_CAPACITY) { // 若旧的threshold大于2^29，则直接设为最大值，并返回
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY) // 否则，若旧的threshold大于16，而加倍后仍然小于2^29
                newThr = oldThr << 1; // double threshold // 则加倍
        }
        else if (oldThr > 0) // 若旧的threshold大于0，则threshold不进行改变
            newCap = oldThr;
        else {               // 以上条件都不满足，则桶的大小设为16，threshold设为12
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) { // 计算新的桶大小对应的新的threshold
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr; // 设置threshold，使之生效
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab; // 创建新桶
        if (oldTab != null) { // 若旧的桶非空，则需要将其中的键值对迁移到新桶中
            for (int j = 0; j < oldCap; ++j) { // 对于哈希桶数组中的每个元素进行检查
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { // 若数组当前位置有键值对，则需要处理，否则直接到一个数组元素
                    oldTab[j] = null; //旧桶设为null，方便GC
                    if (e.next == null) // 若当前位置上只有一个元素，则直接将其迁移到新数组的新位置（经过hash计算）
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode) // 若当前位置是以红黑树方式存储键值对，则对红黑树分裂
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // 若是链表，则将旧的链表分裂成两个新的链表
                        Node<K,V> loHead = null, loTail = null; // 此链表的键值存放在原来的位置
                        Node<K,V> hiHead = null, hiTail = null; // 此链表的键值对放在新位置(旧的位置+旧的桶大小)
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) { // 存放在旧位置上的键值对
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { // 存放在新位置上的键值对
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) { // 分裂的链表1放在旧的位置上
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) { // 分裂的链表2放在新的位置上
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

JDK 1.8在扩容机制上的关键点：

• 扩容后是原来的两倍，所以一个键值对要么在原来位置，要么在(旧位置+旧的桶的容量).
• 所以在扩容时对元素进行迁移时，无需重新计算hash值，而是判断新容量非零的最高位上，键值对的hash值是0还是1：为0，则在原位置；为1，则在新位置。
• 减少了计算hash值的时间，并且可以认为该位上0，1分布是随机的，可以减少冲突。
• JDK 1.7在元素迁移时，迁移到新位置的元素与其在旧位置上的顺序相反（头插法导致原来的在前的元素先插入到新位置，位置在后的元素后插入，后插入的元素在链表前）

遍历方式

两种遍历HashMap的方式:

// 第一种方式:将key 和 value 同时取出
Iterator<Map.Entry<String,Integer>> entryIterator = map.entrySet().iterator();
while(entryIterator.hasNext()){
    Map.Entry<String,Integer> next = entryIterator.next();
}

// 第二种方式:将key取出,若要value,还需通过key遍历一遍
Iterator<String> iterator = map.keySet().iterator();
while(iterator.hasNext()){
    String key = iterator.next();
}

JDK1.8中的HashMap

• 使用数组+链表的方式.
• 默认大小16,负载因子0.75.
• 当hash冲突严重时,桶上的链表越来越长,查询效率越来越低,时间复杂度为O(N).
• 扩容方法resize()在并发执行时容易在桶上形成环形链表.

线程安全性

• HashMap不是线程安全的，多线程应用避免使用。
• 线程安全可使用ConcurrentHashMap。
• JDK 1.7中resize()可能导致环形链表从而产生死锁（执行resize()方法的线程无法退出）
• JDK 1.8进行了改进，是设置两个链表（局部变量），将旧链表上的键值对分别复制到两个新链表上，再将两个新链表迁移到新桶上。
• JDK 1.8不会因为扩容而导致死锁，但是存在其他原因导致的死锁

小结

1. 扩容是一个特别耗性能的操作，所以当使用HashMap，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
2. 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
3. HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
4. JDK1.8引入红黑树大程度优化了HashMap的性能。

参考:

• Java 8系列之重新认识HashMap

原文：https://www.cnblogs.com/truestoriesavici01/p/13216222.html