Какова амортизированная сложность доступа к элементу хеш-таблицы?

Амортизированная сложность доступа к элементу хеш-таблицы

Амортизированная сложность доступа к элементу хеш-таблицы составляет O(1) в среднем. Это означает, что при нормальных условиях и хорошей хеш-функции время доступа не зависит от количества элементов в таблице. Однако в худшем случае, когда все элементы попадают в одну корзину (bucket), сложность может возрасти до O(n).

Как это работает

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

Пример кода

class HashTable {
  constructor() {
    this.table = new Array(100);
    this.size = 0;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.table.length;
    }
    return hash;
  }

  set(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    this.table[index].push([key, value]);
    this.size++;
    // Амортизированное расширение при необходимости
    if (this.size > this.table.length * 0.75) {
      this.resize();
    }
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    if (bucket) {
      for (const [k, v] of bucket) {
        if (k === key) return v;
      }
    }
    return undefined;
  }

  resize() {
    // Дорогая операция, но редкая
    const oldTable = this.table;
    this.table = new Array(oldTable.length * 2);
    this.size = 0;
    for (const bucket of oldTable) {
      if (bucket) {
        for (const [k, v] of bucket) {
          this.set(k, v);
        }
      }
    }
  }
}

Вывод

Амортизированная сложность O(1) делает хеш-таблицы идеальными для сценариев, где требуется быстрый доступ по ключу, например, в кэшах, базах данных и реализации ассоциативных массивов. Однако важно учитывать качество хеш-функции и коэффициент загрузки для поддержания производительности.