关于网站的毕业设计,勉县网站建设,一个网站的入口网页又称为,网站图片的像素一、HashMap里的Hash是什么#xff1f;
首先#xff0c;我们先要搞清楚HashMap里的的Hash是啥意思。
当我们在编程过程中#xff0c;往往需要对线性表进行查找操作。
在顺序表中查找时#xff0c;需要从表头开始#xff0c;依次遍历比较a[i]与key的值是否相等#xff…一、HashMap里的Hash是什么
首先我们先要搞清楚HashMap里的的Hash是啥意思。
当我们在编程过程中往往需要对线性表进行查找操作。
在顺序表中查找时需要从表头开始依次遍历比较a[i]与key的值是否相等直到相等才返回索引i在有序表中查找时我们经常使用的是二分查找通过比较key与a[i]的大小来折半查找直到相等时才返回索引i。最终通过索引找到我们要找的元素。
但是这两种方法的效率都依赖于查找中比较的次数。
那能不能不经过比较而是直接通过关键字key一次得到所要的结果呢这时就有了散列表查找哈希表
散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f使每一个关键字都对应一个存储位置。这样在查找的过程中只需要通过这个对应关系f 找到给定值key的映射fkey。只要集合中存在关键字和key相等的记录则必在存储位置fkey处。我们把这种对应关系f 称为散列函数或哈希函数。按照这个思想采用散列技术将记录存储在一块连续的存储空间中这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址或散列地址。
相信看到这里大家都懂这个Hash是什么意思了其实就是散列技术通过一个对应关系快速找到目标值的位置。
二、HashMap是什么
HashMap是正是基于哈希表的数据结构用于存储键值对(key-value)。
HashMap基于键的HashCode值唯一标识一条数据同时基于键的HashCode值进行数据的存取因此可以快速地更新和查询数据但其每次遍历的顺序无法保证相同。
HashMap的key和value允许为null。
HashMap是非线程安全的即在同一时刻有多个线程同时写HashMap时将可能导致数据的不一致。
如果需要满足线程安全的条件则可以用Collections的synchronizedMap方法使HashMap具有线程安全的能力或者使用ConcurrentHashMap。
三、HashMap的底层原理
HashMap的核心原理是将键的哈希值映射到数组索引位置通过数组链表在Java 8及之后是数组链表或红黑树来处理哈希冲突。
HashMap使用键的hashCode()方法计算哈希值并通过indexFor方法JDK1.7之后版本移除了这个方法直接使用(n-1) hash确定元素在数组中的存储位置。哈希值是经过一定扰动处理的防止哈希值分布不均匀从而减少哈希冲突。
1、HashMap的数据结构 HashMap的数据结构如上图所示其内部是一个数组数组中的每个元素都是一个单向链表链表中的每个元素都是嵌套类Entry的实例Entry实例包含4个属性key、value、hash值和用于指向单向链表下一个元素的next。
HashMap在查找数据时根据HashMap的Hash值可以快速定位到数组的具体下标但是在找到数组下标后需要对链表进行顺序遍历直到找到需要的数据时间复杂度为O(n)。为了减少链表遍历的开销Java 8对HashMap进行了优化将数据结构修改为数组链表或红黑树。在链表中的元素超过8个以后HashMap会将链表结构转换为红黑树结构以提高查询效率红黑树是一种自平衡二叉搜索树能够将最坏情况下的查询复杂度从O(n)降低到O(log N)。如果树中元素的数量低于6个红黑树会转换回链表以减少不必要的树操作开销。
Java 8 HashMap的数据结构如下图所示
2、hashCode()和equals()的重要性
HashMap的键必须实现hashCode()和equals()方法。hashCode()用于计算哈希值以决定键的存储位置而equals()用于比较两个键是否相同。在put操作时如果两个键的hashCode()相同但equals()返回false则这两个键会被视为不同的键存储在同一个桶的不同位置。
误用hashCode()和equals()会导致HashMap中的元素无法正常查找或插入
3、默认容量与负载因子的选择
HashMap常用的参数如下
capacity当前数组的容量默认为16可以扩容扩容后数组的大小为当前的两倍因此该值始终为2n。loadFactor负载因子默认为0.75。threshold扩容的阈值其值等于capacity×loadFactor。
默认容量是16负载因子是0.75这个组合是在性能和空间之间找到平衡。较高的负载因子会减少空间浪费但增加了哈希冲突的概率较低的负载因子会增加空间开销但减少哈希冲突。
如果已知HashMap的容量需求建议提前设定合适的初始容量以减少扩容带来的性能损耗。
4、哈希冲突链表法
当要塞入一个键值对的时候会根据一个hash算法计算key的hash值然后通过数组大小n-1 hash值之后得到一个数组的下标然后往那个位置塞入这个键值对
hash算法是可能产生冲突的且数组的大小是有限的所以很可能通过不同的key计算得到一样的下标因此为了解决键值对冲突的问题采用了链表法
在JDK1.7及之前链表的插入采用的是头插法即每当发生哈希冲突时新的节点总是插入到链表的头部老节点依次向后移动形成新的链表结构。
多线程的情况下头插法可能会导致链表形成环特别是在并发扩容时。
在JDK1.8的时候改成了尾插法即新节点插入到链表的尾部保持插入的顺序。
