Talk:Hopscotch hashing

Misc

The "close-to-universal" at the end of the description could do with further explanation, e.g. by linking to another article. -- Ralph Corderoy (talk) 18:27, 18 November 2011 (UTC)

I found a paper with contact author Moran Tzafier that describes the algorithm in detail: http://www.cs.tau.ac.il/~liortzaf/papers/disc2008_submission_98.pdf

size of neighborhood

This article seems to say 2 contradictory things:

• Hopscotch has "a fixed neighborhood H" (typically H = 32 buckets), no matter how many items are stored, which has an O(1) worst-case lookup time. (In a typical implementation, a lookup checks, in the worst case, at most 32 consecutive slots).
• Hopscotch has a "a logarithmic number of items in the worst case ... i.e. it must accommodate log(n) items" in the neighborhood H, so apparently it has an O(log(n)) worst-case lookup time.

Which one is it? --DavidCary (talk) 22:49, 9 June 2023 (UTC)

As I understand the current version of the article is only about the basic variant so the neighborhood-size H is a fixed size and the algorithm has to resize as soon as a virtual bucket contains more than H elements (constant). The text is also a bit unclear as it is broad in some part such that it is not fully clear what version is actually explained. After reading the paper it seems to me that "logarithmic" is incorrect in this case at least. Twistios (talk) 22:12, 31 January 2024 (UTC)