Поиск по словарю или поиск по массиву;Распределение массива против размещения словаря

Question

Может кто-нибудь из вас сказать мне, что является закулисным методом поиска для структуры словаря , Я имею в виду, как это реализовано? По заданному ключу мы находим значение в словаре.

1) Мы знаем, что поиск массива - это операция O (1). Так что насчет словаря?

2) Если я храню пары ключ-значение, где оба являются целыми числами, если существует огромное количество таких данных и места, моя забота будет предпочтительнее? Массив или словарь? Например, я могу выделить массив с фиксированным размером. Но пары ключ-значение могут не занимать весь массив. Его размер может составлять половину массива. Но распределение массива должно быть максимального размера, так как я не знаю, появится ли определенный ключ или нет. Позвольте мне уточнить, пусть у нас есть ключ, пары значений (10,1), (20,2), (30,3). Поэтому, если я использую массив, я должен объявить его размер как [30] [2], хотя он занимает только 3 записи. Таким образом, словарь будет лучше в этом случае. Не то, чтобы 30 могли быть миллионами. То есть другие записи будут занимать память в массиве, верно?

Answer 1

Термин dictionary является очень общим и может относиться к любому виду структуры данных. Также вы не сказали, является ли это упорядоченным словарем или неупорядоченным. Существуют все виды бинарных деревьев поиска, сбалансированных различными способами, n-арные деревья, хеш-таблицы, скиплисты и т. Д.

Что касается массивов, прямые плоские массивы занимают пустое пространство, когда они малонаселены. Тем не менее, вы можете реализовать многоуровневые массивы. Первые несколько уровней являются каталогами, и только конечный уровень имеет небольшие массивы.

Таблицы страниц виртуальной памяти часто реализуются таким образом.

Так что получается, что индекс массива, такой как (hex) [0x123456], может быть разбит с помощью операций маскирования на [0x12] [0x34] [0x56]. Выберите верхний каталог, который представляет собой массив указателей на средние каталоги, в которых есть массивы указателей на маленькие таблицы. (Конечно, в действительности, код должен обходить уровни и следить за отсутствующими каталогами и таблицами, а не напрямую индексировать! В этом весь смысл: не создавать целое дерево.)

Не так давно я реализовал наборы символов Unicode в движке регулярных выражений, используя такие типы структур различной глубины для различных ситуаций.

Конечно, это не имеет ничего общего с вашими обычными new int[foo] C ++ массивами! Но, конечно, может быть скрыт за классом, который выглядит как массив.

Answer 2

Словари обычно реализуются двумя способами: хэш-картой или двоичным деревом.

1: Если словарь является двоичным деревом, то время поиска является двоичным поиском и, следовательно, O (log n).

Если словарь является хэш-картой, то время поиска равно O (1). (Возможно увеличение до O (m) для ключей с таким же хешем)

2: Вы правы, словарь будет лучше использовать пространство в этом случае разреженного набора данных. Дополнительные затраты времени на поиск по словарю будут относительно низкими.

Поиск по словарю может быть улучшен с помощью чего-то вроде фильтра Блума (если средний случай - это объект, которого нет в хэш-карте).