Comments 11
Но вы даже не написали, что же из себя представляет хэш функция и какова её сложность...
Там же вроде её даже показали. Она просто читает память в строку, если я правильно понял
В этом и суть. Она не читает память в строку, а использует хэш функцию для быстрого получения номера ячейки, откуда брать данные. И происходит это за О1, а не О(n) для чтения всей памяти.
Кстати, важный момент. Тк мы храним в мапе адрес!!! бакетов, то конструкция вида m1:=m2 вызывает копирование адреса в новую область памяти. И изменение m2[a] приведет к изменению по адресу бакета, следовательно m1 формально будет изменена.(формально, тк на самом деле будет изменен бакет, а не сама мапа). На этом моменте нужно быть очень аккуратным, поверьте моим страданиям:(
Не показан рандомизированный получатель значений мапы в циклах перебора for .. range myMap {..}, и его сложность, особенно в части принудительной рандомизации.
Также опущен вопрос горутин и неконсистетности работы с мапами, передаваемыми даже через канал.
Но, в целом, наверное полезно тем, кто не лазил под капот рантайма.. там много чего любопытного и полезного.
П.С. Ну и ещё, можно заметить что сложность поиска по простому массиву (выборка по индексу - смещению) это О(1), и во многих процессорах имеет встроенные команды, исполняемые за 1-4 такта рабочей частоты. Сложность поиска через хеш-функции - это уже миниум О(К) где К - также константна, но в пару тысяч раз больше по величине и содержит несколько вызовов функций, что в ГО само по себе "не даром". А разрешение коллизий, по сути превращает хеш во множество со сложностью О(К+м), где м - количество коллизий на ключе, то есть много дороже чем поиск по индексу массива.
Также не освешена стоимость различных хеш-функций, как то - целочисленные ключи, короткие/длинные строки, структуры данных.
В Java, если ключи Comparable , то вместо связанного списка в бакете создается дерево. Это снижает сложность поиска в бакете с O(N) до O(logN). В этом плане Go ещё направления для оптимизаций
Всегда интересовал вопрос, существует ли общее (не привязанное к ЯП) описание реализации ассоциативных массивов и далее разработчики ЯП реализуют на ЯП?
Или разработчики ЯП реализуют ассоциативный массив каждый раз по своему?
Надеюсь, передел суть вопроса
Я думаю, что существует, но также я уверен, что она не будет одинаково использоваться для каждого ЯП. Поскольку каждый ЯП имеет свои особенности и предпочтения в том, как лучше организовать работу с данными.
Тут еще сильно зависит от того, что такой массив должен уметь. Вот например в php используется описанная в начале этой статьи схема со связанными списками для коллизий, но при этом хэш-таблица умеет понимать, что она "честный" индексированный массив и тогда все работает совсем по другому, ключи записываются вообще без применения хэш-функции.
А все потому, что там массивы и мапы - это два в одном
Мапы в Go: уровень Pro