Java中存储Vector与Integer的HashSet.add()时间复杂度对比及TreeSet分析

首先看你定义的两个HashSet：

HashSet<Integer> H1 = new HashSet<>();
HashSet<Vector> H2 = new HashSet<>();

一、HashSet的add()时间复杂度对比 #

HashSet的add()操作时间复杂度，核心由哈希值计算、equals()比较、哈希冲突处理三个环节决定。

• 对于HashSet<Integer>：
  Integer的hashCode()直接返回自身数值，equals()是简单的数值比对，这两个操作都是O(1)的常数时间。在哈希冲突概率可控的前提下，add()的整体时间复杂度为O(1)。

• 对于HashSet<Vector>：
  Vector继承自AbstractList，它的hashCode()会遍历所有元素计算累加哈希值，equals()也会逐个比对元素是否相等。这会带来两种情况：

  • 如果存储的Vector元素数量固定且极少，hashCode()和equals()的开销接近常数，add()的时间复杂度渐近级别仍为O(1)，只是实际执行的常数开销比存Integer更大。
  • 如果存储的Vector元素数量很多，hashCode()和equals()的时间会变成O(n)（n为Vector内元素的数量），此时add()的时间复杂度会退化为O(n)。
    注意：只有当Vector的元素数量随HashSet的元素数量增长而同步增加时，才会改变add()的渐近复杂度；若单个Vector的元素数量固定，即使HashSet元素增多，渐近复杂度还是O(1)。

二、TreeSet的add()时间复杂度对比 #

TreeSet基于红黑树实现，add()操作的基础时间复杂度是O(log m)（m为TreeSet内元素的数量），这个复杂度的实际开销取决于元素比较操作的耗时。

• 对于TreeSet<Integer>：
  Integer实现了Comparable接口，compareTo()是简单的数值比较，耗时O(1)，因此add()的整体时间复杂度为O(log m)。

• 对于TreeSet<Vector>：
  Vector本身未实现Comparable接口，直接使用会抛出ClassCastException，必须自定义Comparator。根据比较逻辑的不同：

  • 如果Comparator仅基于Vector的少量固定元素做比较（比如只比第一个元素），比较操作耗时O(1)，add()的时间复杂度仍为O(log m)，常数开销比存Integer更大。
  • 如果Comparator需要遍历Vector的所有元素做全量比较（比如字典序比对），且Vector内元素数量为n，那么单次比较耗时O(n)，此时add()的时间复杂度变为O(n * log m)。

内容的提问来源于stack exchange，提问作者codexistent