Почему поиск таблиц так дешев?

Некоторое время назад я узнал немного о большой O-нотации и эффективности различных алгоритмов.

Например, петлевание через каждый элемент в массиве для того, чтобы что-то с ним сделать

foreach(item in array)
    doSomethingWith(item)

является алгоритмом O(n), так как количество циклов, которое выполняет программа, прямо пропорционально размеру массива.

Меня, однако, поразило то, что поиск таблицы - это O(1). То есть поиск ключа в хэш-таблице или словаре

value = hashTable[key]

занимает одинаковое количество циклов независимо от того, есть ли в таблице один ключ, десять ключей, сто ключей или гигабраджиллион ключей.

Это действительно круто, и я очень рад, что это правда, но это не интуитивно для меня, и я не понимаю почему это правда.

Я могу понять первый алгоритм O(n), потому что я могу сравнить его с реальным примером: если у меня есть листы бумаги, которые я хочу штамповать, я могу просмотреть каждую бумагу один за другим и штамповать каждую. Для меня имеет смысл, что если у меня 2000 листов бумаги, то для того, чтобы штамповать по этому методу, потребуется в два раза больше времени, чем если бы у меня было 1000 листов бумаги.

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

Это не процесс O(1): обычно мне потребуется больше времени, чтобы найти слова в тысячестраничном словаре, чем в двухстраничном. Я с трудом представляю себе процесс, который занимает столько же времени вне зависимости от размера словаря.

tl;dr: Можете ли Вы объяснить мне, как можно выполнить поиск таблицы со сложностью O(1)?

(Если Вы покажете мне, как повторить удивительный алгоритм поиска O(1), я определенно получу большой толстый словарь, чтобы я мог показать всем своим друзьям мои навыки поиска ниндзя-словаря)

EDIT: Большинство ответов, кажется, зависит от этого предположения:

У вас есть возможность получить доступ к любой странице словаря при постоянном номере страницы

Если это правда, то мне легко это увидеть. Но я не знаю, почему это лежащее в основе предположение верно: я бы использовал тот же самый процесс для поиска страницы по номеру, что и по слову.

То же самое с адресами памяти, какой алгоритм используется для загрузки адреса памяти? Почему так дешево найти фрагмент памяти по адресу? Другими словами, почему доступ к памяти O(1)?