Как создать хеш-таблицу - PullRequest
Новая
       49

Как создать хеш-таблицу

9 голосов
/ 21 ноября 2011

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

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

На основное блюдо:

Насколько я понимаю, хеш-таблица - это массив списков (или схожей структуры данных), который, как ожидается, оптимально будет иметь как можно меньше коллизий, чтобы сохранить сложность O (1). Ниже мой текущий процесс:

Итак, мой первый шаг - создать массив указателей: 

Elem ** table;
table = new Elem*[size];//size is the desired size of the array

Мой второй шаг - создать хеш-функцию (очень простую). 

int hashed = 0;
hashed = ( atoi( name.c_str() ) + id ) % size;
//name is a std string, and id is a large integer. Size is the size of the array.

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

Вот некоторый псевдокод: 

while( table[hashedValue] != empty )
    hashedValue++

else
    put in the list at that index.

Это относительно не элегантно, но я все еще на стадии "что это". Потерпи меня.

Есть что-нибудь еще? Я что-то пропустил или сделал что-то неправильно?

Спасибо

Ответы [ 3 ]

4 голосов
/ 21 ноября 2011

Дескриптор не находит пустых слотов и изменяет размеры таблицы.

1 голос
/ 21 ноября 2011

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

0 голосов
/ 21 ноября 2011

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

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

...