Выбор структуры данных
Среди 1023 ключей линейный поиск отсутствующего ключа делает 1023 сравнения, двоичный поиск 10, а хеш-таблица с 1023 корзинами в лаборатории делала самое большее 6.
Начни с вопросов, которые будешь задавать
Ни одна структура не лучше всех во всём. Каждая делает одни операции дешёвыми за счёт того, что другие становятся дорогими, поэтому выбирать нужно, перечислив, что программа будет делать чаще всего. Курс MIT 6.006 делит варианты на два интерфейса. Последовательность (sequence) хранит элементы в порядке, который задаёшь ты (первый, второй, третий), и элементы запрашивают по позиции. Множество (set) хранит элементы по ключу, и спрашивают, есть ли ключ, какой наименьший ключ или какой следующий после данного. Множество без вопросов о порядке называется словарём (dictionary).
Несколько частых ситуаций и обычный ответ:
- Читать элементы по позиции, добавлять в конец: динамический массив (массив JavaScript).
- История отмены, парные скобки, поиск в глубину: стек, то есть массив, с которым работают только с конца.
- Задания в порядке поступления, поиск в ширину: очередь с индексом head или кольцевым буфером, а не shift на длинном массиве.
- Искать по имени или id: хеш-таблица, а в JavaScript это Map или Set.
- Держать ключи отсортированными при вставке и удалении, спрашивать следующий ключ: сбалансированное двоичное дерево поиска.
- Много вставок и удалений в месте, на которое уже есть указатель: связный список.
Один и тот же поиск в пяти структурах
Лаборатория ниже хранит одни и те же ключи пятью способами и считает сравнения, нужные, чтобы найти один из них. Ключи: 15, 127 или 1023 случайных целых числа. Неотсортированный массив использует линейный поиск. Отсортированный массив использует двоичный поиск. Сбалансированное дерево построено вставкой сначала средних ключей, поэтому оно как можно ниже. Другое дерево построено из ключей в отсортированном порядке, поэтому оно является цепочкой. В хеш-таблице столько корзин, сколько ключей, и вычисление h(k) считается за 1.
Перетащи, чтобы повернуть. Колёсико или щипок для масштаба.
При 15 ключах разница мала: линейному поиску в среднем нужно 8 сравнений, а двоичному около 3.3. При 1023 ключах это уже не так. Линейный поиск в среднем делает 512 и требует 1023 для отсутствующего ключа, а двоичному поиску и сбалансированному дереву никогда не нужно больше 10. Дерево-цепочка так же плохо, как линейный поиск. Хеш-таблица при любом размере держится в среднем между 2.3 и 2.5, потому что её цепочки остаются короткими, и в этой лаборатории её худший случай для 1023 ключей был 6. Поэтому Map является выбором по умолчанию для поиска, а отсортированные структуры стоят затрат, только когда нужен ещё и порядок.
| По позиции | Получить элемент i | Вставка или удаление в начале |
|---|---|---|
| Динамический массив | 1 | n |
| Связный список | n | 1 |
| Отсортированный массив | 1 | n |
| По ключу | Найти | Вставить | Следующий ключ |
|---|---|---|---|
| Массив или список | n | n | n |
| Отсортированный массив | log n | n | log n |
| Хеш-таблица | 1 в среднем | 1 в среднем | n |
| Сбалансированное ДДП | log n | log n | log n |
Каждая ячейка этих двух таблиц показывает скорость роста стоимости для n элементов, по таблицам из конспектов лекций 2, 4 и 7 MIT. Хеш-таблицы и деревья поиска есть только во второй таблице, потому что они работают по ключу, а не по позиции. В неотсортированном массиве или списке вставка ключа стоит n, потому что сначала нужно проверить, что его там ещё нет. Отсортированный массив ищет быстро, но для нового ключа ему приходится сдвигать значения.
Map или объект?
Программы на JavaScript часто используют обычный объект как словарь и пишут prices["apple"]. MDN перечисляет причины предпочесть Map, когда ключи берутся из данных: у объекта есть прототип, поэтому в нём есть ключи по умолчанию, которые могут совпасть с твоими; Map может использовать в качестве ключа любое значение, а не только строки и символы; его размер является одним свойством, map.size; и обходится он в порядке вставки. Для записей с фиксированным набором именованных полей объекты остаются естественным выбором.
- 1953: Записка Х. П. Луна в IBM предлагает хеширование по корзинам с цепочками.
- Около 1956 г.: IPL Ньюэлла, Шоу и Саймона приносит связные списки.
- 1957: Бауэр и Замельзон подают заявку на патент на метод стека; Fortran выходит с массивами.
- 1962: Адельсон-Вельский и Ландис публикуют АВЛ-дерево, первое сбалансированное дерево поиска.
- 2015: ECMAScript 2015 добавляет в JavaScript Map и Set.
- Сколько сравнений делает линейный поиск отсутствующего ключа среди 1023 ключей?
- Сколько сравнений самое большее делает двоичный поиск среди 1023 отсортированных ключей?
- Линейный поиск по 15 ключам: каково среднее число сравнений по всем 15 ключам?
- ДДП построено из 127 ключей, вставленных по возрастанию: сколько сравнений нужно для наибольшего ключа?
- Текстовому редактору нужна отмена. Какая структура подходит?
- Очередь
- Стек
- Хеш-таблица
- Отсортированный массив
- Сервер печати должен обрабатывать задания в порядке поступления. Какая структура подходит?
- Очередь
- Стек
- ДДП
- Связный список в роли стека
- Нужно много раз в секунду находить запись пользователя по id. Что обычно выбирают в JavaScript?
- Массив с перебором в цикле
- Map с ключом id
- Стек
- Связный список
- Нужно держать ключи отсортированными при вставке и удалении и часто спрашивать следующий больший ключ. Что подходит лучше всего?
- Хеш-таблица
- Сбалансированное ДДП
- Очередь
- Неотсортированный массив
- Как в терминах MIT 6.006 называется множество без операций порядка?
- последовательность
- словарь
- стек
- очередь
- Почему, по словам MDN, обычный объект может быть рискованным словарём для ключей, взятых из данных?
- Объекты не могут хранить строки
- Его прототип приносит ключи по умолчанию, которые могут совпасть с твоими
- Объекты всегда медленнее массивов
- Объекты забывают значения через секунду
- Выбирай по операциям, которые будешь выполнять чаще всего.
- Последовательность: массив, связный список, стек, очередь. Множество: хеш-таблица, ДДП.
- Для 1023 ключей: линейный поиск до 1023 сравнений, двоичный поиск и сбалансированное дерево до 10.
- Map является обычным словарём в JavaScript; если нужен ещё и порядок, используй сбалансированное дерево.
Источники курса (11)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
- lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
- 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
- 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
- Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262)
- 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
- Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
Проверено: 2026-10-18