HashMap与ConcurrentHashMap

double线程

HashMap是一个数组,数组中的每个元素是链表。当put元素进去的时候,会先通过计算key的hash值来获取到一个index,根据index找到数组中的位置,进行元素插入。当新来的元素映射到冲突的数组位置时,只需要插入到对应链表位置即可,新来的元素是插入到链表的头部。

Java中HashMap是利用“拉链法”处理HashCode的碰撞问题。在调用HashMap的put方法或get方法时,都会首先调用hashcode方法,去查找相关的key,当有冲突时,再调用equals方法。hashMap基于hasing原理,我们通过put和get方法存取对象。

当我们将键值对传递给put方法时,他调用键对象的hashCode()方法来计算hashCode,然后找到bucket(哈希桶)位置来存储对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当碰撞发生了,对象将会存储在链表的下一个节点中。

hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时,他们会存储在同一个bucket位置的链表中。键对象的equals()来找到键值对

HashMap和ConcurrentHashMap

HashMap 底层是基于 数组 + 链表 组成的,在 jdk 1.7 和 1.8 中具体实现会有不同

HashMap

  • 在HashMap 中,key 为什么要转成hashCode, 然后在进行补码?

1.7 的实现

是用的是 HashEntry 内部类实现,存在一个很明显的问题就是:

当 Hash 冲突严重时,在桶上形成的链表会变的越来越长,这样查询的效率会越来越低;时间复杂度为 O(N)

1.8 的实现

① 是用尾插法扩容 java7以前都是头插法 所以java8不会有 死循环问题
② 如何判断把链表转换成红黑树的呐?

  • 将 HashEntry 改为了 node 节点
  • 增加了是否将链表转化为红黑数的阈值

性能问题

  • 当数量 大于 容量值*负载因子时,就会发生扩容,而扩容这个过程涉及到 rehash、复制数据等操作,所以非常消耗性能。
  • 在高并发场景下使用容易出现死循环,导致系统不可用

产生死循环的主要原因是 HashMap 扩容的时候会调用 resize() 方法,就是这里在并发操作容易在一个桶上形成环形链表,这样当获取一个不存在的key时,计算出的 index 正好是环形链表的下标就会出现死循环。

ConcurrentHashMap

concurrentHashMap 是专门为了解决高并发问题的

1.7 的实现

主要是有 segment 数组、HashEntry 组成,和 HashMap 一样仍然是数组加链表组成。

1.8 的实现

  • 优化1.7版本的查询遍历链表效率太低问题
  • 抛弃了原有的 segment 分段锁,采用了 CAS + synchronized 来保证并发安全性
  • 将 1.7 中存放数据的 HashEntry 改为 Node,其中 Node 节点 next 使用 volatile 修饰保证了可见性

知识疑问

  1. HashMap 底层为什么一定用数组?
    ① 数组的查询效率高: 在HashMap中,定位桶的位置是通过利用元素key的hash值对数组的长度取模得到。此时我们已得到桶的位置,显然数组的查找效率比 LinkedList 大。
    ② 可自定义扩容机制: 采用基本数据结构,扩容机制可以自己定义,HashMap中数组的扩容刚好是2的次幕,在做取模运算的效率高。

  2. hashMap中的链表到底有什么作用?
    是为了防止 hash 碰撞,因为有些对象的 hashCode 在进行 hash 操作时后可能得到的 index 是用一个值,这个时候会把冲突的放到当前桶后面的链表中,这是哈希算法中解决冲突的一种方法,叫做地址法(拉链法)。

  3. hashCode的作用
    hashMap其实就是形象的将一个数组分类了,而数组的每一个下标表示一个桶,每一个桶就是一个域,每次查找时会先算出这个内容的hashCode,就可以知道在哪个域里面了,这将省很多的迭代过程。

参考文章

HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!
Java:HashMap原理与设计缘由
Java HashMap原理详解