Talk:Linear probing

Linear probing has been listed as one of the Engineering and technology good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it. Review: April 6, 2016. (Reviewed version).

A fact from Linear probing appeared on Wikipedia's Main Page in the Did you know column on 15 April 2016 (check views). The text of the entry was as follows: Did you know... that Donald Knuth's analysis of the linear probing strategy for resolving collisions in hash tables has been called "a landmark in the analysis of algorithms"? A record of the entry may be seen at Wikipedia:Did you know archive/2016/April. The nomination discussion and review may be seen at Template:Did you know nominations/Linear probing.

This article is rated GA-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing Mid‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing Mid This article has been rated as Mid-importance on the project's importance scale.

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)Reply

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)Reply

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)Reply

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)Reply
• "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)Reply
• "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)Reply
• 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)Reply
    • 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)Reply
      •  Done Thanks! I added it to the article. —David Eppstein (talk) 22:21, 6 April 2016 (UTC)Reply
• "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)Reply
• "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)Reply
• "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)Reply
• "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)Reply
• 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)Reply
• "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)Reply
    • Fair enough. Struck. --Cryptic C62 · Talk 21:34, 6 April 2016 (UTC)Reply

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

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

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

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

Hello fellow Wikipedians,

I have just modified one external link on Linear probing. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20150214032028/http://11011110.livejournal.com/232567.html to http://11011110.livejournal.com/232567.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 20:28, 5 April 2017 (UTC)Reply

Hello fellow Wikipedians,

I have just modified one external link on Linear probing. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html to http://algo.inria.fr/AofA/Research/11-97.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 17:27, 22 December 2017 (UTC)Reply