3
$\begingroup$

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books).

Why the names "open" and "closed", and why these seemingly contradictory names for the same method?

$\endgroup$
1
  • 1
    $\begingroup$ While it's no help, this inconsistency has also bugged me for years. I suspect there's no convincing explanation. $\endgroup$ Nov 11, 2014 at 1:15

1 Answer 1

5
$\begingroup$

The short answer is that the terms were coined by different people for different purposes, and it's because hash tables historically had two different contexts: in-memory data structures (I believe that compiler symbol tables was one of the first "killer app" uses) and external-memory data structures (file-based databases).

According to Knuth, the first mention of hashing in the literature is from an internal IBM memo from 1953, and it describes hashing with separate chaining. I don't have a copy of the memo, so I don't know what it was used for. I also don't know (possibly nobody does) who coined the term "closed hashing", but it makes sense to me that with "closed hashing" everything is stored in the table itself, with no need for secondary data structures to do collision resolution. In that sense, the hash table is "closed". From the context, it seems that this was an in-memory use.

We do know who coined the term "open addressing scheme". It's from W.W. Peterson's 1957 paper Addressing for Random-Access Storage (IBM Journal of Research and Development 1.2), though the idea goes back a bit further. The context here is clearly searching in files. The addressing scheme that Peterson analysed was "open", as opposed to "structured" (e.g. sorting the data and using binary search).

$\endgroup$
3
  • $\begingroup$ You mention Knuth; can I assume that you checked TAoCP? If the source is known, chances are that Knuth references it (given that he is the diligent person that he is). $\endgroup$
    – Raphael
    Nov 11, 2014 at 11:26
  • $\begingroup$ I checked a secondary reference which quotes TAoCP, and Knuth does reference it. What I don't have is TAoCP right in front of me at the moment, so I don't have the precise reference. Knuth is the sort of person who can get access to internal IBM memos from the 1950s, and I am not. $\endgroup$
    – Pseudonym
    Nov 11, 2014 at 23:00
  • 1
    $\begingroup$ Knuth uses "open addressing" (TAoCP Vol 3 2nd ed, p525ff); he gives the same reference to Peterson. (Knuth's investigation of different strategies is highly instructive.) There are several references to similar, independent articles (e.g. Ball/Kaman CACM 13 1970, Brent CACM 16 1973, and more in the History section on pages 547ff); these may contain other names even though Knuth does not mention any. (I don't have time to check the references right now.) $\endgroup$
    – Raphael
    Nov 13, 2014 at 11:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.