hashMap、ConcurrentHashMap、hashTable、TreeMap、LinkedHashMap用法区别详解 – 磊

hashMap、ConcurrentHashMap、hashTable、TreeMap、LinkedHashMap用法区别详解 - 磊

  1. Java集合中设计了一个接口Java.util.Map,它实现类中hashMaphashTableTreeMapConcurrentHashMapLinkedHashMap
  2. Map类型的集合用来做键值对存储的,也就是key-value形式的。所以不允许键重复,值是可以重复的。

hashMap

  1. hashMap 底层结构是:数组+链表+红黑树(jdk1.8之前就是存储的数组+链表)

    说明:

     数组的特点:查询效率高,插入,删除效率低。
     链表的特点:查询效率低,插入删除效率高。
     在HashMap底层使用数组加(链表+红黑树)的结构完美的解决了数组和链表的问题,使得查询和插入,删除的效率都很高。
     当链表的长度达到某个阀值(8)的时候,这个链表就将转换成红黑树。
     删除的时候可能导致红黑树转换为链表
     扩容也可能导致红黑树转化为链表 扩容有可能导致红黑树拆成两部分, 在这两部分中, 任意部分, 如果元素数量是小于等于6的话, 会由红黑树转化为链表。
     在jdk1.8中,如果链表长度大于8且节点数组长度大于64的时候,就把链表下所有的节点转为红黑树。树形化还有一个要求就是数组长度必须大于等于64,否则继续采用扩容策略
    
  2. 默认初始容量16, 负载因子0.75,扩容机制是原容量的2倍。且要求容量一定为2的整数次幂

    说明:用数组容量大小乘以负载因子得到一个值,当数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍。在扩容的时候会生成一个新的数组,原来的所有数据需要重新计算哈希码值重新分配到新的数组,所以扩容的操作非常消耗性能.

  3. 无序的,允许存null(键,值),线程不安全的。可以使用 Collections的synchronizedMap方法保证安全

  4. 存储过程
    说明:存储数据时计算KeyhashCode值%数组的长度得到对应的数组下标,如果这个下标没有值就直接存入,如果有值就会计算euqals()的值是不是相等,相等就覆盖,不相等就往下链。链的太多时会转换为红黑树。

LinkedHashMap

  1. LinkedHashMap是HashMap一个子类,基本完全复用和遵从HashMap的特点
  2. LinkedHashMap在HashMap的基础上维护了一个双向链表,意味着他是有序的。

TreeMap

  1. TreeMap它是基于红黑树的NavigableMap实现。(树中的每个节点的值都会大于或等于它的左子树中的所有节点的值,并且小于或等于它的右子树中的所有节点的值),实现了SortMap接口,能够对保存的记录根据键进行排序。
  2. 不允许NULL(键,值),线程不安全的
  3. 在TreeMap中存储数据时, key-value, 我们可以有两种方式: 一个就是让key本身可以比较(继承Comparable接口实现compareTo) 另一个就是可以在创建TreeMap的时候手动提供一个比较器

HashTable

  1. 无序,线程安全的(几乎所有的方法都加锁),不能存储null值,null键
  2. 底层结构是数组+链表
  3. 默认初始容量11,扩容时2倍+1。且不要求底层数组的容量一定要为2的整数次幂;

ConcurrentHashMap

  1. ConcurrentHashMap 是线程安全的,相比较HashTable,jdk1.8之前ConcurrentHashMap是分段锁(Segment),继承了ReentrantLock。jdk1.8开始线程安全性由synchronized 和 CAS 来保证。
  2. ConcurrentHashMap可以一边更新、一边遍历,也就是说在遍历的时候,ConcurrentHashMap也可以进行remove,put操作,且遍历的数据会随着remove,put操作产生变化。HashTable会抛异常。
  3. get方法没有加锁,remove put是要加锁的。
    说明:jdk1.8之前是分段锁,一般不会出现锁的争抢,jdk1.8开始分的更细了,使用cas机制添加到树的头节点,如果失败了,说明有其他线程在操作,那就再次循环上一步添加操作。如果头节点已经存在了,通过synchronized获得头节点锁,进行后续的操作。

总结

  1. 平常使用HashMap,访问速度快,效率高。
  2. 排序需求的,并且需要自定义排序规则的使用TreeMap。
  3. 线程安全并发的需求时考虑使用ConcurrentHashMap。
  4. 需要快速增删改查而且需要保证遍历和插入顺序一致的存储功能 LinkedHashMap。

补充

  1. 二叉树
    特点:左子节点的值小于父节点,右子节点的值大于父子节点。当有序列表时,会变成链表结构
  2. 平衡二叉树 AVL
    特点:和二叉树唯一不同的就是左子节点和右子节点的高度差最多等于1。
  3. 红黑树
    特点:通过左旋或者右旋维持树的平衡,因为AVL太严格,当树的节点发生变化时会破坏平衡。
hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » hashMap、ConcurrentHashMap、hashTable、TreeMap、LinkedHashMap用法区别详解 – 磊