博客

HashMap的几个难点

  • Post author:
  • Post category:其他




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

当我们put的时候，首先计算

key

的

hash

值，这里调用了

hash

方法，

hash

方法实际是让

key.hashCode()

与

key.hashCode()>>>16

进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：

高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞

。按照函数注释，因为bucket数组大小是2的幂，计算下标

index = (table.length - 1) & hash

，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能

在这里插入图片描述



2. 关于扩容

每次添加时会比较当前元素个数和阈值： 

    //如果超出临界值，就得扩容
    if (++size > threshold)
        resize();


扩容：


我们希望控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少

  • 如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞
  • 如果哈希桶数组很大，虽然较差的Hash算法也会比较分散，但是浪费了空间


所以我们要使用好的Hash算法和扩容机制



(容量*填充因子)>threshold

时，会进行扩容，而不是再放满了以后再扩容，这是因为HashMap 扩容开销很大（需要创建新数组、重新哈希、分配等等），初始容量和加载因子是与扩容相关的两个因素，决定了什么时候扩容


加载因子：HashMap 的默认加载因子为 0.75，这是在时间、空间两方面均衡考虑下的结果：


① 加载因子太大的话发生冲突的可能就会大，查找的效率反而变低

② 太小的话频繁 rehash，导致性能降低

HashMap 按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）。扩容之后，要重新计算键值对的位置，并把它们移动到合适的位置上去

① 计算新桶数组的容量 newCap 和新阈值 newThr

② 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的

③ 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。这是1.8以后的，我们现在为了简单先分析1.7的代码 

void resize(int newCapacity) {   //传入新的容量
	Entry[] oldTable = table;    //引用扩容前的Entry数组
	int oldCapacity = oldTable.length;         
 	if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
		threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
    	return;
	}

	Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
	transfer(newTable);                         //！！将数据转移到新的Entry数组里
	table = newTable;                           //HashMap的table属性引用新的Entry数组
	threshold = (int)(newCapacity * loadFactor);//修改阈值
}

void transfer(Entry[] newTable) {
	Entry[] src = table;                   //src引用了旧的Entry数组
	int newCapacity = newTable.length;
	for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
		Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
		if (e != null) {
			src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
			do {
				Entry<K,V> next = e.next;
				int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
				e.next = newTable[i]; //标记[1]
				newTable[i] = e;      //将元素放在数组上
				e = next;             //访问下一个Entry链上的元素
			} while (e != null);
		}
	}
}

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上

在这里插入图片描述


上面是JDK1.7的做法，对于JK1.8做了些优化


//TODO


线程安全问题


在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。

在jdk1.7中使用的是头插法，所以多线程使用HashMap可能造成死循环

有如下代码 

public class HashMapInfiniteLoop {  

    private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
    public static void main(String[] args) {  
        map.put(5， "C");  

        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }  
}

map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize

假设现在线程1进行到了

Entry next = e.next;

后被挂起，线程2完成resize，这时Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表

在这里插入图片描述

线程一被调度回来执行，先是执行

newTalbe[i] = e

， 然后是

e = next

，导致了e指向了key(7)，而下一次循环的

next = e.next

导致了next指向了key(3)

在这里插入图片描述


e.next = newTable[i]

导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了

在这里插入图片描述


使用头插会改变链表的上的顺序，但是jdk1.8使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证



3. 关于key


3.1 能否使用任何类作为 Map 的 key？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

  • 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。

  • 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。

  • 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。

  • 用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。



3.2 为什么HashMap中String、Integer这样的包装类适合作为Key？

  • String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率

  • 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况

  • 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；



3.3 如果使用Object作为HashMap的Key，应该怎么办呢？

重写hashCode()和equals()方法

重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；

重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；



4. HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 – 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；


那怎么解决呢？

  1. HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；

  2. 在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 – 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配”的问题



5. HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。


这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方


版权声明：本文为weixin_43907800原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
Tags: