V: Re-write maps which are currently O(log n) or introduce a new map type with O(1)

[medvednikov]

[ntrel]

AFAIK only a trie has constant time lookup. That uses a lot of memory and is a rare use case that probably doesn't fit general key types well.

O(log n) lookup is fine for maps, they are usually hash tables (or possibly balanced binary trees with a region node allocator).

[medvednikov]

Agreed. And they are much easier to implement.

But sometimes O(1) is required. We'll see.

[ntrel]

Sorry, maybe I was confused about O(1), I thought that meant one operation vs O(k) constant time. But Wikipedia uses O(1) for average lookup time. I was talking worst case.

[agarman]

https://michael.steindorfer.name/publications/oopsla15.pdf is a good candidate for implementing map and set.

[agarman]

https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf for hash table.

[ntrel]

Probably we should port a known good implementation freely licensed to V. This one is very fast and boost licensed so would be compatible:
https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
It now uses Fibonacci hashing to map the key's hash onto the table size to increase slot utilization and postpone growing the table:
https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

[lutherwenxu]

The new map is now implemented as a hashmap with wyhash as the hash. :)