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

Question

我在CodeSignal上参加了一次测试，但没能解决这个问题。

创建一个数据结构并实现以下操作。
插入 x y - 插入一个具有关键字x和值y的对象。
get x - 返回具有关键字x的对象的值。
addToKey x - 将x添加到map中的所有关键字中。
addToValue y - 将y添加到map中的所有值中。
每个操作的时间复杂度应为O(log(N))。

我能够在Java中使用数组和LinkedList创建哈希映射，但我没有办法使时间复杂度达到O(log(N))。 在我的实现中，插入和获取的时间复杂度为O(1)(最坏情况下为O(N))。而addToKey和addToValue的时间复杂度为O(N)，因为我必须遍历所有元素来修改键和值。
那么这个问题需要使用什么适当的数据结构呢？

- Ma Long

---

键和值是数字吗？如果不是，那么将x/y添加到所有键/值意味着什么？ - Eran

这是一个HashMap问题，但实际上是一道二叉搜索树问题。需要创建一个包含两个整数类型的节点，分别为键（key）和值（value），通过比较键（key）的大小来创建二叉搜索树。请完成翻译，不改变原意，尽量通俗易懂。 - Ezio

"addToValue y - 将y添加到映射中的所有值中。我怀疑这个操作最快需要O(N)的时间复杂度，或者如果你将添加值的总和单独保存在另一个变量中，那么可能可以做到O(1)的时间复杂度。" - Cid

@Cid 我也是这么想的，关键字必须是唯一的数字，因此只能更新一个关键字。在 hashMap 中不应该有多个关键字。 - Ezio

Answer 1

在 The Vee 和 Tom Elias 的有益评论后，经过编辑更正答案。

你不能通过遍历所有元素来实现 addToKey 和 addToValue，因为这需要像你认识到的那样线性时间。

相反，你可以保持一个keyDelta和valueDelta int 实例变量，它们保存应该添加到每个键和值上的值（或所有值的总和）。这是假设 addToKey 和 addToValue 应该将数值添加到键或值上。

addToKey 和 addToValue 只需要更新这些实例变量，这需要 O(1) 时间。

get(x) 操作将搜索 键 x - keyDelta 并在添加 valueDelta 后返回其对应的值。

请注意，add(x,y) 也需要更改，因为添加到 Map 中的键-值对不应受先前调用 addToKey 或 addToValue 的影响。如果 insert(x,y) 实际上将对 x - keyDelta, y - valueDelta 插入到 map 中，则可以实现此目标。

如果你使用 TreeMap 来实现键到值的映射，则 get 和 insert 将需要 O(logN) 时间。

- Eran

---

原则上，您可以只从新添加的键值对中减去当前的keyDelta和valueDelta，以节省此方法。 - The Vee

抱歉，我的意思是在它们插入的那一刻。这样它们在所有剩余的操作中都会与已经存在的内容保持一致。 - The Vee

他是正确的，每次插入不要用（key,value），而是使用（key-delta，value-delta）。当你“获取”时，总是返回（value-old delta+new delta）。祝你早安。 - Tom Elias

是的，这可能有效。谢谢 The Vee 和 Tom。 - Eran

嗨，@Eran，谢谢你的回答。你能提供一个TreeMap实现吗？ - Ma Long

@MaLong 可以直接使用 java.util.TreeMap。 - Eran