C # Dictionary Управление памятью

Question

У меня есть Dictionary<string,int>, который может содержать более 10 миллионов уникальных ключей. Я пытаюсь уменьшить объем памяти, который требуется для этого, сохраняя при этом функциональность словаря.

У меня была идея хранить хеш строки как long, вместо этого это уменьшает использование памяти приложения до приемлемого уровня (от ~ 1,5 гига до ~ 0,5 гигабайта), но я не очень хорошо себя чувствую метод для этого.

long longKey=
BitConverter.ToInt64(cryptoTransformSHA1.ComputeHash(enc.GetBytes(strKey)), 0);

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

Существуют ли другие способы уменьшить объем памяти в Словаре, или метод, описанный выше, не так ужасен, как мне кажется?

[править] Чтобы уточнить, мне нужно сохранить возможность поиска значения, содержащегося в словаре, используя строку. Сохранение фактической строки в словаре занимает много памяти. Вместо этого я хотел бы использовать Dictionary<long,int>, где long - результат хеширования в строке.

Answer 1

Итак, я недавно сделал нечто подобное и по определенному ряду причин, которые являются довольно уникальными для моего приложения, не использовал базу данных. На самом деле я пытался прекратить использование базы данных. Я обнаружил, что GetHashCode значительно улучшен в 3.5. Одно важное замечание: НИКОГДА НЕ ХРАНИТЕ НАСТОЯЩИМ РЕЗУЛЬТАТЫ GetHashCode. НИКОГДА. Они не гарантируют согласованность между версиями фреймворка.

Так что вам действительно нужно провести анализ ваших данных, поскольку различные хеш-функции могут работать лучше или хуже на ваших данных. Вы также должны учитывать скорость. Как правило, в криптографических хэш-функциях не должно быть много коллизий, даже если количество хеш-кодов исчисляется миллиардами. Для вещей, которые мне нужны, я обычно использую SHA1 Managed. В целом CryptoAPI имеет ужасную производительность, даже если основные функции хеша работают хорошо.

Для 64-битного хэша я в настоящее время использую Lookup3 и FNV1, которые оба являются 32-битными хэшами, вместе. Для того, чтобы произошло столкновение, оба должны были бы столкнуться, что математически маловероятно, и я не видел, чтобы происходило более 100 миллионов хэшей. Вы можете найти код для обоих общедоступных в Интернете.

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

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

Answer 2

С 10 миллионами нечетных записей вы рассматривали возможность использования базы данных с некластеризованным индексом? У баз данных гораздо больше хитростей для такого рода вещей.

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

Использование строк может занять место, но это надежно ... если вы используете x64, это не должно быть слишком большим (хотя оно определенно считается "большим" ;-p)

Answer 3

Кстати, криптографические хеш-функции / хеш-функции исключительно плохи для словарей. Они большие и медленные. Решая одну проблему (размер), вы только ввели другую, более серьезную проблему: функция больше не будет равномерно распределять входные данные, тем самым уничтожая одно наиболее важное свойство хорошего хеша для приближения к адресации без столкновений (как Вы, кажется, заметили себя).

/ EDIT: как заметил Эндрю, GetHashCode - это решение этой проблемы, поскольку оно предназначено для использования. И как в настоящем словаре, вам придется обходить столкновения. Одна из лучших схем для этого - двойное хеширование . К сожалению, единственный надежный способ на 100% состоит в том, чтобы фактически сохранить исходные значения. Иначе, вы бы создали бесконечное сжатие, которое, как мы знаем, не может существовать.

Answer 4

Почему бы вам просто не использовать GetHashCode(), чтобы получить хеш строки?

Answer 5

Просто возьми SQLite. Вы вряд ли победите, и даже если вы это сделаете, это, вероятно, не будет стоить времени / усилий / сложности.

SQLite.

Answer 6

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

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