Почему в js метод indexOf работает за О(n)?

Question

[T4-100]

Как я понимаю массивы в js хранятся как хэш-таблицы. У хэш-табицы сложность поиска в среднем O(1) (https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%... Тогда почему же indexOf реализован методом перебора? Где можно подробнее прочитать про то как храняться массивы и работает память?

Comments

[Lynn «Кофеман»]

Массивы и хеши это совершенно разные вещи.

[Lynn «Кофеман»]

Вы путаете поиск по значению (indexOf) и поиск по ключу (hash[key]).

Хеши для того и придуманы, что бы быстро отдавать значение по ключу. Но и у массива поиск по ключу тоже O(1) (array[10] — работает быстро).

Answer 1

[Владимир Проскурин]

Так indexOf не ищет по индексу значение, он ищет индекс по значению. O(1) это как раз обращение к массиву по индексу arr[0]

Comments

[T4-100]

Тогда странно обращение называть поиском. Получается, что в худшем случае, чтобы обратиться к элементу в хэш-таблице может потребоваться O(n). И чтоб вставить или удалить элемент в хэш-таблице также потребуется O(n) (в худшем случае).

Из этого возникает вопрос тогда, чем хэш-таблица лучше массива? В массиве же мы стабильно получали бы O(1) при обращении к элементу.

[SagePtr]

Иса, в массиве индексы - положительные целые числа от 0 до N-1. В то время, как в хэш-таблице индексы могут быть любыми, и не обязательно вообще числами.

[T4-100]

SagePtr, это я понимаю, но я имел в виду в плане производительности и тд. Возможность иметь индексы нечисла, слабое преимущество. Я понимаю, что раз придумали хэш-таблицы, значит смысл в них есть)) Просто хотелось понять все аспекты.

[SagePtr]

Иса, с чего это вдруг "слабое преимущество"? Если вам нужно хранить не список однотипных безымянных элементов, то как раз в качестве индексов очень часто используют не порядковые номера, а что-нибудь более осмысленное.

Что удобнее, лучше и понятнее?

person[0] = "Вася";
person[1] = "Пупкин";
person[2] = 24;

Или так?

person.firstname = "Вася";
person.lastname = "Пупкин";
person.age = 24;

[Bhudh]

SagePtr, в JavaScript в любом случае индекс — строка, употребление чисел это лишь синтаксический сахар.

Answer 2

[Lynn «Кофеман»]

Никаким другим способом кроме прямого перебора нельзя ответить на вопрос «в каком ящике лежит foo?» кроме как открывать все ящики по очереди.

Comments

[SagePtr]

Разве что хранить обратную хэш-таблицу, где индексами являются значения элементов, а значениями - их индексы. Но это уже извращение, в некоторых задачах может применяться, где нужен быстрый поиск по огромным объёмам информации, но в большинстве - эти несколько милисекунд не стоят затрат на разработку, отладку и сопровождение этого костыля)