哈希表(hash table)
哈希表也称为散列表 , 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。也就是说关键字为K的元素存储到数组的位置K , 这也就意味着给定一个关键字K , 仅通过查找数组的第K个位置就可以找到该元素 , 这也称为直接寻址 ,这个映射函数叫做散列函数，存放记录的数组叫做散列表。
使用散列的查找算法分为两步 , 第一步是用散列函数将被查找的键转换为数组的一个索引 , 在理想情况下 , 每个键经过散列函数计算之后都会转换为不同的索引值 , 并且对应一个表中的地址(数组中的一个位置 , 也是内存中的一个地址) , 如下图所示 :
当然 , 这是理想的情况 , 不理想的情况就是多个key经过散列函数计算之后转换为的键是相同的 , 这个时候就会涉及到一个问题 : hash碰撞（如下图所示） , 所以散列算法的第二步也就是一个处理碰撞冲突的过程 ， 解决hash冲突的算法有： 拉线法和线性探测法
线性探测法
线性探测法也叫开放定址法 , 把数组比作几套房子 , 当你正要付定金的时候 , 房子刚好被别人买了 , 这个时候怎么办呢?那就只能再找其他房子了 , 线性探测法也是类似的道理 , 如果当前散列地址有值了 , 那么就去寻找下一个空的散列地址 , 只要散列表足够大 , 那么就会有空的散列地址 , 如上图所示 , 在存放键为d的元素的时候发生了hash碰撞 , 那么就可以使用线性探测法 , 一直去判断 , 直到下标为3的时候发现可以存入元素 , 那么就将键为d的元素存到了下标为3的位置
拉线法
拉线法也叫拉链法 , 在hashMap中为了解决hash碰撞就用了拉链法 , 也就是JDK1.7的HashMap实现使用了数组+链表 , 而JDK1.8的实现中为了更快的检索拉出来的这个"链表"中的内容增加了红黑树 , 大致原理就是如下图所示
键为d , f的散列值出现了hash碰撞 , 这个时候就是用链表来存储重复的元素 , 如果需要根据键a找对应的值 , 那么时间复杂度为O(1) , 直接就可以找到 , 但是如果有多个key的hash值计算之后都为2 , 那么数组下标为2的位置的链表就会比较长 , 我们知道 , 链表的遍历是比较慢的 , 所以为了解决遍历链表慢的问题 , JDK1.8进行了优化 , 引入了红黑树来解决查询慢的问题 , 在HashMap中 , 这个数组又可以称为桶
散列函数
在散列的查找算法中 ， 面对的第一个问题就是散列函数的计算 ， 及把键转换为散列值（数组的索引）的计算 ， 也就是说如果现在有一个长度为M的数组 ， 那么就需要一个函数来将任意键转换为该数组范围内([0 , M-1])整数的索引, 而这个散列函数通常有以下特点:
尽可能的避免hash碰撞
计算简单且快速
将键值(key value) 均匀的分布在散列表
除留余数法
哈希函数的实现有好多种 , 其中比较常用的一种就是除留余数法 , 及使用key的哈希值取模一个素数 , 公式表达为 : H(key)=key MOD p (p<=m) , 但是素数的选择是非常重要的 , 尽可能的选择奇数并且接近m(因为偶数发生hash冲突的概率很大 , 接近m是因为这样计算出来的索引值分布更加均匀) , HashMap使用的就是类似的方法 , 在HashMap初始化或者扩容时 , 元素索引的计算为 : hash & (newCap - 1) , 这样就满足了最佳素数的选择条件 , 只不过HashMap的作者为了提高运算效率 , 没有使用% , 而选择了位运算 , 但是选择位运算数组的长度必须是2的N次方
解释一下: 为什么数组的长度必须是2的N次方
9为key , 4为数组的长度
使用除留余数法在平时的取余中我们是这样运算的 : 9 / 4 = 2…1 ,商为2余数为1 , 所以索引为1 , 换成位运算就是 : 9对应的二进制为: 1001 , 4为2的2次方 , 所以如果一个数除以2的N次方 , 那么我们就是要得到最后这个数最后N位二进制的值
9 (1001) / 2的2次方 = 2…1 等于 (1001 后两位 = 0001 = 1)
因为size为二的幂次方，size-1的二进制一定为111···11这种全是1的数，这样进行与操作就能提取到后N位，所以位运算取余公式是 key MOD p = 9 / (4(2的2次方) -1) 替换为位运算 hash & (size - 1) = 1001 & 0011 = 0001 = 0001 = 1
9为key , 3为数组的长度
如果数组的长度不为2的N次方 , 带入公式 key MOD p = 9 / (3 - 1) 替换为位运算 hash & (size - 1) = 1001 & 0010= 0000 = 0 , 由此可见无法达到预期的效果
java规范
而对于键的类型它可以有几种 , 比如整数 , 浮点数 , 字符串 , 所以散列函数和键的类型有关 , 严格一点来说就是 : 对于每种类型的键 , 都需要一个与之对应的散列函数 , 如果键是一个整数 , 那么可以直接使用这个数 , 如果是一个字符串 , 比如名称 , 那么就需要把这个字符串转换为一个数 , 如果这个键有多个部分 , 比如邮件地址 , 那么就需要把这些部分结合起来 , 对于常见类型的的键 , 可以使用java默认的实现
所以hash函数由于每种数据类型都需要相应的散列函数 , 所以java就令所有数据类型都继承了一个能够返回32比特整数的hashCode()方法
整数类型hashCode()实现
public static int hashCode(int value) { return value; }
字符串hashCode()实现
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; }
浮点型hashCode()实现
public static int floatToIntBits(float value) { int result = floatToRawIntBits(value); // Check for NaN based on values of bit fields, maximum // exponent and nonzero significand. if ( ((result & FloatConsts.EXP_BIT_MASK) == FloatConsts.EXP_BIT_MASK) && (result & FloatConsts.SIGNIF_BIT_MASK) != 0) result = 0x7fc00000; return result; }
但是我们需要的是一个[0,M-1]的索引 , 而不是32比特的整数 , 所以在java中是这样计算hash值的
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
首先把key的hashCode值赋值给h , 然后将h右移16位 , 然后进行^异或运算 , 由此可以引申两个问题
1.为什么要右移16位?
右移16位其实是为了减少hash碰撞 , int类型占4字节 , 也就是32位 , 无符号右移16位 , 高位补0 , 这个时候可以同时保留高16位和低16位的特征 , 或许举个例子就很好明白
如果现在有一个数的hash值为 11110001 数组默认长度为16 , 现在有两个值 : 241 193
241 % 15 换算为2进制 11110001 & 00001111 = 00000001
193 % 15 换算为2进制 11000001 & 00001111 = 00000001
这样这两个数据计算之后索引相同 , 因为HashMap使用的是拉链法 , 所以计算出索引容易一样 ,这就可能导致某个索引下的链表比较长 , 值的分布不均匀 , 但是右移16位 , 就可以使高位的数据也加入到取余计算 , 从而使值的分布更加均匀
2.为什么使用^运算 , 而不是用&或者是|
因为异或可以保证两个值的特性 , 位运算中与(&)运算的结果更加的偏向0 , 而|运算的结果更加偏向1
所以我们可以看出 右移是为了保持低16位与高16位的特征 , 而^运算可以使结果不会偏向0或者1 , 增加了散列程度 , 使数据分布的更加均匀
4.HashMap容量与扩容机制
4.1 HashMap默认扩容因子
/**
The load factor used when none specified in constructor.
/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
扩容因子是用来计算扩容阈值用的
4.2 HashMap默认容量
/*
The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
3.HashMap的阈值
HashMap的阈值计算公式 : 阈值(threshold) = 扩容因子(loadFactor) * 容量(capacity)
如果扩容因子和容量都是默认的话 , 那么阈值就是 0.75f * 16 = 12
如果当HaspMap中table(也成为桶)的长度大于等于阈值时就会触发扩容机制
4.为什么HashMap的默认负载因子是0.75，而不是0.5或者是整数1呢？
阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) 根据HashMap的扩容机制，它会保证容量(capacity)的值永远都是2的幂
为了保证负载因子x容量的结果是一个整数，这个值是0.75(4/3)比较合理，因为这个数和任何2的次幂乘积结果都是整数
理论上来讲，负载因子越大，导致哈希冲突的概率也就越大，负载因子越小，费的空间也就越大,这是一个无法避免的利弊关系，所以通过一个简单的数学推理，可以测算出这个数值在0.75左右是比较合理的
5.为什么容量的值永远都是2的幂
HashMap是根据key的hash值通过公式tab[i = (n - 1) & hash] 计算得出key在桶中的位置 , 这里n是HashMap的容量 , 因为永远都是2的幂 , 所以n-1通过二进制表示永远都末位连续1的形式表示 , 例如 00001111 , 00000011 , 当(n - 1)和hash做与运算的时候会保留末位的x位的1 , 这样做的好处在于 :
&位运算的效率比%取模运算的效率高(但是有一个前提 ： n也就是HashMap的容量要保证是2的幂)
能保证索引值在容器范围内(n - 1) & hash 运算的值分布比较均匀 , 可以减少hash冲突
那么如果我们在构造参数指定容器的大小不为2的幂 ,是不是就打破了以上规则?
不是的 , HashMap的tableSizeFor方法做了处理，能保证n永远都是2次幂。
/** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { //cap-1后，n的二进制最右一位肯定和cap的最右一位不同，即一个为0，一个为1，例如cap=17（00010001），n=cap-1=16（00010000） int n = cap - 1; //n = (00010000 | 00001000) = 00011000 n |= n >>> 1; //n = (00011000 | 00000110) = 00011110 n |= n >>> 2; //n = (00011110 | 00000001) = 00011111 n |= n >>> 4; //n = (00011111 | 00000000) = 00011111 n |= n >>> 8; //n = (00011111 | 00000000) = 00011111 n |= n >>> 16; //n = 00011111 = 31 //n = 31 + 1 = 32, 即最终的cap = 32 = 2 的 (n=5)次方 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
6.HashMap的扩容机制
写数据的时候会发生扩容 , 它内部有一个字段用来记录当前数据量的字段 , 如果数据量字段达到扩容的阈值的话 , 就会触发扩容机制
阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) , 当HashMap中的table数组(桶)的长度 >= 阈值的时候就会自动触发扩容机制
扩容规则是这样的 : 因为table数组的长度必须是2的幂 , 所以扩容其实也就是按照上一次的tableSize左移了1位 , 比如当前table数组的长度是16 , 扩容一次之后就是 16 << 1 = 32 , 也就是说扩容之后的长度是当前长度的两倍 , 但需要记住的是扩容使用的是左移一位(newTableSize = tableSize << 1) 得到的扩容后的容量 ,而不是当前容量 * 2
7.为什么HashMap扩容不直接*2
因为cpu不支持乘法运算 , 所有的乘法运算最终都是到了指令层面转换为假发实现的 , 这样效率很低 , 如果使用位运算的话对于cpu来说简洁又高效
8.HashMap的扩容过程
JDK1.7
先生成新的数组
遍历老数组上每个位置上的链表的每个元素
取每个元素的key , 基于新数组的长度 , 计算出每个元素在新数组中的下标
将元素添加到新数组中
所有元素转移完毕之后 , 将新数租赋值给HashMap对象的table属性
JDK1.8
先生成新数组
遍历老数组中每个位置上的链表或者红黑树
如果是链表 , 则直接将链表中的每个元素重新计算下标 , 并添加到新数组
如果是红黑树 , 则先遍历红黑树 , 计算出每个元素对应在新数组中的下标
统计每个下标的元素个数
如果个数超过了8个 , 那么就重新生成红黑树 , 并将根节点添加到新数组对应的位置
如果个数没有超过8个 , 那么则生成一个链表 , 并将链表的头节点添加到新数组对应的位置
所有元素转移完毕之后 , 将新数租赋值给HashMap对象的table属性
如果感觉博主写的还不错的话 可以来一个一键三连 , 并且同时可以顺便关注一下博主的公众号 : [猿人刘先生] , 下面我把链接贴出来 , 非常感谢大家的阅读与关注 , 希望我们可以不想学习 , 共同进步 !!!
java集合框架Map之HashMap底层原理解析
