因为HashCode 相同,不一定就是相等的(equals方法比较),所以两个对象所在数组的下标相同,"碰撞"就此发生。又因为 HashMap 使用链表存储对象,这个 Node 会存储到链表中。
hash 函数是先拿到通过 key 的 hashCode ,是 32 位的 int 值,然后让 hashCode 的高 16 位和低 16 位进行异或操作。两个好处:
因为 key.hashCode()函数调用的是 key 键值类型自带的哈希函数,返回 int 型散列值。int 值范围为**-2147483648~2147483647**,前后加起来大概 40 亿的映射空间。只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组,内存是放不下的。
设想,如果 HashMap 数组的初始大小才 16,用之前需要对数组的长度取模运算,得到的余数才能用来访问数组下标。
保证了对象的 hashCode 的 32 位值只要有一位发生改变,整个 hash() 返回值就会改变。尽可能的减少碰撞。
①table 数组大小是由 capacity 这个参数确定的,默认是16,也可以构造时传入,最大限制是2^30;
②loadFactor 是装载因子,主要目的是用来确认table 数组是否需要动态扩展,默认值是0.75,比如table 数组大小为 16,装载因子为 0.75 时,threshold 就是12,当 table 的实际大小超过 12 时,table就需要动态扩容;
③扩容时,调用 resize() 方法,将 table 长度变为原来的两倍(注意是 table 长度,而不是 threshold);
④如果数据很大的情况下,扩展时将会带来性能的损失,在性能要求很高的地方,这种损失很可能很致命。
loadFactor表示HashMap的拥挤程度,影响hash操作到同一个数组位置的概率。
默认loadFactor等于0.75,当HashMap里面容纳的元素已经达到HashMap数组长度的75%时,表示HashMap太挤了,需要扩容,在HashMap的构造器中可以定制loadFactor。
hashMap在put的时候是:
对key的hashCode进行hash值计算,与运算计算下标获取bucket位置,如果在桶的首位上就可以找到就直接返回,否则在树中找或者链表中遍历找,如果有hash冲突,则利用equals方法去遍历链表查找节点。
创建一个新的数组,其容量为旧数组的两倍
之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。
红黑树是一种自平衡的二叉查找树,是一种高效的查找树。
1.在java 1.8中,如果链表的长度超过了8,那么链表将转换为红黑树
2.发生hash碰撞时,java 1.7 会在链表的头部插入,而java 1.8会在链表的尾部插入
3.在java 1.8中,Entry被Node替代
平时可能大家使用的最多的就是使用 String 作为 HashMap 的 key,但是现在我们想使用某个自定 义类作为 HashMap 的 key,那就需要注意以下几点:
为了能让 HashMap 存数据和取数据的效率高,尽可能地减少 hash 值的碰撞,也就是说尽量把数 据能均匀的分配,每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现。下面是回答的重点哟:
取余(%)操作中如果除数是 2 的幂次,则等价于与其除数减一的与(&)操作(也就是说 hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方)。并且,采用二进 制位操作 & ,相对于 % 能够提高运算效率。
这就是为什么 HashMap 的长度需要 2 的 N 次方了。
fail-fast 机制是 Java 集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行 操作时,就可能会产生 fail-fast 事件。
例如:当某一个线程 A 通过 iterator 去遍历某集合的过程中,若该集合的内容被其他线程所改变 了,那么线程 A 访问集合时,就会抛出 ConcurrentModificationException 异常,产生 fail-fast 事 件。这里的操作主要是指 add、remove 和 clear,对集合元素个数进行修改。
解决办法
建议使用“java.util.concurrent 包下的类”去取代“java.util 包下的类”。可以这么理解:在遍历之前,把 modCount 记下来 expectModCount,后面 expectModCount 去 和 modCount 进行比较,如果不相等了,证明已并发了,被修改了,于是抛出 ConcurrentModificationException 异常。
多线程条件下,可使用两种方式:
HashTable:使用一把锁(锁住整个链表结构)处理并发问题,多个线程竞争一把锁,容易阻塞;
ConcurrentHashMap:
JDK 1.8 中,采用Node + CAS + Synchronized来保证并发安全。取消类 Segment,直接用 table 数组存储键值对;当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD 时,链表转换为红黑树,提升性能。底层变更为数组 + 链表 + 红黑树。
①粒度降低了;
②JVM 开发团队没有放弃 synchronized,而且基于 JVM 的 synchronized 优化空间更大,更加自然。
③在大量的数据操作下,对于 JVM 的内存压力,基于 API 的 ReentrantLock 会开销更多的内存。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。