Табличная структура данных: двумерный массив, таблица по ключу и хеш-таблица

Табличная структура данных — это способ организации данных, при котором элемент находят не по одному порядковому номеру, а по адресу из нескольких частей (номер строки и номер столбца) или по ключу (артикул, логин, координата). В программировании под этим словом обычно понимают две разные вещи: двумерный массив, где адрес — пара индексов, и таблицу с доступом по ключу, которую чаще всего реализуют хеш-таблицей. Ниже разберем обе, покажем, как они лежат в памяти, и отдельно — коллизии и сложность хеш-таблицы в среднем и худшем случае. Примеры проверены на Python 3.14 и C (clang) 23.09.2026.

Мини-словарь, чтобы не путать термины:

Линейные, табличные и иерархические структуры

Классическая учебная классификация делит структуры по тому, как задается адрес элемента.

Это упрощение: границы между типами условны. Список — это по сути таблица с одним столбцом, а таблицу в памяти компьютер все равно хранит линейно, как покажем ниже.

Двумерный массив: адрес = строка и столбец

Возьмем прайс-лист из трех товаров и четырех столбцов (товар, цена, количество, сумма). В программе его удобно хранить как двумерный массив 3×4. Память компьютера при этом одномерная, поэтому язык раскладывает строки подряд одну за другой. Такая раскладка называется row-major (по строкам) — она принята в C, C++ и по умолчанию в NumPy. В Fortran, MATLAB и R принят обратный порядок — column-major (по столбцам).

Для row-major адрес элемента считается формулой: смещение = (i * число_столбцов + j) * размер_элемента. Проверим на C:

#include <stdio.h>

int main(void) {
    int t[3][4];               /* 3 строки, 4 столбца */
    char *base = (char *)&t[0][0];
    int i = 2, j = 1;
    long by_hand = (long)((i * 4 + j) * sizeof(int));
    long real = (long)((char *)&t[i][j] - base);
    printf("sizeof(int) = %zu\n", sizeof(int));
    printf("offset t[2][1]: formula %ld, real %ld\n", by_hand, real);
    return 0;
}

Вывод (macOS, arm64; размер int зависит от платформы, но на распространенных 64-битных системах он 4 байта):

sizeof(int) = 4
offset t[2][1]: formula 36, real 36

Смещение, посчитанное по формуле, совпало с реальным. Отсюда главное свойство двумерного массива: доступ к любой ячейке по индексам — O(1), без перебора. Цена — фиксированная форма: вставить строку в середину значит сдвинуть все следующие строки, это O(n).

Та же идея линейной записи таблицы встречается и в файлах. Формат CSV хранит таблицу строкой текста: столбцы разделены запятой (или точкой с запятой), строки — переводом строки.

Ловушка Python: список списков через умножение

В Python нет встроенного двумерного массива, его заменяют списком списков. Частая ошибка — создать его умножением:

grid = [[0] * 3] * 3      # ошибка: три ссылки на ОДИН список
grid[0][0] = 1
print(grid)

grid = [[0] * 3 for _ in range(3)]   # исправление: три разных списка
grid[0][0] = 1
print(grid)

[[1, 0, 0], [1, 0, 0], [1, 0, 0]]
[[1, 0, 0], [0, 0, 0], [0, 0, 0]]

В первом случае внешний список содержит три ссылки на один и тот же внутренний список, поэтому запись в «одну строку» видна во всех. Генератор списка создает три независимые строки. Для численных матриц в реальных задачах обычно берут NumPy: там это настоящий непрерывный массив с row-major раскладкой.

Таблица с доступом по ключу

Двумерный массив хорош, когда адрес — небольшие целые числа. Но часто ключ — строка («Шкаф»), большой номер (артикул 804117) или кортеж. Тогда нужна таблица «ключ -> значение». Реализовать ее можно по-разному, и выбор определяет скорость:

Как выбирать: нужен только поиск по точному ключу — хеш-таблица; нужны диапазоны («все артикулы от 100 до 200») и обход по порядку — дерево или отсортированный массив. В Python dict помнит порядок вставки (гарантировано языком с версии 3.7), но это порядок добавления, а не сортировка.

stock = {"Смартфон": 2, "Шкаф": 1, "Электробритва": 5}
stock["Шкаф"] += 1
print(stock)
print(stock.get("Чайник", 0))

{'Смартфон': 2, 'Шкаф': 2, 'Электробритва': 5}
0

Как устроена хеш-таблица

Хеш-таблица — это массив «корзин» (buckets). Хеш-функция превращает ключ в целое число, остаток от деления на число корзин дает номер корзины. Если два разных ключа попали в одну корзину, это коллизия — она нормальна и неизбежна, важно лишь, как ее обработать.

Прогон руками. Таблица из 4 корзин, для целых ключей хеш — сам ключ:

1. Ключ 12: 12 % 4 = 0 -> корзина 0.
2. Ключ 7: 7 % 4 = 3 -> корзина 3.
3. Ключ 20: 20 % 4 = 0 -> корзина 0, там уже 12 — коллизия. Пара ставится в ту же корзину следом (метод цепочек).
4. Поиск ключа 20: считаем корзину 0 и сравниваем ключи в ней по очереди — два сравнения.

Теперь то же в коде. Минимальная учебная хеш-таблица с цепочками и счетчиком сравнений:

class HashTable:
    """Учебная хеш-таблица с цепочками (без удаления)."""

    def __init__(self, size=4, hash_func=hash):
        self.buckets = [[] for _ in range(size)]
        self.count = 0
        self.hash_func = hash_func
        self.comparisons = 0          # счетчик сравнений ключей

    def _bucket(self, key):
        return self.buckets[self.hash_func(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            self.comparisons += 1
            if pair[0] == key:        # ключ уже есть - обновляем
                pair[1] = value
                return
        bucket.append([key, value])
        self.count += 1
        if self.count / len(self.buckets) > 0.75:   # коэффициент заполнения
            self._resize()

    def get(self, key):
        for k, v in self._bucket(key):
            self.comparisons += 1
            if k == key:
                return v
        raise KeyError(key)

    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(len(self.buckets) * 2)]
        for k, v in old:
            self._bucket(k).append([k, v])


prices = HashTable(hash_func=lambda n: n)   # для целых ключей - сам ключ
for code, price in [(12, 1000), (7, 500), (20, 300)]:
    prices.put(code, price)
print(prices.buckets)
print(prices.get(20))

good = HashTable()
bad = HashTable(hash_func=lambda k: 0)      # все ключи в одну корзину
for n in range(1000):
    good.put(n, n)
    bad.put(n, n)
print("сравнений при вставке 1000 ключей:", good.comparisons, bad.comparisons)

[[[12, 1000], [20, 300]], [], [], [[7, 500]]]
300
сравнений при вставке 1000 ключей: 0 499500

Первая строка вывода повторяет прогон руками: 12 и 20 в корзине 0, 7 — в корзине 3. Метод _resize удваивает число корзин и раскладывает пары заново, когда коэффициент заполнения (число элементов / число корзин) превышает 0,75 — так цепочки остаются короткими.

Последняя строка — главный урок про сложность. У хорошей хеш-функции (здесь hash для подряд идущих целых) коллизий не было вовсе. У плохой, отправляющей все ключи в корзину 0, каждая вставка сравнивает ключ со всеми предыдущими: 0 + 1 + … + 999 = 499 500 сравнений. Таблица выродилась в список.

Два способа разрешать коллизии

В Java 8+ HashMap при длинной цепочке (порог 8 элементов, при емкости таблицы от 64) превращает корзину в дерево, чтобы худший случай в такой корзине был не линейным.

Сложность: средняя и худшая

• Поиск, вставка, удаление — O(1) в среднем при условии, что хеш-функция хорошо распределяет ключи, а коэффициент заполнения ограничен.
• Вставка — O(1) амортизированно: отдельная вставка с перестройкой стоит O(n), но перестройки редки.
• Худший случай — O(n) на операцию: все ключи в одной корзине, как в примере выше.

Худший случай не только теоретический. Если злоумышленник знает хеш-функцию сервера, он может прислать тысячи ключей с одинаковым хешем (например, имен параметров запроса) и загрузить процессор — это атака HashDoS. Защита — рандомизированные хеш-функции с секретным ключом (в Python хеш строк рандомизирован при каждом запуске, по умолчанию с версии 3.3), ограничение числа параметров во входящем запросе и лимиты на размер данных. Рандомизация снижает риск, но не отменяет лимитов на вход.

Каким бывает ключ

Ключ должен давать один и тот же хеш все время, пока лежит в таблице. Поэтому изменяемые объекты ключами не берут. Для табличной адресации по двум координатам в Python подходит кортеж, а список — нет:

cells = {}
cells[(2, 1)] = "Шкаф"          # кортеж неизменяем - годится как ключ
print(cells[(2, 1)])
cells[[2, 1]] = "Шкаф"          # список изменяем - ключом быть не может

Шкаф
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Текст ошибки приведен для Python 3.14; в более старых версиях он короче: TypeError: unhashable type: 'list'. В Java и C# правило то же по смыслу: если переопределили equals, переопределите и hashCode (Equals и GetHashCode), иначе равные ключи окажутся в разных корзинах.

Таблицы вне кода: электронные таблицы и СУБД

В электронных таблицах (Excel, LibreOffice Calc, Google Таблицы) ячейка адресуется так же, как в двумерном массиве: B3 — столбец B, строка 3. Формулы пересчитываются при изменении ячеек, от которых зависят, — поэтому таблица решает проблему обновления связанных данных, которая есть у «бумажной» таблицы.

Таблица в реляционной базе данных — другая абстракция: строки в ней не имеют гарантированного порядка, а быстрый поиск по ключу дает индекс. Чаще всего это B-дерево (поиск O(log n) и диапазоны), в ряде СУБД доступны и хеш-индексы (только точное равенство). То есть внутри СУБД работают те же структуры, что в таблице выше.

Выводы

• Табличная структура адресует элемент несколькими индексами или ключом; в коде это двумерный массив или таблица «ключ -> значение».
• Двумерный массив в C лежит в памяти по строкам, адрес считается формулой, доступ O(1), но вставка строки в середину стоит O(n).
• Таблица по ключу — абстракция; хеш-таблица — самая частая ее реализация, дерево поиска нужно, когда важен порядок и диапазоны.
• Хеш-таблица дает O(1) в среднем и O(n) в худшем случае; средний случай держится на хорошей хеш-функции и ограниченном коэффициенте заполнения.
• Ключ хеш-таблицы должен быть неизменяемым и согласованным по equals/hashCode.

Где применяется / связь с практикой

FAQ

Чем хеш-таблица отличается от хеш-функции?
Хеш-функция превращает ключ в число, хеш-таблица — структура данных, которая использует это число, чтобы выбрать корзину для хранения пары «ключ -> значение».

Почему размер хеш-таблицы часто берут степенью двойки?
Тогда остаток от деления можно считать быстрой побитовой операцией; так делают, например, Java HashMap и Python dict. Цена — нужна хеш-функция, у которой хорошо перемешаны младшие биты.

Можно ли хранить в двумерном массиве строки разной длины?
В C прямоугольный массив требует одинаковой длины строк; для разной длины используют массив указателей (jagged array). В Python список списков допускает разную длину строк изначально.