幂等散列关联

Question

我有一些名字：["James", "John", "Krieg"]和一些颜色：["Red", "Green", "Blue", "Yellow"]。我想使用一些散列函数将名称映射到颜色：f(name) -> color。这个关联是幂等的。例如，如果在原始列表中，f(James) -> Red，那么在我将名称或颜色添加到它们各自的列表之后，f(James)仍然是{}。在

示例：

列表状态1：

["James", "John", "Krieg"] and ["Red", "Green", "Blue", "Yellow"]: 
    f(James) -> Red
    f(John) -> Yellow 
    f(Krieg) -> Yellow

列表状态2：

^{pr2}$

哈希函数的细节并不重要，只要它尝试统一。我有这个问题是因为我有一个显示给用户的名称列表，随着该列表的增长，我希望先前输入的名称的颜色关联保持不变（因此用户保留名称/颜色关联）。我意识到如果我事先指定颜色列表，这不会是个问题。在

所以现在只是出于好奇——有没有散列函数在输入/输出大小增长时不改变先前关联的值，而没有持久性？很抱歉之前的混乱。在

Answer 1

你说得对，你只需要把关联存储在内存中。你需要的是一个可变的关联集。在python中，这是一个字典：

>>> assocs = dict(zip(['James', 'John', 'Krieg', 'Sarah'], ['Red', 'Green', 'Blue', 'Yellow']))
>>> assocs['Sarah']
'Yellow'
>>> assocs['Sarah'] = 'Black'
>>> assocs['Sarah']
'Black'

编辑

如果始终有两个列表，并且它们总是按顺序排列，那么为什么不使用列表索引来“存储”映射：

^{pr2}$

希望有帮助

Answer 2

我要说的是，没有坚持就不会有这样的事情。在

我们可以排除基于列表位置的任何映射。让我们从N个名称和1个颜色开始-这意味着所有名称都映射到一种颜色。如果我们以后有N个名称和M个颜色，除非我们可以存储哪些N个名称映射到第一种颜色，否则就无法实现这一点。在

同样，我们可以根据名称/颜色的值来排除任何问题。假设我们有一个函数f（name，color），它提供了一个分数来决定一个名字的最佳颜色。如果F（bob，green）>；F（bob，red），那么当我们的列表从[bob], [red]到{}时，我们将得到一个不同的映射。在

您可以想出一些退化的解决方案，这些方案不显式地“保存每个关联”，但仍然保持足够的状态来重新创建计算。充其量，这些存储的数据与简单地存储您的映射一样多。在最坏的情况下，他们会储存更多。在

幂等数的使用表明你最初的问题可能是抽象的好奇心。如果你想解决一个特别的、实际的问题，对这个问题有更具体的解释会有所帮助。在

Answer 3

我不太清楚你说的“一个快速的方法”是什么意思，但我认为一个幂等字典可能会有帮助。例如：

##!/usr/bin/env python
# coding: utf-8

class idempotent_dict(dict):
    def __setitem__(self, key, value):
        if key in self:
            return
        super(idempotent_dict, self).__setitem__(key, value)

if __name__ == '__main__':
    d = idempotent_dict()

    d['James'] = 'Red'
    d['John'] = 'Yellow'
    d['Krieg'] = 'Yellow'

    print d

    d['James'] = 'Black'
    d['John'] = 'Red'
    d['Sarah'] = 'Green'

    print d

打印：

^{pr2}$