Лучшие устройства хеш таблиц 2

[krlz]

Сегодня был произведен небольшой эксперимент. Человеку, который должен был бы придти на собеседование через общих знакомых было сказано, что нужно повторить хеш таблицы. Как и ожидалось, никакой роли это не сыграло, ведь люди знают что хеш таблицы часто спрашивают на собеседованиях, и поэтому готовятся. В результате, у хеш таблицы было время работы

Comments

[ext_8865]

Нуу определение O(f) или предела оно не так уж нужно в повседневной жизни, я второе тоже например забыл, а первое помню исключительно с целью повые^W для общего развития.

А что не так с O(n) у хэш таблицы?

[skavish]

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

[mehas]

А еще существуют хеш-таблицы с гарантированно константным get. Вроде Cuckoo и Hopscotch Hash. Вставка - амортизированно O(1).

[ext_8865]

Ето то понятно, но какбэ когда говорят "алгоритм X работает за O(f)", без уточнений (amortized там или че-то еще), обычно подразумевается как раз самый плохой случай.

[skavish]

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

[ext_8865]

Ну как же не бывает, если таблица с ресайзом, то каждый раз при ресайзе, если без, то так вообще при каждой вставке после того как туда достаточно много элементов напихали -- но с маленьким множителем. Типа, время вставки будет t = С + n / 100500, что тем не менее есть O(n).

Т.е. на собеседовании ответ O(n) по-моему вполне ок, если человек понимает что имеет ввиду, да и если он O(1) ответил, лучше это уточнить.

[krlz]

В таблице с ресайзом среднее время доступа O(1).

[ext_8865]

так я всё про worst case

[mehas]

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

[109]

количество операций при ресайзе O(N), частота ресайза ~1/N, так что amortized всё равно O(1) будет.

[frotmnenogi]

Нефик - ищо как бывает! Во FreeBSD libalias (который для NAT) дает шанс увидеть воочию сей факт. Там есть всё, чего вы лично может нигде и не мечтали увидеть всё вместе:
- таблица неправильных, но статичных (непереконфигурируемых) размеров;
- плохая хеш функция с удачным выбраным профилем для получения максимального числа коллизий;
- single-linked list для удаления устаревших записей.

[krlz]

Вообще, автор сказал конкретно такую фразу: время работы хорошее: O(n).

[squadette]

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

помогает!