Java Map & Set特点

2020-09-09  87 次阅读


本文最后更新于2021年5月24日,已超过 1 个月没更新!

—— Java 集合体系 ——

  • 一个Collection集合体系: 存储单个数据
  • 一个是Map集合体系: 存储key-value数据

一、Map接口

1.1 特点

  1. Map接口是Map集合体系的顶级接口
  2. 和Collection接口以及Collection下面自实现不同的是 , Map所存储的数据不再是单个数据的, 而是Key-value类型的数据( 键值对 )
  3. Map的自实现有些是有序的, 有些是无序的
  4. Map的自实现不允许存储重复元素(指key值)( 重复元素的定义)
  5. Map有些子实现可以存储null, 有些子实现不允许存储null(指key值)

2.2 HashMap

  1. HashMap是Map接口的子实现(存储的是key-value数据);
  2. HashMap表示一个Hash表;
  3. HashMap的底层结构: 数组 + 链表 + 红黑树(jdk1.8之前是存储的数组 + 链表);
  4. HashMap的效率非常高: 存储/查找;
  5. HashMap的默认初始容量 16,数组的扩容机制 2 倍;
  6. HashMap存储的key-value数据,经过散列之后是无序的;
  7. HashMap不允许存储重复元素key: (重复的定义);
  8. 存储 null 值(key-value都允许为null);
  9. 线程不安全;
  10. HashMap 加载因子默认是0.75:尽量保证加载因子在0.5 ~ 1之间 (用空间换时间);
    • HashMap底层数组的扩容阈值 = 数组长度 * 加载因子
  11. sh值的计算: (h = key.hashCode()) ^ (h >>> 16);
    • 由于我们HashMap在做根据hash值取模运算的时候, 只有低位参与了运算, 但是HashMap本身是非常希望这个hash散列足够充分的. 希望hashCode的值高位也参加取模运算, 希望充分散列 ( 高位和低位都参与最终的取模运算, 以使散列更充分)
  12. HashMap的底层数组, 是一个Node类型的数组, 这个Node类型包含四个参数, 分别是hash值, key, value, next;
  13. 最终存储到HashMap中的是一个结点类型, 这个结点类型包含四个参数(hash值, key, value, next);
  14. HashMap的重复的定义: 首先hash值是否一样, hash一样的情况下, 两个key值是否直接相等 或者相equals;
  15. 如果存储的数据key已经存在(key重复了), 那么会用新的value值覆盖已经存储的value值(旧value值);
  16. 如果我们把一份数据key-value(已经存储到HashMap中)中的key通过引用修改, 注意有可能删不掉, 也就意味着, 一份key-value数据, 一旦存储到hashmap中就不要通过引用修改key了;
  17. 当链表长度超过 8,达到 9 的时候(算上新添加上的元素),会由链表转化为红黑树;
    • 当链表长度超过 8,达到 9 的时候(算上新添加上的元素),如果同时数组长度小于 64 的时候,会优先选择扩容,而非转化为红黑树;
      (注意: 如果扩容的时候,原本存在于x位置的元素,可能依旧存储在x,还有可能存储到 旧长度 + x的位置);
    • 如果链表转化为红黑树,红黑树是一个特殊的二叉搜索树,需要比较大小,在HashMap中红黑树比较大小的方式是通过 hash 值进行的。
  18. 删除有可能导致红黑树转化为链表;
    • if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) {
          tab[index] = first.untreeify(map);  //反树化操作: 树转化为链表
          return;
      }
      
    • 删除的时候,如果根节点是null 或者根节点的左右结点是null,或者根节点左节点左节点是null,这四个结点任一个是null,都要由红黑树转化为链表。
  19. 扩容也可能导致红黑树转化为链表
    • 扩容有可能导致红黑树拆成两部分,在这两部分中,任意部分,如果元素数量是小于等于 6 的话,会由红黑树转化为链表。

注意1: HashMap的存储思想

如果我们要在HashMap存储一份数据(key = value),那么首先:

  • 把要存储的数据的key值拿出来,
  • 通过一系列计算:
    • kay ->计算出一个数(hash值): (h = key.hashCode()) ^ (h >>> 16);
      static final int hash(Object key) {
          int h;
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }
      
    • Hash值 -> 取余(数组长度) i = (n - 1) & hash -> 数组下标。
  • 最终求得的数组下标对应的位置就是这份 key-value 数据要存储的位置。

:jdk1.8确定map坐标的方式是tab[(n-1)&hash],n代表map的length;
由于和(length-1)进行运算,length的长度多数情况下小于2^16,始终是hashcode的低16位参与运算,甚至更低,因此要让高16位也参与运算使得下标更加散列。

注意2: 到底什么时候链表会转化为红黑树?

当链表长度达到 9 的时候(算上新添加上的元素),会由链表转化为红黑树

2.3 LinkedHashMap

  1. LinkedHashMap是HashMap一个子类
  2. LinkedHashMap基本上完全复用了HashMap的底层结构,参数,方法
  3. LinkedHashMap的特点基本遵从于HashMap
  4. LinkedHashMap底层在HashMap的基础上(数组+链表+红黑树)额外维护了一个双向链表: 这个双向链表用来记录存储顺序 -> 意味着LinkedHashMap是有序的

彻头彻尾理解 LinkedHashMap

2.4 TreeMap

  1. TreeMap是Map一个子实现
  2. 底层是红黑树
  3. TreeMap大小有序
  4. 不允许重复的key
  5. 不允许null键
  6. 线程不安全
  7. Treemap的重复的定义: 大小比较结果是0; 自然顺序/比较器
  8. 如果我们希望在TreeMap中存储数据, key-value, 我们可以有两个选择
    • 第一个选择, 让key本身可以比较(继承Comparable接口实现compareTo)
    • 第二个选择(优先选择此方法), 不想让key本身实现Comparable接口实现compareTo方法, 那么就可以在创建TreeMap的时候手动提供一个比较器

2.5 Hashtable

HashMap和Hashtable的区别?

  • Hashtable: jdk1.0产生的
  • HashMap : jdk1.2产生的
  1. 线程安全问题
    • HashMap线程不安全
    • Hashtable 线程安全
  2. 底层结构
    • HashMap: 底层是数组+链表+红黑树(jdk1.8)
    • Hashtable: 底层是数组+链表(和jdk1.8之前的HashMap是一样的)
  3. 数组默认初始容量以及扩容机制
    • HashMap: 默认初始容量16以及扩容机制2倍
    • Hashtable: 默认初始容量11以及扩容机制(2倍+1) (除留余数法)
  4. 能不能存储null
    • HashMap: 可以存储null键以及null值
    • Hashtable: 不可以存储null键, 也不可以存储null值

HashMap 和 ConcurrentHashMap 的区别?

  1. ConcurrentHashMap 底层采用分段的数组+链表实现,线程安全
  2. Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术
    • 首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。
  3. ConcurrentHashMap默认将hash表分为16个桶,诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样,原来只能一个线程进入,现在却能同时有16个写线程执行,并发性能的提升是显而易见的。
  4. ConcurrentHashMap扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容

2.6 properties

Properties 是 Hashtable的一个子类,主要就是用来做持久化的

  • 持久化: 代码在运行的过程中(内存), 有可能产生一些数据, 这个数据有时候我们希望立马存在本地磁盘文件上。

如果在使用Properties的时候,不要使用从Hashtable那继承来的方法,因为持久化的时候要求数据key-value都必须是字符串。
输出的两种文件格式: Xml、Properties


二、Set接口

2.1 特点

  1. Set接口是Collection的子接口
  2. 描述的是集合这种数据结构
  3. 一部分子实现是有序的(LinkedHashSet, TreeSet),另一部分子实现是无序的(HashSet)
  4. 一部分子实现允许存储null(LinkedHashSet, HashSet),另一部分子实现不允许存储null(TreeSet)
  5. 都是不允许重复元素

2.2 HashSet

  1. HashSet是Set接口一个具体子实现
  2. HashSet的底层持有一个HashMap对象, 所有存储到HashSet中的元素, 实际上都存储到HashSet所持有的HashMap中作为key存在
  3. 由于它的底层持有的是HashMap对象, 所以无序
  4. 不允许存储重复元素: 存储的元素hash值一样, 并且 两个元素直接相等或者相equals
  5. 允许存储null元素
  6. 其它特点遵从于HashMap(因为底层持有一个HashMap对象, 负责存储数据)

2.3 LinkedHashSet

  1. LinkedHashSet是HashSet的一个子类(LinkedHashSet复用HashSet的方法)
  2. LinkedHashSet底层持有一个LinkedHashMap对象, 它是在HashMap结构(数组+链表+红黑树)上的增强, 多维护了一个双向链表
  3. LinkedHashSet存储的元素是有序的(通过底层的双向链表保证有序)
  4. LinkedHashSet 不允许存储重复的元素
  5. LinkedHashSet 允许存储null
  6. 其它特点遵照于HashSet, LinkedHashMap,  HashMap

2.4 TreeSet

  1. TreeSet是Set接口一个子类, 描述的数据结构是一个红黑树
  2. TreeSet底层持有一个TreeMap对象, 这个TreeMap对象的底层是红黑树
  3. 大小有序
  4. 不允许重复元素; 比较大小的重复
  5. 不允许存储null, 因为null没有办法比较大小
  6. 线程不安全

注:比较器排序的优先级高于自然排序的优先级


Try and fail, but don't fail to try.