Back in the days of VB for DOS I built a DB where I hashed the first four characters in the key to a number proportional to their alphabetic position. Ignoring spaces, numbers and punctuation, AAAA hashed to 1 and ZZZZ hashed to 32,000. The hash number represented a row in an integer array.

If the row was empty I filled it with the record number where the actual data was stored. If occupied I replaced the original value with a negative number whose absolute value pointed to a record holding the head of a linked list whose entries were the record numbers holding the data of collided keys where the linked list was maintained in alphabetical order of the keys so that a long string of collisions could be searched up and down the linked list with a binary search instead of a sequential search.

Given today’s memory sizes I now could hash a much longer key string to a much bigger number in a much bigger array, e.g. 32M, and have far fewer collisions. Still wasteful of storage, of course, but back on an old DOS 80386 machine my primitive design worked quite well.

Graduate of Stanford University & U.C. Berkeley Law School. Author of 17 novels and over 200 Medium columns on Economics, Politics, Law, Humor & Satire.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store