Какой алгоритм хеширования использовать?

Question

[WhiteNinja]

Добрый вечер!

В БД есть порядка 100 000+ записей (постоянно пополняются).
Есть поле ProductName (название продукта) и поле ProductNameHash (хеш от названия продукта, ProductName).
Поле ProductNameHash используется в запросе вида

SELECT Id FROM Products WHERE ProductNameHash=@Hash

Длина ProductName = 50-2500 символов.

Вопрос о безопаcности не стоит. ProductNameHash может быть общедоступным, это не пароль или какая-либо другая secure-информация.
Важно исключить возможность коллизий (для разных ProductName получить одинаковый ProductNameHash). А также чтобы вычисление хеша производилось достаточно быстро.

Подскажите пожалуйста, какой алгоритм хеширования оптимально использовать в данном случае для поля ProductNameHash - MD5, SHA1, SHA-256 или что-то еще?

Comments

[WhiteNinja]

Dr. Bacon Это выдуманный пример, чтобы описать ситуацию, которая возникла. Хеш нужен, чтобы получить ProductNameHash одинаковый длины (независимо от входной строки), и возможность построить INDEX (сейчас INDEX нет возможности построить так как поле типа TEXT (MySQL)).

[WhiteNinja]

Dr. Bacon Т.е. ProductName - это, например, "Очень-красивое НАЗВАние", а ProductNameHash сейчас это - "ОЧЕНЬКРАСИВОЕНАЗВАНИЕ". Но длина в таком случае будет всегда разной, и в целом очень большой (если ProductName имеет большую длину).

ProductName - Для отображения. ProductNameHash - хеш необходимый для внутренних процессов (поиска, соответствия и.т.д).

[WhiteNinja]

Есть, но к сожалению только на движке MEMORY. А в приложении используется InnoDB, возможности поменять нет. А в InnoDB только BTREE :(

[WhiteNinja]

Dr. Bacon, Спасибо! Но насколько я понял - prefix INDEX создаётся только на N-первых символов от ProductNameHash. Правильно? Если это так, то такое решение не подходит, так как нужно использовать всю длину ProductNameHash, иначе можно получить дубли.

Answer 1

[Rsa97]

Важно исключить возможность коллизий

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

Comments

[WhiteNinja]

Rsa97 Но у SHA-256 такая вероятность довольно маленькая на массивах до 1 000 000 записей? Или до 1 000 000 даже MD5 подойдет?

[Rsa97]

WhiteNinja, А в чём исходная задача? Что должно происходить, например, если кто-то поправил опечатку в названии продукта? Может проще использовать не хэш, а один раз генерируемый GUID?

[WhiteNinja]

Rsa97, Задача не допустить дубли. Данные о продуктах приходят из разных источников (например по средствам API, в aормате json) и например из 1-го источника пришел продукт "ПРОДУКТ номер - один, 30461". Мы записали его в БД с данными ProductName="ПРОДУКТ номер - один, 30461" и ProductNameHash="ПРОДУКТНОМЕРОДИН30461" (это как сейчас). Далее через какой-то промежуток времени из 2-го источниках пришли данные - "Продукт, Номер один: 30461", если построить "простой хеш" (как сейчас), то это будет ProductNameHash="ПРОДУКТНОМЕРОДИН30461" и соответственно новая запись в базе создана не будет, а произойдет "мягкое" обновление уже существующего продукта.

Чтобы не описывать реальную предметную область и детали, я описал приближенную, очень упрощённую. В реальной жизни при поиске дублей конечно участвуют и другие поля кроме ProductNameHash.

Просто я столкнулся с проблемой медленных запросов. Соответственно я решил добавить INDEX-ы, но ProductName может содержать строку длиной 2500+ символов, а в MySQL (движок InnoDB) есть ряд ограничений на индексы для полей типа TEXT. И я подумал, что можно решить эту задачу путем хеширования строки, например "ПРОДУКТНОМЕРОДИН30461", и получения меньшей, одинаковой длины. И уже на это поле я без проблем смогу создать INDEX.

[WhiteNinja]

Dr. Bacon, например классическая реализация MD5 хеширования на C#:

using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create())
{
	byte[] inputBytes = Encoding.UTF8.GetBytes(input);
	byte[] hashBytes = md5.ComputeHash(inputBytes);

	// Convert the byte array to hexadecimal string
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < hashBytes.Length; i++)
	{
		sb.Append(hashBytes[i].ToString("X2"));
	}
	return sb.ToString();
}

MD5 покороче, но я переживаю за возможность схватить одинаковые значения хеша, для разных входных данных :(

[WhiteNinja]

Dr. Bacon, Все верно, тут скорее речь о "жестком" сравнении именно названий. Т.е. текущее решение, где просто удаляются все кроме букв и чисел вполне рабочее и всем устраивает, кроме скорости поиска по БД. Поэтому хотелось заменить хранимый хеш на более компактный, но работающий по такому же принципу.

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

[WhiteNinja]

Dr. Bacon, Для задачи поиска именно похожих в системе используются алгоритмы нечеткого поиска (
Расстояние Левенштейна, коэффициент Танимото, алгоритм Захарова и.т.д) - это все используется в другой части приложения.

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

Сам хеш (например MD5) я буду по очищенным и приведенным данным (ПРОДУКТНОМЕРОДИН30461), по тем, что сейчас являются ProductNameHash. Просто хочется заменить строки на меньшие.

Получается для этого можно попробовать использоваться MD5 без боязни получить одинаковые хешы для разных ProductName на массивах 1 000 000 записей?

[Rsa97]

WhiteNinja, Тогда берите любой хэш, а при совпадении хэша уже сравнивайте строки названия.

Answer 2

[xmoonlight]

Нужно решать проблему поиска, а не создания хеша.
Добавьте признаки к товару и ищите по ним.
Как вариант признака от названия (таблица идентификаторов признаков): "содержит только одну А", "содержит только одну Б",.. и т.д.
И сначала делать выборку по признаку - фильтровать, а в полученных записях - уже искать по полному имени.