HashMap的时间复杂度

HashMap的get/put方法的时间复杂度，主要取决于哈希算法，如果有一个优秀的哈希算法，那么时间复杂度就是O（1），如果哈希算法中，多个元素拥有相同的哈希码，get需要对这些元素使用equals进行迭代匹配。

最坏的情况，会遍历哈希桶中的所有元素（例如，如果它们都具有相同的哈希代码），时间复杂度就是O（n）

在JDK8中，HashMap进行了调整，这样，如果可以比较键进行排序，那么相同hash值的元素都将被实现为一棵树，树的查找复杂度为log n， 因此即使有很多元素具有相同的哈希代码，复杂性也为O（log n）。 当然，如果根据排序获取到的元素，却不equals，这可能会导致问题。

如果你没有足够的内存来存储哈希图，无论你使用什么数据结构，复杂度都会很高。