Язык С, хэш-таблица.
здравствуйте, делаю лабу университетскую по хэш-таблицам и вот у меня задание: Создать хеш-таблицу со случайными ключами и определить, сколько
элементов находится в каждом стеке. какой ещё стек? я не понимаю что значит стек в этом контексте.
Всё дело - в коллизиях, т.е. нескольких элементах с одним хешем по модулю размерности таблицы.
Вот реализация с вёдрами. Обычно это реализуется через связный список, а стек поминается потому, что вставка идёт в начало (чтобы не бежать по всему списку). При такой реализации можно позволить себе невысокий load factor, например, в районе 0.6 плюс-минус (т.е. на каждые 10 ячеек приходится примерно 6 элементов).
Вот реализация с рехешированием. При коллизии выбирается следующая ячейка по алгоритму. Например, ближайшая следующая. Из таких таблиц геморройно удалять, поэтому они используются только тогда, когда невозможно использовать вёдра, либо если удаление вообще не предполагается. Чтобы снизить количество коллизий при рехешировании, такие таблицы должны быть сильно разрежёнными, например, load factor 0.1 или около того.
видимо, имеется в виду ведро (множество элементов с одинаковыми хешами)
как ты его реализуешь (стек/массив/список/бумажка с карандашными записями) - вопрос твоей реализации, лишь бы по нему можно было итерироваться и искать какой-то элемент
В контексте хеш-таблиц, стек обычно используется для реализации открытой адресации, которая является одним из способов разрешения коллизий.
При использовании открытой адресации элементы, которые должны быть помещены в ячейку, которая уже занята другим элементом, помещаются в другую свободную ячейку в таблице. Если таких свободных ячеек нет в той же строке, то следующая свободная ячейка ищется в другой строке, начиная с некоторой фиксированной точки (обычно это точка, вычисленная с помощью хеш-функции).
Стек в этом случае представляет собой список ячеек, которые были проверены при поиске свободной ячейки. Этот стек может быть использован для определения количества элементов в каждом стеке: если ячейка, которая была использована при поиске свободной ячейки, уже содержит элемент, то этот элемент будет добавлен в соответствующий стек.
Таким образом, в вашей лабораторной работе стек представляет собой список ячеек в таблице, которые были проверены при поиске свободной ячейки. Количество элементов в каждом стеке можно определить, перебирая ячейки в каждом стеке и подсчитывая количество элементов, которые они содержат.