Рубрики

Таблица прямых адресов

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

Мы можем понять концепцию, используя следующий пример. Мы создаем массив размером, равным максимальному значению плюс один (при условии индекса на основе 0), а затем используем значения в качестве индексов. Например, на следующей диаграмме ключ 21 используется непосредственно в качестве индекса.

Преимущества:

  1. Поиск за время O (1). В таблицах прямого адреса используются массивы, которые представляют собой структуру данных с произвольным доступом, поэтому ключевые значения (которые также являются индексом массива) можно легко использовать для поиска записей за время O (1).
  2. Вставка в O (1) времени: мы можем легко вставить элемент в массив в O (1) времени. То же самое следует и в таблице прямых адресов.
  3. Удаление за O (1) Время: удаление элемента занимает за время O (1) в массиве. Точно так же, чтобы удалить элемент в таблице прямых адресов, нам понадобится O (1) раз.

Ограничения:

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

Хеширование может преодолеть эти ограничения таблиц прямых адресов.

Как обрабатывать столкновения?
Столкновения могут быть обработаны как хеширование. Мы можем использовать цепочку или открытую адресацию для обработки коллизий. Единственное отличие от хеширования здесь в том, что мы не используем хеш-функцию для поиска индекса. Мы скорее напрямую используем значения в качестве индексов.

Рекомендуемые посты:

Таблица прямых адресов

0.00 (0%) 0 votes