亲宝软件园·资讯

展开

简单谈谈HashMap

江城子23 人气:0
# 概述 面试Java基础,HashMap可以说是一个绕不过去的基础容器,哪怕其他容器都不问,HashMap也是不能不问的。 除了HashMap,还有HashTable跟ConcurrentHashMap,两个都是线程安全的哈希容器,但是HashTable是JDK1.0就有的容器,线程安全是通过`synchronized`关键字来实现的,而且锁住的是整个table对象,虽然线程安全,但是并发性能并不高。因此在JDK1.5里面并发大师Doug Lea操刀写了个ConcurrentHashMap,通过粒度更细的锁来实现更高的性能。 # HashMap的历史 在不同版本的JDK中,HashMap是在不停优化的。 - 比如JDK1.6里面new HashMap时,开辟了内存空间,如果不使用,则浪费内存;JDK1.7里面改成了懒加载,new HashMap并没有开辟内存空间,节约了内存空间 - 1.8优化了hashCode算法:高16位异或(XOR)低16位 主要是为了增加扰动,减少碰撞几率 - 1.8里面优化了hash碰撞较多情况下的性能问题(链表长度限制为8,过长时请将链表转换为TreeNode(红黑树)) # 配置常量 ```Java static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; static final int TREEIFY_THRESHOLD = 8; static final int UNTREEIFY_THRESHOLD = 6; static final int MIN_TREEIFY_CAPACITY = 64; ``` HashMap容器初始化的容量为16,默认负载因子为0.75,树化阈值为8,反树化阈值为6。 # put流程 - 对key的hashCode()做hash运算,计算index; - 如果没碰撞直接放到bucket里; - 如果碰撞了,以链表的形式存在buckets后; - 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树(JDK1.8中的改动); - 如果节点已经存在就替换old value(保证key的唯一性) - 如果bucket满了(超过load factor*current capacity),就要resize。 # get流程 - 对key的hashCode()做hash运算,计算index; - 如果在bucket里的第一个节点里直接命中,则直接返回; - 如果有冲突,则通过key.equals(k)去查找对应的Entry; - 若为树,则在树中通过key.equals(k)查找,O(logn); - 若为链表,则在链表中通过key.equals(k)查找,O(n)。 # Hash算法 ```Java static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ``` HashMap中可以存放key为null的值,放在首位。 将高16位与低16位异或运算,通过这样一个扰动函数,减小了hash冲突的概率。然后再通过这个hash值与数组的长度进行取模运算,决定这个键值对该放入哪个bin中。 > (n - 1) & hash 这个算法是当bin为bull的时候,直接将Node放入table中;当扩容的时候,存在两种情况,要么放在原来的位置,要么往后移动原来的容量大小的位置,这时候使用的是下面这个算法: > e.hash & oldCap 如果得到的结果为零,则在原位置;反之,则将其向高位移动oldCap大小的位置。 # 拓展 String的Hash算法如下: ```Java public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } ``` String类中的hashCode计算方法还是比较简单的,就是以31为权,每一位为字符的ASCII值进行运算,用自然溢出来等效取模。 哈希计算公式可以计为s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 那为什么以31为质数呢? 主要是因为31是一个奇质数,所以`31*i=32*i-i=(i<<5)-i`,这种位移与减法结合的计算相比一般的运算快很多。

加载全部内容

相关教程
猜你喜欢
用户评论