Две хеш-таблицы, хеш-таблица с двойным ключом или другое решение?

Question

Еще раз, говоря о моем предстоящем университетском проекте ... У меня был сегодня урок, на котором мы могли бы кое-что спросить о проекте, но я все еще не определился с лучшим способом сделать это.

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

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

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

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

Ребята, вы предлагаете какую-нибудь другую альтернативу?

Answer 1

Я бы пошел с двумя хеш-таблицами. Думайте об этом как о двух индексах в базе данных. База данных - ваши пользователи, и вы предоставляете два индекса: один индекс ssn и один индекс имени.

Answer 2

1. Две хеш-таблицы, как вы сказали. Преимущество состоит в том, что поиск будет очень быстрым для СЛУЧАЙНЫХ данных или даже реальных данных. Недостаток в том, что вы не знаете, что ваши профессора бросят на это (или вы?), И они могут вызвать наихудший случай.

2. Сбалансированный поиск деревьев. Я рекомендую трепы: http://en.wikipedia.org/wiki/Treap - они, на мой взгляд, самые простые в реализации.

3. Сортировка пользователей и бинарный поиск. Также O (log N) для каждого поиска, и даже легче реализовать, чем трепет.

4. Комбинация хэшей + отсортированные пользователи / деревья поиска, если вы можете себе позволить память. Это сделает O (1) лучшим случаем и O (log N) худшим случаем. Если H [i] = список объектов, которые хэшированы в i, сохраните счетчик для каждого i, который сообщает вам, сколько объектов в этом списке. Если это число слишком велико, используйте вместо этого отсортированный список пользователей / дерево поиска.

Answer 3

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

Если вы хотите, чтобы и поиск по SSN, и поиск по имени были действительно быстрыми, то вам нужны две хеш-таблицы. Вы должны помнить, чтобы добавить к ним обоим или удалить из них обоих.

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

Answer 4

Я думаю, что два Hashtables в порядке. Также рассмотрим бинарные деревья поиска, они могут быть более компактными, но O (log n) поиска и сложнее в реализации.

«Хеш-стол с двумя ключами» никогда не слышал об этом ...

Answer 5

Как насчет объединения двух ключей и использования в качестве ключа?

В примере у меня были x, y, z.

Concatanete x и y, используя строку или символ в качестве разделителя. Это простой способ сделать это.

В этом посте я вижу, что может быть интереснее для этого решения: Многомерные ассоциативные массивы в javascript