Должны ли хеш-функции быстрого хешируемого протокола возвращать уникальные значения?

Я работаю над учебным пособием по быстрому Tetris для iOS *, и оно завершено и работает. Но меня озадачивает один конкретный аспект — протокол Hashable. Функция:

class Block: Hashable, Printable {
    [...]    
    var hashValue: Int { return self.column ^ self.row }

Строки идут 0..9, а столбцы 0..20. В примечаниях об этой функции говорится: «Мы возвращаем исключающее ИЛИ наших свойств строки и столбца, чтобы сгенерировать уникальное целое число для каждого блока». Но я понимаю, что 0 ^ 1 будет таким же, как 1 ^ 0 и т. д. Я хотел бы знать, является ли это проблемой, если хэш-функция не уникальна, как эта, или коллизии обычно в порядке? Как я уже сказал, приложение работает нормально...

*https://www.bloc.io/tutorials/swiftris-build-your-first-ios-game-with-swift#!/chapters/681


swift protocols hashable unique collision
person Duncan Rowland    schedule 14.01.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Столкновения не "в целом нормально". Основное предположение состоит в том, что хеш-значение x является хэш-значением y тогда и только тогда, когда x == y. Если вы считаете, что столбец 2, строка 1 такая же, как столбец 1, строка 2, тогда все в порядке. Но я не думаю, что вы делаете! Может показаться, что приложение работает, но, по-видимому, вы пока не сделали ничего, что требовало бы хешируемости.

person matt    schedule 14.01.2015
comment
Вот что я думал. Я думаю, что, возможно, код работает, потому что функции, которым требуется хеш, просто воздействуют на одну строку или столбец за раз. Спасибо за помощь. -Д - person Duncan Rowland; 15.01.2015
comment
Вопрос в том, что произойдет, если у вас есть, скажем, словарь, ключи которого являются блоками. Они не будут работать правильно, потому что хеш-значение используется для поиска ключа, и оно не будет уникальным. - person matt; 15.01.2015
comment
Словарные ключи МОГУТ иметь коллизии, и фактическая эквивалентность проверяется (==) перед возвратом значения. На самом деле, вы можете просто вернуть 0, и Dictionary будет работать нормально. Не гарантируется, что это подойдет для всего кода, использующего hashValue, но hashValue не требуется для гарантии уникальности. Например, вы можете хэшировать строку на основе первой буквы. hashValue не заменяет ==, поэтому Hashable требует Equatable - person Christopher Swasey; 04.04.2015
comment
-1. Коллизии хэшей никогда не должны вызывать ошибок, поскольку хеш-функции (как правило) не гарантируют идеального хеширования. Единственная гарантия, которую дает хэш-функция h, заключается в том, что h(x) != h(y) подразумевает, что x != y. - person Tim Vermeulen; 03.07.2016
comment
Совершенно неправильный ответ. - person Tamás Zahola; 13.05.2021
comment
@matt Не могли бы вы подтвердить, требует ли Swift идеальной хеш-функции? Я предполагаю, что «основное предположение» немного расплывчато: это «предположение» существует в Java для поиска по словарю O(1) , но не требует идеального хеш-кода. - person Maarten; 07.06.2021

arrow_upward
1
arrow_downward

Приложение работает, потому что оно также реализует протокол Equatable:

func ==(lhs: Block, rhs: Block) -> Bool {
    return lhs.column == rhs.column && lhs.row == rhs.row && lhs.color.rawValue == rhs.color.rawValue
}
person Hugo F    schedule 03.07.2016