java - 具有 O(log(N)) 时间复杂度操作的 HashMap

Question

我对 CodeSignal 进行了测试，但无法解决此问题。

Create a data structure that allows the following operations.
insert x y - insert an object with key x and value y.
get x - return the value of an object with key x.
addToKey x - add x to all keys in map
addToValue y -add y to all values in map.
Time complexity of each operation should be O(log(N))

我能够使用 Java 中的数组和 LinkedList 制作哈希映射。但是我无法将时间复杂度设为 O(log(N))。
在我的实现中，插入和获取的时间复杂度为 O(1)(最坏情况下为 O(N))。 addToKey 和 addToValue 的时间复杂度是 O(N)，因为我必须迭代所有元素来修改键和值。
这个问题的正确数据结构是什么？

Answer 1

在 The Vee 和 Tom Elias 的有益评论之后编辑以更正答案。
您无法实现 addToKey和 addToValue通过迭代所有元素，因为正如您意识到的那样，这需要线性时间。
相反，您可以保留一个 keyDelta和 valueDelta int保存应该分别添加到每个键和值的值(或所有值的总和)的实例变量。这是假设 addToKey和 addToValue应该向键或值添加数值。addToKey和 addToValue只需要更新那些实例变量，这需要 O(1) .get(x)操作将搜索 key x - keyDelta加上valueDelta后返回其对应的值到它。
请注意 add(x,y)还需要更改，因为添加到 Map 的键值对不应受到之前对 addToKey 的调用的影响。或 addToValue .如果 insert(x,y) 可以实现这一点实际上会插入一对 x - keyDelta, y - valueDelta到 map 。
如果您使用 TreeMap实现键到值的映射，get和 insert会花O(logN) .