What a delightful breath of fresh air. I get awfully tired of the hash-tables-are-constant-time and worst-case-behavior-is-too-rare-to-worry-about nonsense that floods the web.

And here we have the problem and proposed solutions clearly explained, and presented in a pleasant, readable design.

Excellent post. Keep up the good work.