欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

01-备战秋招之Map

程序员文章站 2022-04-03 09:54:13
一、概述Map 在 Java 里边是一个接口,常见的实现类有 HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap数据结构哈希表的实现: 数组+链表/红黑树LinkedHashMap 底层:数组+链表+双向链表TreeMap 底层:红黑树ConcurrentHashMap底层:数组+链表/红黑树二、hashMaphashMap 有几个构造方法,但最主要的就是指定初始值及负载因子的大小(默认hashmap的大小为16,负载因子的大小为0....

一、概述

  1. Map 在 Java 里边是一个接口,常见的实现类有 HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap
  2. 数据结构
    1. 哈希表的实现: 数组+链表/红黑树
    2. LinkedHashMap 底层:数组+链表+双向链表
    3. TreeMap 底层:红黑树
    4. ConcurrentHashMap底层:数组+链表/红黑树

二、hashMap

  1. hashMap 有几个构造方法,但最主要的就是指定初始值及负载因子的大小(默认hashmap的大小为16,负载因子的大小为0.75

  2. hashmap的大小只能是2次幂,举例:传入的值为10,实际上最终的 HashMap 的大小为16;传入一个7进去,hashmap最终的大小是8,具体的实现在 tableSizeFor可以看到

  3. 位运算:我们把元素放进HashMap的时候,需要算出这个元素所在的位置(hash),在HashMap里用的是位运算来代替取模,index = hash值 % 数组长度这样的话 index 的值就永远都在数组长度之内,也就可以作为数组下标了,但缺点是效率低。 所以采用减一与运算index = hash值 & (数组长度 - 1)
    01-备战秋招之Map

  4. 负载因子的大小决定着哈希表的扩容和哈希冲突。比如默认的hashmap 的大小为 16,负载因子为 0.75,这意味着数组最多只能放 12 个元素(16 * 0.75),一旦超过12 个元素,哈希表就需要扩容。每次 put 元素进去的时候,都会检查 HashMap 的大小有没有超过这个阈值,如果有,则需要扩容(由于HashMap 的大小只能是 2 次幂,所以扩容的时候默认是扩原来的 2 倍)。虽然扩容操作耗时,但也不推荐将负载因子调高(比如调至为 1,那 HashMap 就等到 16 个元素的时候才扩容,但负载因子调高则意味着哈希冲突的概率会增高,会导致查找的速度变慢)

  5. put 和 get 方法

    1. put 方法
      1. 首先调用 key 对象的 hashccode() 方法,获取 hashcode,根据 hashcode 计算出 hash值(要求在[0, 数组长度-1]区间),根据 hash 计算出该 key 所在的 index
      2. 如果没有碰撞,直接放到数组中,如果碰撞,需要判断目前数据结构是链表还是红黑树,根据不同的情况进行插入
      3. key 相同,则替换原来的值,最后判断哈希表是否满了(当前哈希表大小 * 负载因子),如果满了,则扩容
    2. get 方法
      1. 同put,根据 key 做 hash 运算,计算出该 key 所在的 index, 然后判断是否有 hash 冲突
      2. 有冲突直接返回,没有冲突则判断当前数据结构是链表还是红黑树,分别从不同的结构中取出。
  6. HashMap 中怎么判断一个元素是否相同?

    1. 首先比较 hash 值,随后用 == 或者 equals
    2. 计算hashcode使用的是杂凑算法,可能会让多个对象返回相同的杂凑值。hash值相同,那么

三、LinkedHashMap

  1. 底层是数组+链表+双向链表,继承了 HashMap,在HashMap基础上维护了一个双向链表,有了这个双向链表,插入可以是有序的(插入有序,非大小有序)
  2. LinkedHashMap 在遍历的时候实际用的是双向链表来遍历的,所以LinkedHashMap的大小不会影响到遍历的性能。

四、TreeMap

  1. TreeMap的key不能为null(如果为 null,那还怎么没排序?),TreeMap有序是通过 Comparator 来进行比较的,如果 comparator 为 null,那么就使用自然顺序。

五、线程安全的 Map

  1. HashMap 不是线程安全的,在多线程环境下, HashMap可能会有数据丢失和获取不了最新数据的问题,比如说:线程A put 进去了,线程B get 不出来。
  2. 若想线程安全,一般使用 ConcurrentHashMap,是线程安全的Map实现类,它在juc包下。支持高并发的访问和更新。ConcurrentHashMap通过在部分加锁和利用CAS算法来实现同步,在get的时候没有加锁,Node用了volatile 来修饰。在扩容时,会给每个线程分配对应的区间,并且为了防止putVal导致数据不一致,会给线程所负责区间加锁
  3. 此外,还有 HashTable 实现类。或者使用 Collections 来包装出一个线程安全的Map。但无论是HashTable还是Collections包装出来的都比较低效(因为直接在外层套synchronize),所以我们一般有线程安全问题的考量,都是用 ConcurrentHashMap。

本文地址:https://blog.csdn.net/weixin_45501561/article/details/114300008