Talk:Linear probing

Removal of a+mod

It seems to me the +constant version of linear probing described in this article is an unnecessary complication. Given all the analysis (5-independent and tabulation hashing) assumes the step constant is 1 anyway.

I suspect +step and quadratic probing are both just heuristics to accommodate for bad hash functions, hence they should be described in a later section as such. Thomasda (talk) — Preceding undated comment added 18:59, 13 May 2014 (UTC)

I removed the step size complication. It's even worse than you say: using a step size s is equivalent to replacing each memory access A[i] by A[si]. That is, it just permutes the memory cells (making locality of reference worse) without making any change to collisions. —David Eppstein (talk) 00:11, 16 January 2016 (UTC)

GA Review

This review is transcluded from Talk:Linear probing/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Cryptic C62 (talk · contribs) 22:52, 2 April 2016 (UTC)

So far the article looks to be in great shape. I've read through Analysis, and I have a few comments. I will likely finish reading the article later tonight. I've now commented on the entire article.

• "If an empty cell is found, the search returns as its result that the key is not present in the dictionary." For someone with a computer science or mathematics background, it will be obvious why this should be true. However, I think it would benefit from an extra sentence of explanation for lay readers.
  •  Done —David Eppstein (talk) 06:12, 5 April 2016 (UTC)
• "If the insertion would cause the load factor of the table (its fraction of occupied cells) to grow too close to one" I find myself wondering: how close is "too close"? Are we talking 0.75, or 0.9999?
  •  Done —David Eppstein (talk) 06:12, 5 April 2016 (UTC)
• "However, it is not sufficient to do so by causing its cell of the array to become empty again, because this could affect searches for other keys that have a hash value earlier than the emptied cell but that are stored in a position later than the emptied cell" Very long sentence, and the first clause seems unnecessarily wordy. How about "However, it is not sufficient to do so by simply emptying its cell. This will affect searches for other keys that have a hash value earlier than the emptied cell, but that are stored in a position later than the emptied cell:"
  •  Done with some other wording changes. —David Eppstein (talk) 05:54, 6 April 2016 (UTC)
• Related to the above: I think Deletion would greatly benefit from a simple diagram, perhaps similar in style to the diagram in the lead.
  •  Pending. I think this is a good idea, and plan to do it, but it may take more time and effort than the other changes, especially if it also involves matching an existing drawing style. —David Eppstein (talk) 05:54, 6 April 2016 (UTC)
    • I took a shot at putting one together myself. What do you think of this guy? --Cryptic C62 · Talk 21:34, 6 April 2016 (UTC)
      •  Done Thanks! I added it to the article. —David Eppstein (talk) 22:21, 6 April 2016 (UTC)
• "Instead, when a cell i is emptied, it is necessary to search forward through the subsequent cells of the table until finding either another empty cell or a cell containing a key whose hash value is equal to or earlier than i. If such a key is found, its key–value pair is moved back to cell i, emptying the cell it formerly occupied, and the process repeats." What happens when another empty cell is found? Does the operation stop?
  •  Done —David Eppstein (talk) 05:54, 6 April 2016 (UTC)
• "Using linear probing, dictionary operation can be implemented in constant time." Possible typo. Should be "operations" plural, yes?
  •  Done —David Eppstein (talk) 06:16, 5 April 2016 (UTC)
• "when the load factor n/N is bounded away from one" Maybe I missed something, but I don't see that lowercase n is defined in this section.
  •  Done — removed the n/N formula as load factors have already been defined and used earlier (so no need to define it here) and my feeling is that gratutous formulas make articles harder to read. —David Eppstein (talk) 05:23, 6 April 2016 (UTC)
• "In terms of the load factor α (the ratio of the number of elements in the table to the table length)" It seems odd that "load factor" would be defined in parentheses here, despite having used (and linked) the term earlier in this section.
  •  Done —David Eppstein (talk) 06:16, 5 April 2016 (UTC)
• The History section leaves me wondering a few things: First, what methods had people used prior to 1954? Was this a solution to an unsolved problem, or just another tool added to the toolbox? Second, have there really not been any developments on the subject since 1963?
  •  Done — added some prehistory for context, and a precis of a few of the most heavily cited later research papers. —David Eppstein (talk) 05:04, 6 April 2016 (UTC)
• "It was invented in 1954 by Gene Amdahl, Elaine M. McGraw, and Arthur Samuel" from the lead section seems to gloss over the inherent ambiguity presented by this quote: "the system is so natural, that it very likely may have been conceived independently by others either before or since that time." I think the phrasing in the lead could be softened to avoid implying that it is definitive.
  •  Not done — I think the wording as it stands now is sufficiently weaselly that we don't need to soften it. The history section labels the 1954 invention claim as being "according to Knuth" rather than as something we state ourselves as absolute fact. And the lead says only that the 1954 people invented it (true), not that they were the only people to invent it. As long as we don't actually say incorrect things in the lead, I think it's more important there to get the main point across concisely and clearly than to be pedantic about details (that's for later). —David Eppstein (talk) 05:04, 6 April 2016 (UTC)
    • Fair enough. Struck. --Cryptic C62 · Talk 21:34, 6 April 2016 (UTC)

Thanks for putting in the effort on this! --Cryptic C62 · Talk 22:52, 2 April 2016 (UTC)

Ok, thanks! I'll take a look and address your comments. —David Eppstein (talk) 01:13, 3 April 2016 (UTC)

I think everything has been addressed now. —David Eppstein (talk) 22:21, 6 April 2016 (UTC)

Excellent work! I've gone ahead and passed the article. --Cryptic C62 · Talk 23:30, 6 April 2016 (UTC)