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

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所述，可以使用^{}确保相同的字符串只存储一次：

class InternDict(dict):

    def __setitem__(self, key, value):
        if isinstance(value, str):
            super(InternDict, self).__setitem__(key, intern(value))
        else:
            super(InternDict, self).__setitem__(key, value)

下面是一个效果的例子：

^{pr2}$

Answer 2

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

Answer 3

• 如果你的字典可以放入内存，那么可以使用一个简单的哈希表。

尝试在哈希表中插入每个键值。 如果在插入之前密钥已经存在，那么您已经发现了一个重复项。 在许多语言中，hashtable有许多实现。在

基本上有两种方法：数组和树。在

• Array在高内存开销下关注速度。哈希表实现的主要区别是在unicity上的行为，有些实现强制unicity，有些实现强制unicity。

• 树集中在以O（log（n））cpu使用为代价的内存智能使用。g++映射依赖于非常强大的red black tree。

如果大小是非常有问题的，那么您应该搜索Huffman压缩和/或Lampel Ziv压缩，但它的成本要高一点，以适应词典。在

• 如果你的单词记不住了

你应该看看数据库。 数据库的红黑树被称为BTree（几乎）。它有针对低延迟硬盘驱动器情况的分支因子优化。在

我在维基百科上放了很多链接，但是如果你喜欢这个主题，我建议你：