Constant time immutable hash map?

Yeah, the key word here is “effectively” (constant time). Another thing to mention is that n is never greater than 7 (32^6.4 maxes out an int).

I’m already exploring something like this for Elm, just need to find the time. An implementation for Elm already exists (https://github.com/Skinney/collections-ng) but there are bunch of things that can be improved to increase the performance, like a proper hash function and applying lessons learned from Array.Hamt. Expect to read more about this soon.

7 Likes