???????java语言除了数组外是没有任何现成的数据结构的,所有的数据结构都是jdk类库提供的,哈希表是一种数据结构,这种数据结构要求读写对应的时间复杂度必须为O(1),为了实现这个目的大家看下jdk大佬们是如何实现的吧,以及从jdk1.8只有做了哪些相应的改进.
1.成员变量
// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
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真正存储数据的桶数组,该数组的长度就是该hashmap的capacity(容量)
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
// 存储的数据量,比如初始化时table的长度为16,但是还没有put值.
// 那么此时hashmap的capacity=16,size = 0;
transient int size;
// 修改计数器:用于快速失败.比方说一边查询,一边删除.
transient int modCount;
// 阈值:当hashmap的size超过该值,可能会引发扩容
int threshold;
// 负载因子:容量 * 负载因子 = threshold.表示该hashmap容量达到的百分比,比如loadFactor=0.75
// 说明,hashmap中数据的个数已经达到table数组75%,本来hashmap的初衷是要做O(1)时间复杂度.
// 这个容量已经达到数组长度的3/4了,本来打算数组的一个索引放一个值的,但由于考虑空间使用问题,
// 折中方案是采用在数组的一个索引下挂一个链表结构来节省内存空间.存的时候是根据hashcode对
// 数组长度取余来确定该key的存放位置的.但是由于取模的位置有可能重复.比如初始容量为16,当我们的
// hashcode=16,32,48,64,...,16*n 对16取模,取得的值均为0,都会放到0号桶内.这样就有可能造成0号桶内
// 数据堆积,查询的时候就需要遍历0号桶,那么相应的时间复杂度就会增大,有可能会背离O(1)的初衷
// 当对hashmap扩容后.分别会将16,48等数据(一半)的数据从0号桶迁移到16号桶内.这样就会大大减小每个桶
// 内数据的堆积,减少每个桶内数据的个数,从而降低时间复杂度.
final float loadFactor;
接着我们看下hashmap的构造函数
public HashMap() {
// 无参构造只是初始化了负载因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
// 带参数的构造
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException(
"Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(
"Illegal load factor: " + loadFactor);
// 初始化了负载因子和阈值
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
**ps:**哈希表数据结构读写对应的时间复杂度必须为O(1),java的哈希表结构实现者为了平衡时间复杂度与资源利用率(计算机内存).所以做出了数组不断扩容的结构，hashcode不同但桶地址相同 以及 hashcode相同但equals不同的key采用单链表结构来进行处理,jdk1.8以后当单链表长度大于8时会转换成红黑树结构,从而进一步降低因节省计算机内存造成的时间复杂度升高的影响.
2.put方法
???????我们先看下put的流程图
2.1.hash扰动
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
// 1.扰动的原理
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么要对原始的hashcode值进行扰动呢？请看下面的图:假设hashmap的初始化容量为16
???????从上图我们可以看到当高16位有值,低16位无值时,扰动是朝着哈希桶寻址算法有利的方向发展的.但高16位有值,低16位也有值这样会朝着哈希桶寻址不利的方向发展.从上图看,一正一反好像没有多大意义啊?那我们看下扰动算法的注释吧.
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
// 我们看这一段
// Among known examples are sets of Float keys holding consecutive
// whole numbers in small tables
// 翻译过来就是：已知的例子有在小表中保存连续的浮点键集。大意就是当hashmap中的table数组长
// 度比较小时,而且key存的是浮点类型的数据,如果不扰动,使用原始hashcode通过哈希桶寻址算法
// 找到的桶重复的可能性很大,也就可能导致一个桶下挂了n多节点,从而不能达到O(1)的复杂度.
static final int hash(Object key)
- 到底是否如注释所说呢?我们做如下实验
// 字符串不够32位左补0
public static String leftZero(String src) {
StringBuilder sbf = new StringBuilder();
if (src.length() < 32) {
int leftNum = 32 - src.length();
for (int i = 0;i < leftNum;i++) {
sbf.append("0");
}
}
return sbf.append(src).toString();
}
???????首先我们看下浮点型
public static void runFloat() {
for (float i = 0f;i < 10f;i++) {
String srcHash = Integer.toBinaryString(Float.hashCode(i));
System.out.println(leftZero(srcHash));
}
}
???????我们看下输出结果
???????惊人的发现,浮点型数据当小于1000000时,生成的低4位全为0.换句话说,当我们用浮点型数据作为hashmap的key的时候.且取值在1000000以下时,如果hash值不扰动的话,在hashmap的初始容量为16的情况下.这些数据都会聚集到0号桶.那么我们的哈希表就背离了O(1)时间复杂度这一初衷了.如果是jdk1.7没有红黑树结构改造的话,时间复杂度就是O(n),即使jdk1.8新增了红黑树结构,那么对应的时间复杂度也是O(logn).所以才有了hash扰动算法.
- 那我们看看String类型的key的hash码的分布是如何的？
public static void runString() {
String srcStr = "qwertyuiopasdfghjklzxcvbnm";
StringBuilder sbf = new StringBuilder();
Random random = new Random();
for (int i = 0;i < 20;i++) {
// 将buf置为空
sbf.setLength(0);
// 从srcStr随机抽10个字符组成新的字符串
for (int j = 0;j < 10;j++) {
sbf.append(srcStr.charAt(random.nextInt(srcStr.length())));
}
System.out.println(leftZero(
Integer.toBinaryString(sbf.toString().hashCode())));
}
}
???????我们看看结果
???????看到了吧,不管String的长度是多少,String的hashcode计算的都非常均匀,高16位与低16位分布的都很散.既有有利扰动,也有不利扰动.扰动函数对String类型是不敏感的.网上很多帖子写的关于String类型的来测试扰动算法,其实都是不太合适的,也不太会有明显的效果.
Q：hashmap是怎么处理hash值的？为什么要这么处理？
A：hashmap对key的原始hash值进行了扰动处理,具体方法是高16位与低16位进行异或处理.已知int,float等类型作为key时,计算出来的hashcode是不均匀的,当值不是特别大时,比如说小于1000000,那么相应的低位是没有有效位的(全是0位).如果不采用扰动函数可能造成单桶数据堆积,从而无法达到O(1)的时间复杂度要求,jdk1.7时时间复杂度可能为O(n),jdk1.8及以后可能为O(logn).
2.2.找old值
2.2.1.链表结构
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// ... 省略 ...
// p为该桶的头结点
// e为记号结点,找到相同的key则不为null,否则为null
for (int binCount = 0; ; ++binCount) {
// 而且将该节点的下一个节点赋值给记号结点e
// 到了该桶的尾结点时才会进到if里面,同时记号结点被赋值为null
if ((e = p.next) == null) {
// 如果到了尾结点都都没有找到相同的k.那么放到链表尾部即可
// 尾插法
p.next = newNode(hash, key, value, null);
// 如果链表长度大于8,该桶的链表结构需要转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 转换红黑树
treeifyBin(tab, hash);
break;
}
// 如果找到了相同的k.那么也跳出
// e为找到的旧节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
// ... 省略 ...
}
???????从上述代码可以看出找相同key的两个条件,满足一个即可
- 扰动后的hash相等 && 地址值相等
- 扰动后的hash相等 && equals为true
这两个条件满足一个即可.
2.2.2.红黑树结构
final TreeNode<K,V> putTreeVal(HashMap<K,V> map,
Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 找到头结点
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
// 当前桶内节点的hash值大于准备存入值,也就是说存入的数据小 需要往左找
if ((ph = p.hash) > h)
dir = -1;
// 这个也就是说准备存入的数据大 需要往右找
else if (ph < h)
dir = 1;
// 当前的key与准备存入的key地址相等 || equals方法相等,
// 直接就找到了之前hashMap中存的节点,返回
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 省略...
// 省略...
TreeNode<K,V> xp = p;
// dir <=0 往左找,dir > 0往右找,如果没有找到节点说明找到了最后一个
// 如果找到了节点,根据dir判断往左挂还是往右挂
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
// 需要新创建一个TreeNode节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// 存入的数据小,要往左放
if (dir <= 0)
xp.left = x;
// 存入的数据大,要往右放
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// 这里是保证红黑树的平衡性
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
???????这里判断key是否相同的规则与链表结构一样.而且这里有一点,红黑树节点的大小比较是根据key的hash值来判断的.
Q:什么是hash碰撞？
A:两个不同的key经过相同的hash函数计算后得到相同的hash值.
?
Q:hashmap是如何处理hash碰撞的?
A:hashmap判断key是否相同时,当hashcode相同时需要判断key的地址值是否相同或者equals方法是否返回true,二选一作为附加条件来解决hash碰撞因不同的key产生相同的hashcode的问题.
?
Q:hashmap的key需要注意什么吗？
A:hashmap的key需要为不变值,至少当hashmap的key变得时候不要影响到其hashcode结果及equals方法的结果.否则当我们把自定义对象作为key存入到hashmap中.当修改对象某一属性并影响到了hashcode和equals方法的话,会导致该对象无法从hashmap中取出.
?
Q:jdk1.7和1.8对hashmap有什么改进
A:jdk1.7的时候是数组加链表结构,1.8的时候当链表的长度 > 8时,需要将链表结构转换成红黑树结构.举例：当某一对象的hashcode值计算不合理时会造成大量数据单桶堆积(float类型作为key,且不进行扰动时),会影响该结构O(1)的时间复杂度初衷.如果单桶堆积严重时,链表结构的时间复杂度为O(n),效率太低.所以当单链表长度较长时,引入了红黑树结构,时间复杂度为O(logn).该结构结合hash值的扰动,基本能达到O(1)的一个时间复杂度的要求.
?
Q:为什么不直接用数组+红黑树?而且当红黑树中节点数小于6又要转换回单链表?
A:这个问题我也不好回答.自己感觉红黑树虽然是O(logn)但是在n较小的时候没有太明显的区分.无非当n=8时,一个是查8次,一个是查3次没有太明显区别.另外一点是红黑树结构复杂,既要保证搜索性(左小右大)又要保证平衡性(左旋右旋),当n较小时其对应的读写时间复杂度未必有单链表高.
?
Q:为什么不使用搜索二叉树?
A:因为搜索二叉树不能保证平衡性,极端情况下,搜索二叉树容易形成单链表(只有左子节点或者只有右子节点).
2.3.扩容
2.3.1.链表桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 将头结点赋值给e
if ((e = oldTab[j]) != null) {
else { // preserve order
// 这里为什么只有高位头和高位尾呢?
// 因为一个桶的数据经过扩容之后,只有两个去处
// 要么不动,要么去到oldCap + 当前桶
// 低位头,低位尾
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;
}
// 位置 + oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
// 直到该桶下的数据全部迁移完毕
} while ((e = next) != null);
// 如果低位的尾不为null,说明该节点在原桶中不是最后一个节点,
// 但是在新桶中是最后一个节点,这里需要断开与旧桶的下一节点链接
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位尾处理方法与低位相同
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
2.3.2.红黑树
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
// 这边也是,根据与旧容量按位与&,找桶.这里是不变桶
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
// 这里需要变桶
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 如果换完之后,发现树结构的节点 <= 转换链表的阈值,需要将头转换成链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
// 这里是转红黑树,有点复杂解读
loHead.treeify(tab);
}
}
if (hiHead != null) {
// 如果换完之后,发现树结构的节点 <= 转换链表的阈值,需要将头转换成链表
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
Q: 什么时候会引发扩容?
A: 当往hashmap中put数据时,而且该数据在hashmap中不存在时才可能引发扩容,即产生新节点时.
?
Q: 能说说细节吗?
A: 其实这个看我的流程图就能看出端倪.当往hashmap中put数据时,如果生成了新的节点,而且size超过了扩容阈值.这时会引发扩容现象.扩容的时候会根据之前的hash值进行桶的再分配,这时桶内节点只有两个去处,一个是在当前桶内,另一个是到oldCap + 旧桶位的新桶内.如果原桶是红黑树节点的话,由于桶内的数据可能会减少,那么当桶内节点小于等于6时会触发红黑树转单链表的操作.
?
Q: hashmap被多个线程put时会有什么问题?
A: 其实会有很多问题.jdk1.7时链表是头插法,会产生死循环问题.jdk1.8改成了尾插法也会有数据错乱问题,比如线程1、线程2同时获取到当前节点的next的节点.此时线程1等待,线程2经计算需要把next节点移到 oldcap+旧桶位的新桶内并且与新桶的数据产生连接.那么线程1在回来时进行next的时候拿的就是新桶的数据而不是旧桶的数据了. 而且扩容的时候刚创建完新桶还没有进行数据迁移的时候就会将hashmap的table指针指向新桶,这一时刻hashmap中是没有任何数据.这时如果在去get的话会什么也取不到.总之一句话hashmap不适合多个线程同时读写.但是可以同时读.如果需要并发读写需要使用ConcurrentHashMap.
?
Q: hashmap的容量有什么规律？
A: hashmap的容量都是2的幂.
?
Q: 为什么会这么设计?
A: 1.因为采用二进制运算效率高,整数采用2的幂能很好模拟二进制运算
????????1).因为&的运算效率高,2的倍数才能使用&来进行桶寻址.
????????2).扰动函数也是采用(h = key.hashCode()) ^ (h >>> 16).
??? 2.扩容的时候减少数据移动(只有一半数据移动).可看我前一篇文章
3.get方法
public V get(Object key) {
Node<K,V> e;
// 这里的hash也是要扰动的
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;
// 桶已经初始化,且对应桶的头结点有值
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 检查头结点的hash 与 (地址 || equals方法).跟put一致
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果头结点不是我们要找的节点,而且头结点有next节点
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;
}
????????get方法比较简单,判断key相同的规则与put一致.