6 ms·

the domain/range is fixed, so you don't have to allocate, actually, because you can have a fixed sized table and perfect hash :) That said, I agree you can mak

• rep_lodsb 4y ago
  Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. Bit operations and shifts take a single clock cycle, and the mask can be stored in a register throughout the entire loop. If "early exit" brings any improvement, I don't see why the best wouldn't be to combine the two solutions instead of choosing one or the other.
  • dahfizz 4y ago
    > Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation. This is known as a perfect hash[1]. knowing that you will never have collisions does allow for a faster implementation. The hash map can be backed by an array which will never need to be resized, and you don't have to fiddle with linked lists to chain collisions. You're correct though, that this is something you will have to implement yourself. Library hashmaps are going to trade performance for general usefulness. [1] https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function