I generally prefer C, so I’m accustomed to building whatever I need
on the fly, such as heaps, linked lists, and especially hash
tables. Few programs use more than a small subset of a data structure’s
features, making their implementation smaller, simpler, and more
efficient than the general case, which must handle every edge
case. A typical hash table tutorial will describe a relatively lengthy
program, but in practice, bespoke hash tables are only a few lines of
code. Over the years I’ve worked out some basic principles for hash
table construction that aid in quick and efficient implementation. This
article covers the technique and philosophy behind what I’ve come to call
the “mask-step-index” (MSI) hash table, which is my standard approach.