Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица
Страница 5. Ограничения порядкового индексирования

Ограничения порядкового индексирования

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

Однако лишь в немногих ситуациях нам известна позиция элемента, интересующего нас. Например, рассмотрим базу данных сотрудников предприятия. Каждый сотрудник может быть идентифицирован уникальным образом с помощью номера социального страхования (в США), который имеет вид DDD-DD-DDDD, где D - это цифра (0-9). Если бы у нас был неупорядоченный массив сотрудников, то, скажем, для поиска сотудника с номером 111-22-3333 нам бы потенциально потребовалось произвести поиск среди всех элементов массива сотрудников - операция, сложность которой равна O(n). Лучше было бы предварительно отсортировать сотрудников по их номеру социального страхования, уменьшив тем самым асимптотическое время поиска до O(log n).

В идеале, нам хотелось бы находить записи о каждом конкретном сотруднике за время O(1). Одним из способов реализовать это будет создать огромный массив, в котором номер каждого элемента был бы номером социального страхования. То есть, наш массив начинался бы с элемента номер 000-00-0000 и заканчивался бы элементом 999-99-9999, как показано на рисунке внизу:

Рисунок 7. Массив, содержащий все 9-значные числа

Как показано на рисунке, каждая запись о сотруднике содержит некоторую информацию: имя (Name), номер телефона (Phone), зарплату(Salary), и так далее. Каждая запись индексируется посредством номера социального страхования. По такой схеме информация о любом работнике может быть получена из массива за постоянное время - О(1). Недостаток этого подхода ужасающая растрата памяти - всего существует 109 (миллиард) различных номеров социального страхования. Для компании, в которой работает 1000 сотрудников, лишь 0,0001% массива будет фактически использовано. (На деле, чтобы почти полностью заполнить этот массив, вашей компании придется нанять ни много, ни мало - одну шестую часть населения Земли)