java - Map的空间复杂度是多少>?

Question

我试图在 Java 中计算我的代码的空间复杂度，我只使用地图和列表，但我不确定它是O(n^2)或者O(n)为什么？.

Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
List<String> list = new ArrayList<String>();;
Map<String, Integer> map = new HashMap<String,Integer>() ;

通常另一个数据结构中的数据结构通常是 O(n^2) 对吗？

谢谢

Answer 1

定义n是什么会很有帮助，然后确定空间复杂度相对容易。我将n定义为放置在 HashMap 中的字符串数。我还将假设哈希表中的最小负载因子为 0.5。令I为 Integer 的大小，S为字符串的最大大小，H为散列表的单个槽使用的空间，L为散列表中列表的最大长度。

然后，对于一个最少填充的哈希表，将有n / L个占用的插槽，每个插槽最多有SL空间加上I用于分配的密钥。哈希表本身将占用2Hn / L空间——2 是由于负载因子。因此，总空间将为[(SL + I + 2H) / L] n，即O(n)。