数据结构之【 HashMap 】

HashMap是在开发过程中必用的存储结构，也是面试过程中经常问到的技能点。本章在这里介绍下HashMap在JDK8中的底层原理以及记录下常见的面试问题。

名称解释

Hash：

一般翻译为散列，直译为哈希

Hashing: 散列法

把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。是一种典型的“空间换时间”的做法。

负载因子

比如我们存储70个元素，但我们可能为这70个元素申请了100个元素的空间。70/100=0.7，这个数字称为负载因子

哈希冲突（碰撞）

由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突
解决方案：开放寻址法、拉链法。HashMap处理方案就是拉链法

数据结构存储图示

源码说明（JDK1.8）

类声明

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {...}

类属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;             // 默认的初始化容量 2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30;                    // 最大容量  2^30=1073741824
static final float DEFAULT_LOAD_FACTOR = 0.75f;                 // 默认负载因子 0.75
static final int TREEIFY_THRESHOLD = 8;                         // 存储结构转链表结构转换为树状结构的阈值 =8
static final int UNTREEIFY_THRESHOLD = 6;                       // 存储结构由树状结构转换为链表结构的阈值=6 
static final int MIN_TREEIFY_CAPACITY = 64;                     // 树状结构的最小容量=64   

int threshold;                                                  // 阈值,当实际大小（容量*负载因子）大于该值时会进行扩容
final float loadFactor;                                         // 负载因子
transient int size;                                             // 存储元素总数
transient int modCount;                                         // 被修改的次数（用于fast-fail机制）

初始化

// 使用指定初始容量以及负载因子来初始化，参数均可使用默认值
public HashMap(int initialCapacity, float loadFactor) {
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);  // 返回比输出值大的最近的2的整数次幂运算值，例如11的最近是16
}


// 使用Map数据来初始化
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

hash算法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

散列值理论上是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int表值范围从-2147483648到2147483648。前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
Object.hashCode（）
是一个Native方法，使用和当前线程相关的随机数和其他值最终通过Marsaglia's xorshift scheme随机算法产生一个随机数
hashCode无符号右移16位，即先将32位的int的低位舍弃，高位补0，然后再与hashCode进行（位）异或运算，使得高位不受影响，低位与高位进行运算（这部分为扰动，真正参与运算的还是低位）

Put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);  // 先对key进行了一次Hash运算
}

链表节点属性

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
      ...
}

树状节点属性：是链表节点的子类

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    ...
}

// LinkedHashMap.Entry与HashMap.Node是继承关系
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

具体细节

/**
 * @param hash            key的hash值
 * @param key             the key
 * @param value           the value to put
 * @param onlyIfAbsent    true时，表示不修改已存在的值
 * @param evict           false时，表示是在初始化HashMap
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table数组为空，需要resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 确定key要插入的数组位置的元素p，如果不存在则直接放入，(n - 1) & hash==hash%n ，前者效率更高
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 插入的位置元素已存在，则说明发生了hash碰撞（1.key是一样的，覆盖value,2,key不一样，存储在链表或者树中） 
    else {
        Node<K,V> e; K k;
        // 检查数组节点p是否和新插入的节点相等（比较key） 
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果不相等
        // 判断数组节点是否为树节点，如果是则按照树状节点规则插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 不是，则按照链表节点规则插入
        else {
            // 死循环，通过break来终止，这里为寻找下一个链表节点的过程
            for (int binCount = 0; ; ++binCount) {
                // 判断当前节点的下一个节点是null的，则占位，如果发现需要转为树结构，则转换，binCount统计链表长度，从0开始
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
               // 下一个节点不是空，则判断是否和新节点相等（key比较），相等则该位置为要找的位置
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 下一个节点变为当前节点，继续循环
                p = e;
            }
        }
        // 要放入的位置确定后，判断位置上的元素是否存在，如果存在则判断是否替换
        if (e != null) { 
            V oldValue = e.value;
            // 满足替换条件才替换
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断是否需要扩容
    if (++size > threshold)
        resize();
    // 插入后的后续处理，HashMap默认=false,不需要
    afterNodeInsertion(evict);
    return null;
}

比较Key的方法

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

hash值必须相等
且
比较key地址相等或者 key!=null 时，比较key内容相等

get

public V get(Object key) {
	Node<K,V> e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	// 从数组中获取对应位置元素不为null则继续查找
	if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
		// 根节点就是要找的节点，则返回
		if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		// 不是则判断根节点类型
		if ((e = first.next) != null) {
			// 树状节点则按照树结构去查找
			if (first instanceof TreeNode)
			return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			do {
				// 不是则按照列表结构查找
				if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
				return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

树状转换

final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
	// 未达到树状结构的最少容量时(默认64)，只扩容不转换
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		resize();
	// 转换
	else if ((e = tab[index = (n - 1) & hash]) != null) {
		TreeNode<K,V> hd = null, tl = null;
		do {
			TreeNode<K,V> p = replacementTreeNode(e, null);
			if (tl == null)
				hd = p;
			else {
				p.prev = tl;
				tl.next = p;
			}
			tl = p;
		} while ((e = e.next) != null);
		if ((tab[index] = hd) != null)
			hd.treeify(tab);
	}
}

数据结构验证

hash定位

public int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

数据准备

String[] arr1 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7"};
String[] arr2 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0"};
String[] arr3 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu"};
String[] arr4 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n"};
String[] arr5 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n", "jaua", "zth9", "maxe"};
String[] arr6 = new String[]{"cg80", "lo8u", "pqdi", "bbam", "hhc5", "pnem", "u955", "p4z7", "phr0", "suv8", "u4pu", "p63n", "jaua", "zth9", "maxe", "wymp"};

arr1是8个字符串,arr2是9个字符串，arr1数据在size=16时，全部落到index=2处

arr2的数据在size=16同样会落在index=2处，此时因为链表长度>8结构转变，因为此时总容量=16小于树状结构最小容量64，因此只扩容1倍=32

arr2数据在size=32时，部分落到index=2处，部分落到index=18处

for (String key : arr2) {
    System.out.println(String.format("%s\tsize=16,index=%s \t ", key, hash(key) % 16));
}
-------------------------------------------------------
cg80 size=16,index=2
lo8u size=16,index=2
pqdi size=16,index=2
bbam size=16,index=2
hhc5 size=16,index=2
pnem size=16,index=2
u955 size=16,index=2
p4z7 size=16,index=2
phr0 size=16,index=2

Map<String, Integer> map1 = new HashMap<>(16, 1);
for (String key : arr1) {
map1.put(key, 0);
}
Map<String, Integer> map2 = new HashMap<>(16, 1);
for (String key : arr2) {
map2.put(key, 0);
}

链表内存验证

Image [16].png Image [17].png

arr3是arr2的链表满长度情况，index=18处的数据长度=8，,arr4则是arr3数据在index=18的数据长度=9时情况，此时再次触发扩容（szie=32<64不会转为树）

for (String key : arr4) {
    System.out.println(String.format("%s\t size=32,index=%s \t", key, hash(key) % 32));
}
-------------------------------------------------------
cg80     size=32,index=18     
lo8u     size=32,index=18     
pqdi     size=32,index=18     
bbam     size=32,index=2     
hhc5     size=32,index=2     
pnem     size=32,index=18     
u955     size=32,index=18     
p4z7     size=32,index=18     
phr0     size=32,index=2     
suv8     size=32,index=18     
u4pu     size=32,index=18     
p63n     size=32,index=18

Map<String, Integer> map3 = new HashMap<>(16, 1);
for (String key : arr3) {
    map3.put(key, 0);
}


Map<String, Integer> map4 = new HashMap<>(16, 1);
for (String key : arr4) {
    map4.put(key, 0);
}

Image [18].png Image [19].png

arr5则是arr4的满员状态，此时index=50的数据长度=8，arr6则是arr5的数据在index=50的数据长度=9时情况，此时链表长度=8触发扩容，size=64.触发树状结构转换

for (String key : arr6) {
    System.out.println(String.format("%s\t size=64,index=%s", key, hash(key) % 64));
}
-------------------------------------------------------
cg80     size=64,index=50
lo8u     size=64,index=50
pqdi     size=64,index=50
bbam     size=64,index=2
hhc5     size=64,index=2
pnem     size=64,index=18
u955     size=64,index=50
p4z7     size=64,index=50
phr0     size=64,index=2
suv8     size=64,index=18
u4pu     size=64,index=18
p63n     size=64,index=18
jaua     size=64,index=50
zth9     size=64,index=50
maxe     size=64,index=50
wymp     size=64,index=50

Map<String, Integer> map5 = new HashMap<>(16, 1);
for (String key : arr5) {
    map5.put(key, 0);
}
Map<String, Integer> map6 = new HashMap<>(16, 1);
for (String key : arr6) {
    map6.put(key, 0);
}

树状数据转换，只针对index=50这个节点，红黑树图示

Image [20].png Image [21].png

红黑树内存验证

Image [22].png Image [23].png

常见问题

为什么使用HashMap

HashMap是非synchronized的键值对存储结构，速度快，效率高
HashMap支持键和值为null存储
HashMap不保证元素的顺序

HashMap中null的使用

key可以为null,但只能有一个，index=0,后续会覆盖前者
value可以为nul，数量不限制

查找效率

在数组中 O(1)
在链表中 O(N)
在树中 O(log N)

为什么采用红黑树而不是AVL树（平衡二叉树）？

区别
- 红黑树特点
  - 每个结点要么是红的要么是黑的。
  - 根结点是黑的。
  - 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
  - 如果一个结点是红的，那么它的两个儿子都是黑的。
  - 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
- 平衡二叉树特点
  - 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
原因
- 二者在查找是都是通过二分法查找，效率差不多
- 插入与删除是红黑树效率较高，因为AVL树要求绝对的平衡，为保证绝对平衡，进行旋转的次数较多

存在问题

在自动调整大小时存在线程安全问题
在ForEach遍历时不能删除元素，正确方式为采用Iterator

为什么使用包装类作为键而不是基本类型

因为包装类重写了hashCode和equals方法，保证了键的不变性，在查询元素时能查找到正确的元素对象

使用对象作为键需要注意什么

注意保证键的不变性，即对象的hashCode和equals方法返回值是确定的

多线程时如何存储

使用HashTable或者ConcurrentHashMap
HashTable是HashMap的synchronized版本，不支持null的键或者值，底层是数组+链表，没有红黑树。ConcurrentHashMap是HashTable的改进版本
ConcurrentHashMap JDK7之前采用锁分离技术，默认将Hash表分为16段，对每段单独加锁，支持16个线程同时访问，支持读取并发，采用fail-fast迭代器，迭代中删除元素抛异常，JDK8之后使用synchronized+cas技术。原因在于分段锁浪费空间且实际中锁竞争情况出现很少。
HashTable是采用锁表技术，对每个操作都加锁保证安全，同一时刻只有一个线程能访问，效率低下，大部分情况可以使用ConcurrentHashMap替代，未采用fail-fast迭代器

扩容为什么是2的整数倍

保证Node的hash尽量的一致性
当n扩容后仍保持2^m时，Node落地点的下标
i=(n - 1) & hash
会更优化

为什么负载因子0.75，链表转红黑树阈值=8，红黑树转链表=6

作为一般规则，默认的负载因子(0.75)提供了良好的性能权衡时间和空间成本。值越高，空间开销越小，但增加查找成本
阈值=8，是因为Hash下标的落地点遵循泊松分布，在负载因子=0.75前提下，忽略计算方差，λ=0.5时，阈值=8的概率为0.00000006，再高概率小于百万分之一，此时性能已经满足需求
阈值=6，是因为=8时链表转为树，再由树转链表这阈值一定小于8，所以=6

使用的是头插法还是尾插法

JDK7之前都是头插法，JDK8之后都是尾插法。因为JDK7中HashMap使用的是数组+链表的数据结构，使用头插法效率高，但是容易出现逆序和链表闭环的问题。JDK8中HashMap使用的是数组+链表+红黑树的数据结构，使用尾插法效率更高。