TreeSet

  • 基于treemap实现的有序集合，TreeSet 不是直接继承自 TreeMap，而是通过内部维护一个 TreeMap 实例来实现自己的功能。entry只有key，没有value。
  • 不能有重复对象
  • TreeSet中的元素支持2种排序方式：自然排序或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
  • 因为维护了一个内部treeset，所以treeset等于是通过红黑树实现
  • treeset非线程安全

TreeMap

  • TreeMap 本质上就是一棵“红黑树”，而 TreeMap 的每个 Entry 就是该红黑树的一个节点。
  • hashmap和treemap都是通过对象来对对象进行索引的Map集合，用来索引的对象叫做key，索引对应的对象叫做value。
  • 数据结构：treemap基于红黑树实现，hashmap基于哈希表+链表/红黑树实现。两者都是在存储entry这种结构。
  • 效率：treemap时间复杂度$O(logn)$，hashmap时间复杂度$O(1)$。
  • 线程安全：两者都是非线程安全，线程安全要使用ConcurrentHashMap。
  • 应用场景：HashMap是无序的，而TreeMap是有序的。
  • treemap可以插入值为null的entry。键不能为null。

HashMap( JDK 1.8 )

  • hashmap可以存放值为空的entry，值为空的可以多个。也可以存储键为null的entry，但是只能有一个。但是null作为键是没有hashcode的，所以会被存储在一个固定的地方。
1
2
3
4
5
6
7
8
9
10
11
// 创建一个 HashMap
Map<Integer, Integer> sites = new HashMap<>();
// 往 HashMap 添加一些元素
sites.put(null, 1);
System.out.println("HashMap: " + sites);
sites.put(2,null);
System.out.println("HashMap: " + sites);
sites.put(3,null);
System.out.println("HashMap: " + sites);
sites.put(null,null);
System.out.println("HashMap: " + sites);

运行结果：

1
2
3
4
5
6
HashMap: {null=1}
HashMap: {null=1, 2=null}
HashMap: {null=1, 2=null, 3=null}
HashMap: {null=null, 2=null, 3=null}

Process finished with exit code 0

https://github.com/brucewayne9064/Algorithms/tree/main/HashMap

JDK1.8之前的hashmap由链表加数组组成，数组是HashMap的主体，链表是为了使用拉链法解决哈希冲突而存在的。

JDK1.8之后，又引入了红黑树。

根据元素数量进行扩容

当HashMap中的元素数量超过一定的阈值（由负载因子决定）时，会触发扩容操作，通常是将底层数组的大小翻倍。HashMap 默认的初始化大小为 16。并且， HashMap 总是使用 2 的幂作为哈希表的大小。

在进行rehashing的时候，哈希函数和哈希值不会改变，但是由于数组容量变化，所以每个键的哈希值对数组大小进行模运算后的结果可能会改变，从而导致元素在数组中的位置发生变化。

将链表转换为红黑树

如果链表的长度大于等于阈值（8），会触发判断：

  • 如果当前的数组长度小于64，那么先进行数组扩容，然后进行rehashing（会遍历旧数组，对每个键值对使用相同的哈希函数重新计算索引，然后将其放置到新数组的正确位置上）。
  • 如果当前的数组长度大于等于64，将链表转化为红黑树，以减少搜索时间。