Это хорошая идея для генерации и хранения случайного числа в качестве значения хеш-функции для моего класса?

Question

У меня есть класс, который по существу оборачивает список, и списки, очевидно, не могут иметь хеш-значений. Моя идея состояла в том, чтобы сгенерировать случайное число и сохранить его как хеш-значение.

Answer 1

Если у вас есть два экземпляра, которые эквивалентны, они должны возвращать одинаковое значение __hash__.Если вы генерируете один случайным образом, вы не можете гарантировать, что это будет так, поэтому вы получите странное поведение.

Можете ли вы использовать кортеж вместо списка?Можете ли вы просто игнорировать список при вычислении хеша?Это нормально, если неравные объекты имеют столкновение.

Вы должны увидеть DictionaryKeys о том, почему списки не могут иметь хеш-значения.

Answer 2

Как уже упоминалось, a если два объекта считаются "равными", то они должны иметь одинаковое хеш-значение.

Как вы определяете equals для вашего класса, зависит от вас. Если вы заботитесь только о ссылочном равенстве, тогда вы можете сгенерировать случайное число на __init__, но лучше, если MyWrapper([1,2,3]) == MyWrapper([1,2,3]) равно False.

Причина, по которой вы не должны использовать содержимое списка в качестве хеша, как предлагает @iluxa, заключается в том, что если вы используете свой класс в качестве ключа в словаре, то измените содержимое так, чтобы значение хеша изменилось, это быть в состоянии найти этот ключ в словаре, поскольку он хранил старое значение хеш-функции и пытается найти новое.

Подводя итог:

1. Если a == b, тогда hash(a) == hash(b) должно быть истинным.
2. Если a != b тогда hash(a) != hash(b) должно быть правда большую часть времени для производительность поисков, но это не обязательно так.
3. The значение хеша не должно меняться между временем добавления его к dict (или любой другой на основе хеша структура поиска, которая не пересчитать хеш значения при поиске) и пытается найти его.

Последняя часть часто просто упрощается, чтобы значение хеша никогда не менялось.

Answer 3

Не очень хорошая идея.Общий контракт хеш-кода заключается в том, что если Объект A равен Объекту B, A.hashCode () равен B.hashCode ().С тем, что вы предлагаете, это не будет выполняться.

Вы можете попробовать использовать

• длину списка в качестве хеш-кода
• хеш-код первого элемента в спискекак хеш-код
• сумма всех хеш-кодов всех элементов, как хеш-код

или что-то еще в этом духе.

Answer 4

Целесообразно поддерживать хеширование для изменяемых контейнеров, но общее правило заключается в том, что вы хэшируете текущее значение, а не контейнер.

РЕДАКТИРОВАТЬ Это в принципе разумно, хотя Python обычно защищает от этого.

Для такого рода задач есть даже особая техника хеширования. Хэширование Zobrist вычисляет хэш постепенно, основываясь на каждом изменении контейнера, таким образом, что независимо от того, как вы достигаете определенного значения, вы получаете один и тот же хэш. Это используется в шахматных программах для обнаружения случаев, когда доска достигает одного и того же состояния через различные последовательности ходов, в качестве оптимизации для поиска по игровому дереву.

Вопрос здесь почему вы хотите найти список, используя поиск на основе хеша?

Если значение меняется, но вы все равно хотите найти один и тот же контейнер, то это может сработать (с проблемами коллизий) - но все равно это кажется бессмысленным. Случайное значение хеша - это просто некий идентификатор, идентифицирующий объект, на который вы ссылаетесь. Ссылка / указатель на объект является лучшим идентификатором. И как вы узнаете, какое хеш-значение нужно искать, если у вас все равно нет ссылки на объект?

Если вам нужна коллекция контейнеров, список списков - лучшее решение, чем словарь случайных хэшированных списков.

РЕДАКТИРОВАТЬ Возможное исключение, если вам нужна коллекция списков, где один и тот же список может быть добавлен более одного раза, но будет присутствовать в контейнере только один раз - набор экземпляров списка. В этом случае хэш должен основываться на IMO на основе ссылки на объект, но я не могу вспомнить, как это делается.