Map概念:

  • 1.Map实现有很多种,基本都是key-value形式,hashMap实现采用的是hash表,而treeMap采用的是红黑树

hashMap

  • 1.实现了Map接口,允许一个NULL键和多个NULL值。非线程安全
  • 2.hash冲突:hash值冲突是发生在put()时,从源码可以看出,hash值是通过hash(key.hashCode())来获取的,当put的元素越来越多时,难免或出现不同的key产生相同的hash值问题,也即是hash冲突,当拿到一个hash值,通过indexFor(hash, table.length)获取数组下标,先查询是否存在该hash值,若不存在,则直接以Entry<V,V>的方式存放在数组中,若存在,则再对比key是否相同,若hash值和key都相同,则替换value,若hash值相同,key不相同,则形成一个单链表,将hash值相同,key不同的元素以Entry<V,V>的方式存放在链表中,这样就解决了hash冲突,这种方法叫做分离链表法,与之类似的方法还有一种叫做 开放定址法,开放定址法师采用线性探测(从相同hash值开始,继续寻找下一个可用的槽位)hashMap是数组,长度虽然可以扩大,但用线性探测法去查询槽位查不到时怎么办?因此hashMap采用了分离链表法
  • 3.在 HashMap 中不能用 get() 来判断是否存在某个 key,应该用 containsKey() 来判断

hashTable

  • 1.无论是 key 还是 value 都不能为 null。
  • 2.底层采用数组+链表实现
  • 3.HashTable是一个线程安全的类,它使用synchronized来锁住整张Hash表来实现线程安全,由于 Hashtable 中的所有数据都加了同步锁,即每次锁住整张表让线程独占,因此性能最差。
  • 4.HashMap 的迭代器(Iterator)是 fail-fast 迭代器,而 Hashtable 的 enumerator 迭代器不是 fail-fast 的。所以当有其它线程改变了 HashMap 的结构(增加或者移除元素),将会抛出 ConcurrentModificationException,但迭代器本身的 remove() 移除元素则不会抛出 ConcurrentModificationException。但这并不是一定发生的行为,要看 JVM。

currenthashMap

  • 1.currenthashMap底层采用分段的数组+链表实现
  • 2.ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分,每个段其实就是一个小的Hashtable,它们有自己的锁。只要多个修改操作发生在不同的段上,它们就可以并发进行。
  • Segment 代码如下:
    Segment.jpg

table.jpg
HashEntry.jpg
Put.jpg

  • 4.java.util.concurrent中提供的一个线程安全且高效的 HashMap 实现。在 JDK 1.7 中采用分段锁的方式;JDK 1.8 中直接采用了 CAS(无锁算法)+ sychronized。
    jdk1.7-CurrentHashMap.png

jdk1.8-CurrentHashMap.png

总结如下图:

Map.png

Last modification:November 2nd, 2020 at 11:01 am
如果觉得我的文章对你有用,请随意赞赏