F# hash structured data

Microsoft, сэр!

F#, сэр, это не только MS. Да и вообще где ещё спрашивать, если не ЛОРе.

Коллизия, сэр :)

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

Тогда это не хэш, а херня.

мсье, много найдете хешей, гарантирующих уникальность объекта (не являющегося int-ом или еще чем целочисленным)?

google://хеш коллизия

sha256/512

Как найдёшь — обязательно сообщи.

я думал, что hash не гарантирует уникальность пользовательских типов, т.к. реализация GetHashCode() может быть любой, хоть и возвращающей одно и тоже число каждый раз. Но для стандартных типов, GetHashCode() для одного типа во всяком случае, должна работать адекватно, иначе зачем она нужна. Другое дело, как работает GetHashCode для составных объектов - разбивает ли объект на отдельные и складывает или как-то по-другому? Но мне в общем-то похрен, я простой программист, увидел hash, применил.

сюрприиииз! они не гарантируют уникальность хеша.

Но для стандартных типов, GetHashCode() для одного типа во всяком случае, должна работать адекватно

так и работает. Еще раз: хеш не означает уникальности.

иначе зачем она нужна.

для реализации ассоциативных массивов тащемта например.

Функция hash возвращает значения из множества, ограниченного количеством элементов 2^64. Это столько уникальных объектов можно отобразить на уникальные хеши. Теперь, как можно отобразить 2^1000 уникальных объекта на хеши без коллизий? Кто знает способ?

сделать хэш составным (i, hash) и разбить элементы на n групп, i>0 && i <=n?

тем самым увеличив размер хеша, так ничесна!

А у тебя миллионы хешей берутся?

Так идея хеша в том, что мы нечто большое отображаем по быстрому на нечто маленькое, да так, чтобы разные элементы по возможности получали разные значения. Ключевые слова: «нечто маленькое» и «по возможности».

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

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

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

Да, я понял, но как-то не верится, что на таких простых данных возможна была на практике такая коллизия.

эм, нет, по сути у меня берётся максимум 10^3 хэшей, но разница то какая, когда в моём случае хэш (0,2) = хэш(2,0), а такие значения всегда есть в моём случае, т.к. эти пары - индексы матрицы.

А ты не думал просто перегонять их в строки и брать хеши от строк?

типа хеши строк уникальны.

тут вопрос - зачем оные хеши были применены?

А для чего нужно брать хэши индексов матрицы? Хэш нужен, если складываешь значение в хэш-таблицу. В остальных случаях его вычислять скорее всего незачем.

Завтра сделаю что-нибудь с этим, возможно через строки.

хэши нужны были чтобы складывать выборку по матрице в хэш таблицу

А, тьфу. Индексы матрицы.

i*columns + j, где i - номер строки, j - номер столбца. Вот и будет тебе хеш.

Хэш-таблица помимо равенства хэшей проверяет равенство ключей. В чём тогда проблема с коллизиями?

матрица 3 x 3: hash [(1, 1)] = 4; hash [(0, 0); [1, 1]] = 4 ну и ещё варианты такие же есть) у меня хэш не от одной пары индексов а от списка. А насчет строк - хэш от строк разве уникальный?

в качестве ключей используются хэши

Не верю, что в F# нет готовых хэш-таблиц с любыми хэшабельными типами ключей и авторазрешением коллизий.

Не надо так делать. Можно использовать сами пары (i, j), но не хэши.

А насчет строк - хэш от строк разве уникальный?

Коллизии крайне редки. Тебе придётся постараться, чтобы напороться.

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

к примеру как? вся прелесть хэш таблиц в их быстром доступе. К примеру, если использовать множества вместо хэш таблиц то на моих примерах я получу разницу в 30 секунд работы против 3. Это существенно для моей задачи.

То есть коллизии со структуированными значениями, парами к примеру, намного чаще встречаются?

Понятия не имею, как реализован хеш для структурированных элементов (и реализован ли вообще). Но хеши для строк тестируют куча людей в своём коде и если бы коллизии были частыми, то воя было бы много.

еще раз: хеш-таблица не умеет сама принимать в качестве ключей оные пары (оно там вроде как не «два значения через запятую», а отдельный тип tuple)? Где видел, стандартные ассоциативные массивы могут иметь ключами любой тип, для которого реализованы хеш (для хеш-таблиц) и равенство, и сами разгребают коллизии. Зачем сразу изобретать велосипеды?

Коллизии крайне редки. Тебе придётся постараться, чтобы напороться.

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

Хэш-множества дают точно такой же быстрый доступ, как и хэш-таблицы. По сути, это одна и та же структура данных.

Не очень понял, зачем ещё раз повторять, я и так это отлично понимаю)

не дают они такой же быстрый доступ, Оптимизация поиска _наличия_ общего элемента 2х списков

упс, не заметил приставку «хэш-», но тогда тем более не понятно как заменить хэш-таблицы хэш-множествами и избежать проблем описаных ранее?

я и так это отлично понимаю)

к примеру как?

цота непохозе)

как и вкуда добавляется элемент сейчас? Пример кода с указанием типов.

Не надо вычислять хэш-код элемента. Множество это делает самостоятельно и самостоятельно же решает коллизии. Надо просто складывать пары индексов в множество.

вы имеете в виду, что при добавлении в HashSet новый элемент сравнивается с каждым уже имеющемся элементом с помощью Equals, а в случае с HashTable сравнивается только GetHashCode? Если так, то видимо это и есть причина тормознутости HashSet в случаях, когда создаётся много таких объектов.

let ht = HashTable()
let getData keys =
   match ht.Contains(hash keys) with
   | true -> ht.Item(hash keys)
   | false -> 
       let data = 
           keys |> List.collect (fun k -> dataProvider.Get(k))
       ht.Add(hash keys, data)
       data

код схематичный

Нет, не с каждым. HashSet и HashTable работают одинаково. Сравниваются только те ключи, у которых совпал хэш-код.

почему бы не ht.Contains(keys), ht.Item(keys) итд?

ок, а в каких случаях тогда предпочтительна HastTable? И не очень понятно как происходит тогда обращение к элементу? То есть мы добавили элемент A с хэш-кодом 1, потом мы добавили элемент B с таким же хэш-кодом, но функция Equals(A, B) ложна. И под каким тогда ключом лежит B?

так а что меняется? ну будет сама таблица вызвать GetHashCode, а результат тот же

так а что меняется? ну будет сама таблица вызвать GetHashCode, а результат тот же

сейчас HashMap считает хеш от хеша, а будет от объекта :)

Надеяться на уникальность GetHashcode нельзя. Хочешь уникальных хешей, перепиши на sha256

Легко. Я в своё время так накололся на GetHashCode от строк. Две разные строки боладали одним хешем.

Все знакомые мне стандартные языковые реализации хеш-таблиц корректно обрабатывают коллизии - при совпадении хешей ключей идет проверка на равенство самих ключей.

Т.е. вот сейчас что происходит:

1) берется объект, логически являющийся ключом, вычисляется его хеш

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

....

n) берется объект, блабла, вычисляется хеш, и вдруг так получается, что он совпадает с ранее вычисленным для другого объекта ключа - коллизия. Об этом никто не знает и не отлавливает.

n+1) значение этого хеша используется в качестве ключа. В таблицу помещается значение. Таблица видит, что хеш такого ключа (который сам по себе хеш) в ней уже есть, проверяет равенство самого нового ключа и имеющегося, они равны - коллизия произошла на предыдущем этапе вне таблицы - и затирает старое значение новым.

Видим, где косяк? Теперь используем в качестве ключа сам объект:

1) объект фактически используется в качестве ключа, по нему в таблицу помещается некое значение. При помещении значения таблица вычисляет хеш от ключа (который теперь объект), проверяет, что такого хеша у нее не имеется, размещает новое значение.

....

n) берется объект, логически выступающий в качестве ключа

n+1) объект используется в качестве ключа. В таблицу помещается значение. Таблица видит, что хеш такого ключа (который теперь объект) в ней уже есть, проверяет равенство самого нового ключа и имеющегося, они не равны - коллизия. Таблица обрабатывает ее своими механизмами - зачастую это означает, что хэш теперь указывает на некий массив, а не на одну пару «ключ-значение».

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