Ответ
В хэш-таблице позиция для вставки нового элемента определяется в два этапа: вычисление первичного индекса и разрешение коллизий.
1. Вычисление первичного индекса:
- Сначала вычисляется хэш-код ключа с помощью хэш-функции.
- Затем этот хэш отображается на диапазон индексов таблицы, обычно с помощью операции взятия остатка от деления (
%).
2. Разрешение коллизий (если ячейка занята): Существует несколько основных методов:
- Метод цепочек (Separate Chaining): Каждая ячейка содержит связный список (или другой контейнер). Новый элемент добавляется в список соответствующей ячейки.
- Открытая адресация (Open Addressing): Ищется следующая свободная ячейка внутри самой таблицы по определенному алгоритму.
Пример реализации на C++ с линейным пробированием (открытая адресация):
template<typename K, typename V>
class HashTable {
struct Entry {
K key;
V value;
bool occupied = false;
bool deleted = false; // Флаг для ленивого удаления (tombstone)
};
std::vector<Entry> table;
size_t size = 0;
const float loadFactorThreshold = 0.7;
size_t hash(const K& key) const {
return std::hash<K>{}(key);
}
size_t probe(size_t index, size_t attempt) const {
// Линейное пробирование: index = (hash + i) % capacity
return (index + attempt) % table.capacity();
}
public:
bool insert(const K& key, const V& value) {
// Проверка необходимости рехеширования
if (static_cast<float>(size) / table.capacity() > loadFactorThreshold) {
rehash();
}
size_t h = hash(key);
for (size_t i = 0; i < table.capacity(); ++i) {
size_t idx = probe(h, i);
if (!table[idx].occupied || table[idx].deleted) {
// Нашли свободную ячейку или "могилу"
table[idx] = {key, value, true, false};
++size;
return true;
}
if (table[idx].occupied && table[idx].key == key) {
// Ключ уже существует, обновляем значение
table[idx].value = value;
return false;
}
// Коллизия: продолжаем пробирование
}
// Таблица переполнена (должно быть предотвращено рехешированием)
return false;
}
};Критерии выбора метода:
- Цепочки проще реализовать, стабильнее при высокой нагрузке, но требуют дополнительной памяти на указатели.
- Открытая адресация лучше использует кэш процессора, но требует тщательного контроля коэффициента загрузки и сложнее при удалении элементов (нужны "могилки").
- В стандартной библиотеке C++ (
std::unordered_map) обычно используется метод цепочек.
Ответ 18+ 🔞
Давай разберем эту всю механику, как ключ попадает в свою ячейку, а то звучит, будто мы в сортире ищем свободную кабинку. Эх, ебать мои старые костыли, сейчас всё по полочкам.
В общем, чувак, алгоритм простой до безобразия, как два пальца об асфальт. Сначала ты ключ свой в хеш-функцию суёшь — она тебе на выходе какую-то цифру-кашу выдаёт, хеш-код. Потом эту цифру надо впихнуть в размер нашей таблицы. Обычно берут остаток от деления, то есть hash % размер_таблицы. Вот тебе и первичный индекс, куда бы мы в идеальном мире элемент положили.
Но мир не идеален, ёпта. Бывает, что два разных ключа на одну и ту же ячейку претендуют. Это и есть коллизия, пиздец, да? Тут два главных подхода, как из этой ситуации выкрутиться.
Первый — метод цепочек. Представь, что каждая ячейка таблицы — это не одно место, а крючок в гардеробе. На один крючок можно десять пальто повесить. Вот так и здесь: если ячейка занята, новый элемент просто добавляется в связный список, который из этой ячейки растёт. Просто, как три копейки. Памяти, правда, жрёт больше, потому что на каждый элемент ещё указатели хранить надо.
Второй — открытая адресация. Тут уже философия другая. Если твоя кабинка занята, ты идешь искать следующую свободную, прямо по коридору. Самый тупой способ — линейное пробирование: пошёл на ячейку вправо, занято? Пошёл ещё на одну. И так, пока не найдёшь пустую. Кэш процессора использует эффективнее, но если таблица заполнена под завязку, то искать свободную ячейку будет овердохуища времени. И ещё с удалением элементов геморрой — просто так выкинуть нельзя, надо «могилку» (tombstone) оставить, чтобы поиск не сломался.
Вот, смотри, как это на плюсах выглядит с линейным пробированием. Блок кода не трогаю, он святой.
template<typename K, typename V>
class HashTable {
struct Entry {
K key;
V value;
bool occupied = false;
bool deleted = false; // Флаг для ленивого удаления (tombstone)
};
std::vector<Entry> table;
size_t size = 0;
const float loadFactorThreshold = 0.7;
size_t hash(const K& key) const {
return std::hash<K>{}(key);
}
size_t probe(size_t index, size_t attempt) const {
// Линейное пробирование: index = (hash + i) % capacity
return (index + attempt) % table.capacity();
}
public:
bool insert(const K& key, const V& value) {
// Проверка необходимости рехеширования
if (static_cast<float>(size) / table.capacity() > loadFactorThreshold) {
rehash();
}
size_t h = hash(key);
for (size_t i = 0; i < table.capacity(); ++i) {
size_t idx = probe(h, i);
if (!table[idx].occupied || table[idx].deleted) {
// Нашли свободную ячейку или "могилу"
table[idx] = {key, value, true, false};
++size;
return true;
}
if (table[idx].occupied && table[idx].key == key) {
// Ключ уже существует, обновляем значение
table[idx].value = value;
return false;
}
// Коллизия: продолжаем пробирование
}
// Таблица переполнена (должно быть предотвращено рехешированием)
return false;
}
};Так какой же метод выбрать, спросишь ты? Всё зависит от задачи, чувак.
- Цепочки — надёжные, как швейцарские часы. Реализация проще, и даже когда таблица забита, деградация производительности плавная. Но память хавают.
- Открытая адресация — шустрая, особенно на современных процессорах, потому что данные лежат рядышком в памяти. Но тут надо терпения ноль ебать и следить за коэффициентом загрузки, иначе поиск превратится в ад. Да и с удалением морока — эти самые «могилки» могут таблицу захламить.
Кстати, в стандартной библиотеке C++ (std::unordered_map) ребята не стали мудохудочить и используют обычно метод цепочек. Надёжно и предсказуемо. А то знаешь этих теоретиков, начнут оптимизировать — будет вам хиросима и нигерсраки в продакшене.
