Как получить каждый элемент в постоянное время?

Question

Мы получили n элементов и n ящиков, чтобы хранить их. Каждый элемент имеет идентификационный номер из 10 цифр. Как мы можем хранить эти элементы, чтобы иметь доступ к каждому элементу в постоянное время?

Я думал хранить их в порядке возрастания (id-номер) или наоборот. Но это вызвало бы время работы n в худшем случае. Как бы вы их сохранили?

Answer 1

Используйте идеальную хэш-функцию.

Доступ к элементам в постоянное время. O(1) в худшем случае

Вот ссылка на Википедию: https://en.wikipedia.org/wiki/Perfect_hash_function