云梦县城乡建设局网站,凡科快图在线制作免费官网下载,郑州h5网站建设,原创文章对网站的好处目录
HashMap是什么#xff1f;
为什么要使用HashMap#xff1f;
HashMap存储元素原理#xff08;put⽅法#xff09;
扰动函数
前置知识
异或运算
运算
为什么使用扰动函数
实验验证扰动函数
常见问题
HashMap的默认长度是多少#xff1f;
HashMap是先扩…目录
HashMap是什么
为什么要使用HashMap
HashMap存储元素原理put⽅法
扰动函数
前置知识
异或运算
运算
为什么使用扰动函数
实验验证扰动函数
常见问题
HashMap的默认长度是多少
HashMap是先扩容在插入数据还是先插数据在扩容
HashMap链表转红黑树 和 红黑树退化为链表的条件分别是什么
HashMap链表转红黑树
HashMap红黑树退化成链表
HashMap和Hashtable的区别
HashMap的搜索的时间复杂度是多少 HashMap是什么 JDk1.7HashMap 数据结构为 数组链表JDk1.7。JDK1.8中增加了红黑树其中链表的节点存储的是一个 Entry 对象每个Entry 对象存储四个属性hashkeyvaluenext 。
为什么要使用HashMap
对于要求查询次数特别多查询效率比较高同时插入和删除的次数比较少的情况下通常会选择ArrayList因为它的底层是通过数组实现的。对于插入和删除次数比较多同时在查询次数不多的情况下通常会选择LinkedList因为它的底层是通过链表实现的。
但现在同时要求插入删除查询效率都很高的情况下我们该如何选择容器呢 那么就有一种新的容器叫HashMap他里面既有数组结构也有链表结构所以可以弥补相互的缺点。而且HashMap主要用法是get()和put() 。
HashMap存储元素原理put⽅法 扰动函数
在HashMap存放元素时候有这样一段代码来处理哈希值这是java 8的散列值扰动函数用于优化散列效果
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
前置知识
异或运算
异或运算是一种布尔运算通常表示为符号“^”它的结果为两个操作数相应位上的数值相异或得到的值。如果两个相应位的值相同则结果为0否则结果为1。具体来说如果输入的两个二进制数的某一位相同则该位上的异或结果为0否则为1。
运算
运算是位运算符之一用来执行按位与操作。它对两个操作数的每一位执行逻辑“与”操作即如果两个操作数的对应位都是1则结果为1否则为0。运算符通常用于处理二进制数据例如在编程语言中进行位操作。
为什么使用扰动函数
理论上来说字符串的hashCode是一个int类型值那可以直接作为数组下标了且不会出现碰撞。但是这个hashCode的取值范围是[-2147483648, 2147483647]有将近40亿的长度谁也不能把数组初始化的这么大内存也是放不下的。
我们默认初始化的Map大小是16个长度 DEFAULT_INITIAL_CAPACITY 1 4所以获取的Hash值并不能直接作为下标使用需要与数组长度进行取模运算得到一个下标值也就是我们上面做的散列列子。
那么hashMap源码这里不只是直接获取哈希值还进行了一次扰动计算(h key.hashCode()) ^ (h 16)。把哈希值右移16位也就正好是自己长度的一半之后与原哈希值做异或运算这样就混合了原哈希值中的高位和低位增大了随机性。计算方式如下图 说白了使用扰动函数就是为了增加随机性让数据元素更加均衡的散列减少碰撞。
从上面的分析可以看出扰动函数使用了哈希值的高半区和低半区做异或混合原始哈希码的高位和低位以此来加大低位区的随机性。
但看不到实验数据的话这终究是一段理论具体这段哈希值真的被增加了随机性没有并不知道。所以这里我们要做一个实验这个实验是这样做
选取10万个单词词库
定义128位长度的数组格子
分别计算在扰动和不扰动下10万单词的下标分配到128个格子的数量
统计各个格子数量生成波动曲线。如果扰动函数下的波动曲线相对更平稳那么证明扰动函数有效果。
实验验证扰动函数
扰动函数对比方法
public class Disturb {public static int disturbHashIdx(String key, int size) {return (size - 1) (key.hashCode() ^ (key.hashCode() 16));}public static int hashIdx(String key, int size) {return (size - 1) key.hashCode();}}
disturbHashIdx 扰动函数下下标值计算hashIdx 非扰动函数下下标值计算
单元测试
// 10万单词已经初始化到words中
Test
public void test_disturb() {MapInteger, Integer map new HashMap(16);for (String word : words) {// 使用扰动函数int idx Disturb.disturbHashIdx(word, 128);// 不使用扰动函数// int idx Disturb.hashIdx(word, 128);if (map.containsKey(idx)) {Integer integer map.get(idx);map.put(idx, integer);} else {map.put(idx, 1);}}System.out.println(map.values());
}
以上分别统计两种函数下的下标值分配最终将统计结果放到excel中生成图表。
扰动函数散列图表
以上的两张图分别是没有使用扰动函数和使用扰动函数的下标分配。实验数据
10万个不重复的单词128个格子相当于128长度的数组
未使用扰动函数 使用扰动函数 从这两种的对比图可以看出来在使用了扰动函数后数据分配的更加均匀了。数据分配均匀也就是散列的效果更好减少了hash的碰撞让数据存放和获取的效率更佳。
常见问题
HashMap的默认长度是多少
严格意义说HashMap的默认长度是0但是长度为0的时候第一次插入数据的时候若判断当前长度为0则直接扩容到16.leng
HashMap是先扩容在插入数据还是先插数据在扩容
若判断长度0时则是先扩容再插入数据若长度不为0则是先插入数据再扩容
HashMap链表转红黑树 和 红黑树退化为链表的条件分别是什么
先展示一下HashMap里的三个常量 HashMap链表转红黑树
链表的节点数量(包括新增节点)大于等于树化阈值HashMap的容量(Node数组的长度)大于等于最小树化容量值。
延伸题 若链表节点数超过树化阈值但是HashMap的容量小于树化容量会如何
会进行一次扩容使其大于或等于最小束花容量值随后在进行树化
HashMap红黑树退化成链表
当红黑树中的元素个数小于等于6时该红黑树会被转换为链表。这是因为当元素数量较少时红黑树的性能反而会不如链表。
HashMap和Hashtable的区别 HashMap Hashtable 父类 继承AbstractMapAbstractMap又实现了 Map 接口 Hashtable 继承了 Dictionary 并实现Map接口 默认值不同 默认的初始数组长度是 16 默认的加载因子是 0.75 每次扩容变成之前数组的 2 倍长度 默认的初始数组长度是 11 默认的加载因子是 0.75 每次扩容是之前数组的 2 倍长度加 1 空值 只能有一个key为空 允许value为空。 keyvalue 都不允许为空。 获取数组下标的方式 底层数据结构不同 数组链表红黑树 数组链表 线程安全问题 false true
HashMap的搜索的时间复杂度是多少
若不hash冲突则是O(1)
链表则是O(n)
红黑树是O(logn)
