#c #hash #hashtable
#c #гашиш #хэш-таблица
Вопрос:
Я создаю хэш-таблицу на C, используя открытое хэширование (отдельную цепочку) для хранения слов. Меня не волнует порядок, в котором я буду хранить слова с одним и тем же хэш-ключом.
В настоящее время у меня есть указатель на структуру (struct dict * d) с моей хэш-таблицей (элемент структуры * arr). Более конкретно, эта таблица представляет собой массив элементов (элемент структуры), содержащий слово (символ * слово) и указатель (элемент структуры * далее).
Мне неясны два аспекта:
1. При объединении слов в цепочку после столкновения (вставка нового элемента) следует ли вставлять элемент в начале или в конце связанного списка?
Я видел, как это делается в обоих направлениях, но последнее кажется более популярным. Однако первый вариант кажется мне более быстрым, так как мне нужно только установить указатель моего первого элемента на мой новый элемент, а его указатель на нуль. Мне не нужно преследовать указатель (т. Е. Перемещаться по связанному списку, пока я не найду нулевой указатель).
2. Должна ли моя хэш-таблица представлять собой массив указателей на элементы (элемент структуры) или просто массив элементов (элемент структуры), как я это сделал?
Другими словами, должен ли самый первый элемент для определенного хэш-ключа быть вставлен в первую ячейку (пустую ячейку), или в этой ячейке уже должен быть указатель, который мы будем указывать на этот новый элемент?
Ответ №1:
Для 1. На самом деле не должно иметь значения, добавляете ли вы или добавляете в список. Если вы сохраняете небольшую нагрузку, цепочки будут короткими, и вы не увидите заметной разницы в производительности доступа. Если вы держите стол маленьким, а нагрузка становится высокой, вам может потребоваться изучить различные стратегии. Тогда шаблон доступа может иметь значение. Например, если вы с большей вероятностью будете искать недавно вставленные значения, вы хотите, чтобы они находились в начале списка, поэтому лучше добавить их заранее. Но с хэш-таблицей лучше по возможности уменьшить нагрузку, и тогда это не должно иметь значения.
Для 2. либо тоже будет работать. Если ваша таблица представляет собой массив указателей, нулевых для пустых цепочек, простая реализация рекурсивного связанного списка будет хорошо работать. Сделайте так, чтобы ваши функции списка принимали список в качестве аргумента и заставляли insert и delete возвращать новый список. Либо аргумент, либо возвращаемое значение может быть равно НУЛЮ. Затем сделайте что-нибудь вроде tbl[bin] = insert(tbl[bin], val) или tbl[bin] = delete(tbl[bin], val) . Если цепочки короткие, вам не нужно слишком беспокоиться о накладных расходах на рекурсию. В любом случае, вам не нужна рекурсия для поиска значения или вставки, если это просто добавление, поэтому удаление выполняется только там, где вы все равно не получаете хвостовую рекурсию. Преимущество, которое вы получаете от наличия массива ссылок, заключается либо в том, что вы получаете фиктивный элемент в начале списка, что упрощает реализацию нерекурсивных списков, избегая особых случаев для пустых списков, либо вы избегаете следования указателю для доступа к первому элементу в цепочке, как только вы просматриваете корзину. Для последнего, однако, вам нужен способ отличить пустую цепочку от цепочки с одним элементом. Вряд ли это того стоит, и если вы хотите избежать прыжков по связанным спискам, может быть лучше использовать открытую адресацию или какую-либо другую стратегию столкновения.