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?
Asked By : Hendrik Jan
Answered By : Pseudonym
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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/32957
0 comments:
Post a Comment
Let us know your responses and feedback