Почему скорость поиска в хеш таблице и доступ к значению в массиве - константа?
Как происходит сопоставление вычисленного hash и конкретной ячейки?
Ситуация с коллизиями понятна, но тут не об этом.
Даже если бы у нас значения были отсортированы, то это был бы логарифм.
Аналогично как происходит доступ к массиву по индексу за константу?
Ответы (1 шт):
В дополнение к ответу выше, доступ к элементу массива по индексу это по сути указание конкретной ячейки памяти. Операция [] представляет собой разыменование указателя, то есть получение значения по этому указателю. Когда мы объявляем массив, мы получаем ссылку (указатель) на его местонахождение в памяти (не вдаваясь в детали реализации, условно ячейка нулевого элемента). Когда мы обращаемся к n-ому элементу, мы просто добавляем n*s байт к ячейке, на которую указывает ссылка, где s - это размерность типа массива в байтах.