0

I would like to have a non-growable hash map whose size is known at compile time that is stored on either the stack or as a global variable. The main use case for this is hash maps in microcontrollers with > 32k of RAM.

Is this even theoretically possible? I know at a certain fullness there would likely be way too many collisions — but when you aren't that full I think it could still be worth it.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
vitiral
  • 8,446
  • 8
  • 29
  • 43

1 Answers1

1

I don't see why it wouldn't be possible. If the keys are all known in advance then theoretically you could find a perfect hash for them, eliminating any overhead in the hashtable size.

If the keys are dynamic but you want to avoid heap allocation, you want to use a open addressing scheme that uses the existing memory. You'll probably want to explicitly keep track of the number of values in the hashtable and reject new insertions once it's full enough (e.g. 80% is probably a good maximum to ensure performance isn't degraded too badly).

Daniel Pryden
  • 59,486
  • 16
  • 97
  • 135
  • thanks! I thought it should be theoretically possible. Would love any existing implementation (in any language) to back that up :) – vitiral May 27 '17 at 17:33