Хеширование неопределенных объектов

Question

Мне нужно спроектировать объект, который поддерживает некоторую неопределенность (или дикие символы, если хотите) его компонентов.Работа сделана на Python.

Рассмотрим следующий класс

class C():
    def __init__(self, p1):
        self.p1 = p1

Свойство p1 может быть либо "x", "y", "z", но иногда "x"или y ", или любая другая комбинация.

Требуется, чтобы, если p1 из c1 было 'x', а p1 из c2 было 'x или y', то c1 == c2вернет True.Это легко достигается с помощью правильной функции __eq__.Однако эти объекты также должны храниться в наборах, поэтому мне нужно предоставить функцию __hash__.Как бы вы вычислили хеш-функцию для этого случая, например, если c1 == c2 затем hash(c1) == hash(c2)?

Вариант 1: хеширование свойства

Не хорошо Вот почему

c1 = C('x')
c2  = C('x or y or z')
c1 == c2 #True
hash(c1) == hash(c2)#False

Answer 1

Ваш критерий равенства не является транзитивным и, следовательно, недействительным:

C('x') == C('x or y') == C('y')

но

C('x') != C('y')

Поскольку вы можете создать элемент, равный всем остальным C('x or y or z or a or ...'), единственная хеш-функция, которая выполняет c1 == c2 ⇒ hash (c1) == hash (c2), является константой, т.е.

def __hash__(self):
    return 0

Answer 2

Самое простое решение - заставить все ваши объекты возвращать одинаковый хеш.Это снижает установленную производительность O (1) до O (n), так как все содержащиеся объекты будут вставлены в один и тот же слот.Затем будет проведено разграничение по методу __eq__.

Что касается ваших требований, Дэвид уже подробно ответил.

Answer 3

Требуется, чтобы, если p1 из c1 было 'x', а p1 из c2 было 'x или y', то c1 == c2 вернет True.

Это очень схематичный (то есть, вероятно, плохой) дизайн.Равенство должно быть транзитивным, так что если c1 == c2 и c2 == c3, то c1 == c3.Теперь ваша спецификация требует, чтобы C('x') == C('x or y') и C('x or y') == C('y'), что должно подразумевать, что C('x') == C('y') - но вы, вероятно, не хотите, чтобы это было правдой.(И я вижу, что вы поняли это, когда я писал это.)

Я хотел бы предложить, чтобы вы оставили __eq__ в покое и использовали совершенно другой метод для выполнения этих «нечетких» сравнений, возможно, что-токак is_compatible_with.Или, если вы собираетесь переопределить __eq__, по крайней мере, сделайте что-то разумное, что подчиняется переходному свойству, например, просто сравнивая строковые аргументы.Это может означать, что __eq__ не очень полезен для вашего конкретного приложения, но это нормально;вот почему вы можете создавать другие методы.

Answer 4

Я только что понял, что мое проектное требование неверно.Требование, чтобы C ('x') == C ('x or y') было True, а C ('y') == C ('x or y') - True, также потребует, чтобы C ('x') == C ('y') также будет True.Похоже, мне нужно переосмыслить свой дизайн и, возможно, отказаться от возможности иметь хеши объектов.Что ты думаешь?