大小有效的字典（关联数组）实现

Question

有哪些算法可用于大小高效A dictionary or associative array？ 例如，使用这个键/值集，如何避免值中的重复“Alice”？在

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

我检查了Python's implementation on dictionary，但似乎实现的重点是速度（保持O（1））而不是大小。在

Answer 1

提高空间效率的一种方法（除了共享值，正如bennofs在评论中指出的那样），您可以通过使用系统实习生)是使用hopscotch hashing，这是一种用于解决冲突的开放寻址方案（线性探测的一种变体）——闭合寻址方案使用更多空间，因为您需要为每个bucket分配一个链表，而对于开放寻址方案，您只需在后备数组中使用一个打开的相邻插槽，而不需要分配任何链表。与其他开放寻址方案（如布谷鸟哈希或香草线性探测）不同，跳房子哈希算法在高负载因子（超过90%）下表现良好，并保证了恒定的时间查找。在