Элементы массива - связные списки. Элементы с одинаковым хэшем выстраиваются в цепочку.
direct-address table - так называется массив наших связных списков.
Исследуем все элементы пока не найдем совпадение или не закончится список.
Если ищем по key - $O(k)$, где k - длина списка, в котором ищем
Если нам дали ссылку на Node - $O(1)$
Исследуем все элементы пока не найдем совпадения, если не нашли – вставляем в начало.
Если есть возможность вставить то, что уже есть - $O(k)$, где k - длина списка, в котором ищем
Если вставляемый элемент точно не присутствует в хэш-таблице - $O(1)$
Исследуем все элементы пока не найдем совпадение или не закончится список и удаляем найденный, если нашли.
Если удаляем по key - $O(k)$, где k - длина списка, в котором ищем
Если удаляем по указателю на Node И у нас doubly linked lists - $O(1)$
Introduction to Algorithms (Fourth Edition) - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022)
Основная идея состоит в том, чтобы выбрать M достаточно большим, чтобы списки были достаточно короткими для обеспечения эффективного поиска с помощью двухэтапного процесса: хэширование для поиска списка, который может содержать ключ, затем последовательный поиск по этому списку для ключа.