Talk:Linear probing

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Removal of a+mod[edit]

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]

GA Review[edit]

GA toolbox
Reviewing
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.
  • "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?
  • "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:"
  • 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]
  • "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?
  • "Using linear probing, dictionary operation can be implemented in constant time." Possible typo. Should be "operations" plural, yes?
  • "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.
  • 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]

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]


External links modified[edit]

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:

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: 18 January 2022).

  • 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]

External links modified[edit]

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:

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: 18 January 2022).

  • 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]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Linear_probing&oldid=1203606967"