Просматриваю сейчас курс на www.coursera.org Web Intelligence and Big Data и профессор задаёт следующий вопрос:
The time it takes to search a ‘normal’ hash-table that maps a large number (n) of objects to a small number (m) hash values is ..
- A) O(log n)
- B) independent of n
- C) independent of m
- D) O(log m)
Ответом лектора оказался B)
Правильного ответа тут вообще не присутствует (O(1+loadFactor)).
Однако, в данной выборке ответов более логичным видится ответ C)
А вы что думаете?
Ну тут просили не указать правильную асимптотику, а лишь выбрать верное утверждение.
Действительно, верным тут вроде является только B. Этот самый loadFactor не зависит от принципиально возможного количества ключей n, но зависит от количества значений, засунутых в эту конкретную мапу. Ну и разумеется от m он зависит — меньше значений хеша — больше коллизий.
Странно. Казалось бы loadFactor = n / m, следовательно B == C — или оба утверждения ложны, или оба верны. С другой стороны предложение "hash-table maps n Ёжиков to m Ёлочек" я бы понял так, что у нас есть мапа которая отображает ёжиков в ёлочки (C++ stdext::hash_map<Ёжик, Ёлочка>), и от мощности множества ёлочек ничего не зависит. Если под m подразумевается текущее число бакетов, а не мощность множества Ёлочек, то loadFactor = k / m, где k — количество элементов в мапе т.е. 0 <= k <= n, или вообще забыть про k и считать равным его равным n. Короче ИМХО верный ответ 42. Задавать вопрос надо яснее.
Мне кажется, что утверждение "hash-table that maps a large number (n) of objects to a small number (m) hash values" не совсем корректно, так как хэш-таблица мапит хэш-значения объектов в объекты, а сами объекты мапятся хэш-функцией в хэш-значения.