Обоснование выбора типа хэш-ключа - PullRequest
Новая
       30

Обоснование выбора типа хэш-ключа

1 голос
/ 17 апреля 2010

Ребята, у меня есть структура данных, которая имеет 25 различных ключей (целое число) и значение. У меня есть список этих объектов (скажем, 50000), и я намерен использовать хеш-таблицу для их хранения / извлечения. Я планирую использовать один из этих подходов.

  1. Создайте целочисленный хеш из этих 25 целочисленных ключей и сохраните его в хеш-таблице. (Да! У меня есть некоторые средства для обработки столкновений)

  2. Создайте конкатенацию строк для отдельных ключей и используйте ее в качестве хэш-ключа для хэш-таблицы. Например, если значения ключа 1,2,4,6,7, тогда ключ хеширования будет «12467».

Если предположить, что у меня есть в общей сложности 50000 записей, каждая с 25 различными ключами и значением, то будет ли мой второй подход излишним, когда речь идет о стоимости сравнения строк, которое необходимо сделать, чтобы извлечь и вставить запись? 1013 *

Еще немного информации!

  1. Каждый сегмент в хеш-таблице представляет собой сбалансированное двоичное дерево.
  2. Я использую метод hash_combine библиотеки boost для создания хеша из 25 ключей.

1 Ответ

1 голос
/ 17 апреля 2010

Абсолютно используйте первый метод, потому что, если вы используете второй, вам потребуется хеш-таблица, в которой доступно 1x10^(25m), where x is the maximum length of a key слотов.

Например, если максимальное число ключей может быть 9999, m будет равно 4, и вам потребуется 1x10 ^ 100 слотов в вашей таблице.

Пояснение:

Идея, лежащая в основе хеш-таблицы, заключается в том, что вы можете получить произвольный доступ к любому элементу с эффективностью O (1) (за исключением коллизий), поскольку хеш любого элемента влияет на его положение в хеш-таблице . Так, например, если я хэширую Object X и возвращаем хеш-код 24 (или какой-то хеш-код строки, который преобразуется в число, которое оказывается равным 24), я просто перехожу к слоту 24 моей таблицы (часто реализуемому как массив), и может получить Объект X.

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

И помните, с первым - поскольку вы используете бинарное дерево, коллизии действительно не будут иметь большого значения. В худшем случае это будет эффективность извлечения / вставки O (log (n)), которая на самом деле не так уж и плоха.

...