程序猿
微录

Java数据结构之【HashMap】(jdk1.8)

程序猿微录 发布于: 2020-05-12 03:31 253 0 0 0
首页
文章
专栏
问答
寄语
公告
  • 前往登录

Java数据结构之【HashMap】(jdk1.8)

程序猿微录 发布于 2020-05-12 03:31 253 0 0 0
所属文册: JDK 文章标签: HashMap 、数据结构

数据结构之【 HashMap 】

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

名称解释

  • Hash:
    • 一般翻译为 散列,直译为 哈希
  • Hashing: 散列法
    • 把任意长度的输入通过散列算法变换成固定长度的输出,该输出就是散列值。是一种典型的“空间换时间”的做法。
  • 负载因子
    • 比如我们存储70个元素,但我们可能为这70个元素申请了100个元素的空间。70/100=0.7,这个数字称为负载因子
  • 哈希冲突(碰撞)
    • 由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突
    • 解决方案:开放寻址法、拉链法。HashMap处理方案就是拉链法

数据结构存储图示

Image [43].png

源码说明(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使用的是数组+链表+红黑树的数据结构,使用尾插法效率更高。