Question on Params about httprouter

[julienschmidt]

Good question. The hashing of the string is actually more expensive than just comparing it with the names.
Now we all learned that hash map lookups are O(1) and the comparing is O(n), but in this case n is very small, since n is just the number of parameters in the matched URL pattern. I can't think of a good URL structure with n ≥ 10, usually it is just 0 ≤ n ≤ 3.
And the hash map lookup is actually O(1+c), where c is a quite big constant in this case.

Moreover hash maps need a lot more memory.
The router initially used maps ;)

[jackspirou]

@julienschmidt So glad you addressed the O(1) vs O(n). Great answer!

I had no idea about O(1+c) (for hash maps) probably being greater than O(n) where n is usually 0 ≤ n ≤ 3.

Are all hash maps usually a large c constant and O(1+c) or is this just a thing in Go?

Just curious. Thanks!

[jackspirou]

@julienschmidt I noticed that Brad Fitzpatrick suggested using an array instead of a map for part of the HTTP2 golang implementation. Probably because that particular map only contains 10 elements. I wonder what the performance cutoff is in go for maps?

https://www.youtube.com/watch?v=gAfoLwog_MA&feature=youtu.be&t=21m18s

Well played!