Мелочь, но важно.

[thesz]

Подумал я о необходимости хеш-функции для множеств. Чтобы из хеша для set и элемента a быстро получить hash setHash a. Ну, и чтобы порядок получения множества не влиял на результат: hash (hash set a) b = hash (hash set b) a.

Пришел к выводу, что это возможно с помощью hash hashSet a = hashSet `xor` cryptoHash aВроде, всё соблюдается. Особенно,

Comments

[nponeccop]

Ещё решение со сложением по модулю.

[thesz]

Вот спасибо!

[soloviewoff]

Да, вроде нормально - благодаря коммутативности xor'а. Дополнительный бонус - можно обновлять таким же макаром хеш и при удалении.

При добавлении дубликатов надо осторожно.

[thesz]

Правильные множества не содержат дубликатов.

Плюс, тут рядом дали ссылку на решение со сложением, там и дубликаты правильно отработаны будут.

[soloviewoff]

Я имел в виду, что если поддерживать значение хеша для множества как член класса (и обновлять при добавлении или удалении элемента), то при добавлении элемента важно его обновить, только если элемент был добавлен, а не содержится уже.

[thesz]

Не надо обновлять. Только неприятностей наживете.

Лучше создавать новое.

[antilamer]

Ага, как-то раз такое делал (на java, но с immutable деревьями) и использовал точно такой же хеш.