В массиве данных (не БД), если представить в виде таблицы, имеется около 5-7 ключевых колонок комбинация которых уникально определяет запись в массиве. Этот массив нужно референсить из другого подобного и, чтобы не тянуть все 7мь колонок, хочется использовать какой-нибудь уникальный хэш вместо них.

Посоветуйте алгоритм/библиотеку позволяющую быстро сгенерить гарантированно уникальный хэш на основании нескольких строк.
Спасибо.

Здравствуйте, Antei, Вы писали:

A>В массиве данных (не БД), если представить в виде таблицы, имеется около 5-7 ключевых колонок комбинация которых уникально определяет запись в массиве. Этот массив нужно референсить из другого подобного и, чтобы не тянуть все 7мь колонок, хочется использовать какой-нибудь уникальный хэш вместо них.

A>Посоветуйте алгоритм/библиотеку позволяющую быстро сгенерить гарантированно уникальный хэш на основании нескольких строк.
A>Спасибо.

Значение_колонки1+Значение_Колонки2+… Значение_колонкиХ;

Точно даст уникальное значение, если сам набор значений в строке уникален… Правда насчет "быстроты" генерации такого "хэша" сложно что-то предположить заранее

Здравствуйте, Antei, Вы писали:

A>Посоветуйте алгоритм/библиотеку позволяющую быстро сгенерить гарантированно уникальный хэш на основании нескольких строк.
A>Спасибо.

Советую обратиться к определению хэш функции и принципу Дирихле. Определение гласит что хэшфункция может быть использована для вычисления значения фиксированной длины для входной последовательности произвольной длины. А принцип Дирихле:

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

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

Здравствуйте, Antei, Вы писали:
A>В массиве данных (не БД), если представить в виде таблицы, имеется около 5-7 ключевых колонок комбинация которых уникально определяет запись в массиве. Этот массив нужно референсить из другого подобного и, чтобы не тянуть все 7мь колонок, хочется использовать какой-нибудь уникальный хэш вместо них.

A>Посоветуйте алгоритм/библиотеку позволяющую быстро сгенерить гарантированно уникальный хэш на основании нескольких строк.

Guid.NewID(). Но правильно это называется — суррогатный (первичный) ключ.

Здравствуйте, samius, Вы писали:

S>Отсюда напрямую следует что уникальность области значений хэш функции возможна только при размере хэша, превосходящем любую входную последовательность. А это противоречит определению хэш функции.
Судя по определению из вики:

Хеширование или хэширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

не противоречит

Здравствуйте, samius, Вы писали:

S>

S>Если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.

S>Отсюда напрямую следует что уникальность области значений хэш функции возможна только при размере хэша, превосходящем любую входную последовательность. А это противоречит определению хэш функции.

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

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

Здравствуйте, itslave, Вы писали:

I>Здравствуйте, samius, Вы писали:

S>>Отсюда напрямую следует что уникальность области значений хэш функции возможна только при размере хэша, превосходящем любую входную последовательность. А это противоречит определению хэш функции.
I>Судя по определению из вики:
I>

I>Хеширование или хэширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

I>не противоречит
Противоречит. Для любого наперед заданного размера выходной битовой строки найдется массив из входных данных, превосходящий длину выходной строки. Т.е. кролики не влезут в клетки. Наличие коллизий — прямое следствие из определения.

Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, samius, Вы писали:

S>>Отсюда напрямую следует что уникальность области значений хэш функции возможна только при размере хэша, превосходящем любую входную последовательность. А это противоречит определению хэш функции.

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

Pzz>Поэтому программы, которые полагаются не несовпадение хеша в случае несовпадения входных данных, имеют право на существования. Но важно хеш применять хороший, а не абы какой.
Но ТС хотел гарантий уникальности настолько, что выделил болдом слово "гарантированно". Т.е. любое решение, не гарантирующее отсутствие коллизий, ему не подходит.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, Pzz, Вы писали:

Pzz>>Здравствуйте, samius, Вы писали:

Согласен, samius, спасибо за столь ясные аналогие с кроликами
Также вынужден согласиться с Carc: гарантированно уникальным вариантом который можно построить на лету может служить конкатенация, при наличии уникального разделителя, конечно.

Т.к. сконкатенированный ключ может быть большим, думаю, можно построить составной индекс:
колонка 1) какой-то хэш, скажем murmur64
колонка 2) сконкатенированный через делимитеры ключ

Колонка 1) будет малого размера и позволит быстро сузить поиск по индексу
Колонка 2) обеспечит уникальность

Здравствуйте, samius, Вы писали:

Pzz>>Поэтому программы, которые полагаются не несовпадение хеша в случае несовпадения входных данных, имеют право на существования. Но важно хеш применять хороший, а не абы какой.
S>Но ТС хотел гарантий уникальности настолько, что выделил болдом слово "гарантированно". Т.е. любое решение, не гарантирующее отсутствие коллизий, ему не подходит.

Что есть гарантия?

Например, если вероятность коллизии в миллион раз меньше вероятности аппаратного сбоя, это гарантия? А если в миллиард? А если в миллион миллиардов?

Здравствуйте, Pzz, Вы писали:

Pzz>Здравствуйте, samius, Вы писали:

S>>Но ТС хотел гарантий уникальности настолько, что выделил болдом слово "гарантированно". Т.е. любое решение, не гарантирующее отсутствие коллизий, ему не подходит.

Pzz>Что есть гарантия?
Гарантия — это лирика. Это как "совершенно точно" или "зуб даю". Т.е. в применении к совершенно однозначному требованию уникальности значений функции (читаем инъективности, чему есть определение), слово "гарантированно" не ослабляет определение инъективности, а как-бы наоборот, усиливает его (было бы куда).

Pzz>Например, если вероятность коллизии в миллион раз меньше вероятности аппаратного сбоя, это гарантия? А если в миллиард? А если в миллион миллиардов?
Это гарантия неинъективности отображения. Гарантия инъективности — это когда вероятность коллизии = 0, если удобнее оперировать вероятностями.

Конечно, это всего лишь мое понимание гарантий уникальности. Если есть другое, прошу привести его.

Здравствуйте, Pzz, Вы писали:
Pzz>Что есть гарантия?

Pzz>Например, если вероятность коллизии в миллион раз меньше вероятности аппаратного сбоя, это гарантия? А если в миллиард? А если в миллион миллиардов?
Математически говоря, это не гарантия.

Вероятность, миллион миллиардов — это математика для «банков», но не для математики.
А если по сути, то ТС получил ответ ровно на тот вопрос, который задал.

а) «Гарантированно» — я ему ответил. Если нужны коллизии с очень низкой вероятностью, то разговор о сферическом коне в вакууме. Что за значения, размер массива данных? Где-то и CRC32 подойдет (скорость), а где-то и AES будет мало.

б) «Быстро» — что за быстро? Быстро закодить? Чтобы быстро работало? Если про закодить, то на чем? Си? Асм? VB? Bat-файлы?
Если про быстро работало? То «имя, сестра, имя» — насколько быстро? Сколько вычислений в минуту\секунду\миллисекунду?

Здравствуйте, samius, Вы писали:


S>Противоречит. Для любого наперед заданного размера выходной битовой строки найдется массив из входных данных, превосходящий длину выходной строки. Т.е. кролики не влезут в клетки. Наличие коллизий — прямое следствие из определения.
Все таки про кроликов — это не определение. А вот в определении битовая строка не ограничивается и она может быть аналогичной по размеру максимальному из возможных исходных данных(например функция свертки возвращает исходные данные "добитые" нулями) и даже больше. В этом случае уникальность гарантирована, но, безусловно, полезность — под огромным вопросом.

Здравствуйте, itslave, Вы писали:

I>Здравствуйте, samius, Вы писали:


S>>Противоречит. Для любого наперед заданного размера выходной битовой строки найдется массив из входных данных, превосходящий длину выходной строки. Т.е. кролики не влезут в клетки. Наличие коллизий — прямое следствие из определения.
I>Все таки про кроликов — это не определение.
Конечно, нет. Это утверждение, которое можно сформулировать иначе.

I>А вот в определении битовая строка не ограничивается и она может быть аналогичной по размеру максимальному из возможных исходных данных(например функция свертки возвращает исходные данные "добитые" нулями) и даже больше. В этом случае уникальность гарантирована, но, безусловно, полезность — под огромным вопросом.
В определении хэш функции входные данные произвольной длины. Это значит, что нет элемента максимальной длины. Всегда найдется элемент, на единицу длинее. Да, на практике используются хэши избыточной длины. Но гарантии уникальности гарантированно кончаются там, где размер входного множества превышает 2^n — 1, где n — размер битовой строки хэша. Таким образом, даже идеальные хэш функции (perfect hash) не являются хэш функциями по определению.

Здравствуйте, samius, Вы писали:

S>В определении хэш функции входные данные произвольной длины. Это значит, что нет элемента максимальной длины. Всегда найдется элемент, на единицу длинее. Да, на практике используются хэши избыточной длины. Но гарантии уникальности гарантированно кончаются там, где размер входного множества превышает 2^n — 1, где n — размер битовой строки хэша. Таким образом, даже идеальные хэш функции (perfect hash) не являются хэш функциями по определению.
Отлично, согласен. В реальном же мире, всегда есть максимальная длина входных данных. И с этим допущением, гарантированно существующим всегда в этой вселенной, мы можем гарантировать наличие уникального "кеша" для всех видов входных данных.

Здравствуйте, itslave, Вы писали:

I>Здравствуйте, samius, Вы писали:

I>Отлично, согласен. В реальном же мире, всегда есть максимальная длина входных данных. И с этим допущением, гарантированно существующим всегда в этой вселенной, мы можем гарантировать наличие уникального "кеша" для всех видов входных данных.
С этим сложно не согласиться. В мире, где файлы не бывают больше 100Гб, функция id с размером выходной строки 100Гб нас полностью удовлетворит в отношении уникальности хэшей контентов файлов.

Здравствуйте, samius, Вы писали:

S>С этим сложно не согласиться. В мире, где файлы не бывают больше 100Гб, функция id с размером выходной строки 100Гб нас полностью удовлетворит в отношении уникальности хэшей контентов файлов.

Да, я уже несколько раз отмечал, что с практической точки зрения сложно придумать юзкейс, в котором "гарантированно уникальные хеши" помогают решить проблему.
Конкретно же ж случае топик стартера(связь между двумя таблицами с огромным естественным первичным ключом), ему нужен суррогатный уникальный ключ, что я и присоветовал сразу, но почему то получил минус от ТС.

Здравствуйте, itslave, Вы писали:

I>Guid.NewID(). Но правильно это называется — суррогатный (первичный) ключ.

Уж сколько раз твердили миру: генерация гуидов с достаточно высокой частотой рано или поздно даст два одинаковых значения подряд.

SHA-256. Гарантий никто не даст, но на практике совпадений не будет.

Здравствуйте, Mr.Delphist, Вы писали:

I>>Guid.NewID(). Но правильно это называется — суррогатный (первичный) ключ.

MD>Уж сколько раз твердили миру: генерация гуидов с достаточно высокой частотой рано или поздно даст два одинаковых значения подряд.

Это откуда такая информация?