Рекомендация для произвольного доступа к большому количеству объектов (например, хеш-таблица)

Question

Я обрабатываю некоторые сгенерированные файлы данных (сотни мегабайт), которые содержат несколько G объектов. Мне нужно произвольный доступ к этим объектам. Я полагаю, возможная реализация может быть большой HashTable. Моя программа написана на Java, и кажется, что java.util.HashMap не может справиться с этим (как-то очень медленно). Кто-нибудь может порекомендовать решение для случайного доступа к этим объектам?

Answer 1

Если HashMap очень медленный, то две наиболее вероятные причины:

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

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

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

---

Примечание: если «несколько объектов G» означает несколько миллиардов объектов, у вас возникнут проблемы с хранением содержимого файлов в памяти ... если вы не запустите это приложение на компьютерес сотнями гигабайт оперативной памяти.Я советую вам сделать некоторые расчеты «за пределами конверта», чтобы понять, возможно ли то, что вы пытаетесь сделать.

Answer 2

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

В худшем случае, если вы возвращаете одинаковый хэш для всех объектов, HashMap по сути становится связанным списком.Вот хорошее место для написания хеш-функций: http://www.javamex.com/tutorials/collections/hash_function_guidelines.shtml

Answer 3

Несколько сотен МБ не могут содержать несколько миллиардов объектов, если каждый объект не является битом (который на самом деле не является объектом ИМХО).

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

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