История изменений
Исправление mix_mix, (текущая версия) :
Эффективность хэш-функции определяется лишь количеством коллизий. В качестве одной можно взять убогую strlen(key)%buckets, а можно murmur(key)%buckets, — все они будут работать за линейное время относительно длины ключа, но эффективность разная будет, да.
Сложность доступа же по ключу в обоих случаях будет оставаться амортизированной константой относительно количества ключей с высокой вероятностью (т.е. при определённом load factor).
Исходная версия mix_mix, :
Эффективность хэш-функции определяется лишь количеством коллизий. Ты можешь брать strlen(key)%buckets, а можешь crc32(key)%buckets, — все они будут за линейное время (относительно длины ключа) работать, но эффективность разная да. Сложность доступа же по ключу в обоих случаях будет оставаться амортизированной константой (относительно количества ключей) с высокой вероятностью.