Вообще, по хоорошему

ну конечно

В среднем будет O(1 + α), где α  - это мат. ожидание, которое считается в зависимости от n.

Для этого, кстати, существует редьюс.

так, и ? зачем ?

Тут наверно и правда тонкости совсем. Из серии что бытрее set(Array.from(a[n])) или n раз set.add(1)

дак под капотом в конструкторе set наверняка add вызывается :D

Нет, не будет. В худшем случае будет зависимость от N.
O(N) не значит, что Вы обязательно будете просматривать все элементы в какой-то структуре данных. Это значит, что время работы зависит от количества элементов внутри стркуктуры данных.
Представьте, что мы выбрали замечательную хэш-функцию: x => x % 4, и решили в нашу хэш-таблицу положить числа от 0 до 16, тогда структура хэш-таблицы будет такая:

[
 0 : [0, 4, 8, 12],
 1 : [1, 5, 9, 13],
 2 : [2, 6, 10, 14],
 3 : [3, 7, 11, 15],
]

Тогда, распределение у нас будет +- равномерным и мы получим, что поиск будет занимать в среднем O(N/4), а в худшем, если нам поступают только числа кратные 4 - O(N).

Ну вдруг там хитрая оптимизация? 8)

Что "зачем"?

И это мы говорим только про бакетные хэш-таблицы

А есть еще реализация с открытой адресацией

Вроде reduce тут не в тему 8)

И там тоже куча стратегий адресаций (двойное хэширование, инкриментальная адресация и тд)

Ну вот по ссылке выше двойное хеширование и используется

Я к тому, что зачем его туда лепить ?

Ну можно редьюсом сделать... но зачем ? Кода будет даже больше

А это тогда что такое https://github.com/dotnet/runtime/blob/master/src/libraries/System.Private.CoreLib/src/System/Collections/Hashtable.cs#L126

Так ты почитай дескрипшн )