[jira] [Commented] (SPARK-4690) AppendOnlyMap seems not using Quadratic probing as the JavaDoc
[
https://issues.apache.org/jira/browse/SPARK-4690?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14233124#comment-14233124
]
Sean Owen commented on SPARK-4690:
--
No, it is using quadratic probing. It adds {{delta}} each time, but {{delta}}
grows by 1 each time too. The offsets are thus 1, 3, 6, 10 ... or the sequence
n*(n+1)/2 which is quadratic.
AppendOnlyMap seems not using Quadratic probing as the JavaDoc
--
Key: SPARK-4690
URL: https://issues.apache.org/jira/browse/SPARK-4690
Project: Spark
Issue Type: Question
Components: Spark Core
Affects Versions: 1.1.0, 1.2.0, 1.3.0
Reporter: Yijie Shen
Priority: Minor
org.apache.spark.util.collection.AppendOnlyMap's Documentation like this:
This implementation uses quadratic probing with a power-of-2
However, the probe procedure in face with a hash collision is just using
linear probing. the code below:
val delta = i
pos = (pos + delta) mask
i += 1
Maybe a bug here?
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
-
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-4690) AppendOnlyMap seems not using Quadratic probing as the JavaDoc
[ https://issues.apache.org/jira/browse/SPARK-4690?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=1429#comment-1429 ] Matei Zaharia commented on SPARK-4690: -- Yup, that's the definition of it. AppendOnlyMap seems not using Quadratic probing as the JavaDoc -- Key: SPARK-4690 URL: https://issues.apache.org/jira/browse/SPARK-4690 Project: Spark Issue Type: Question Components: Spark Core Affects Versions: 1.1.0, 1.2.0, 1.3.0 Reporter: Yijie Shen Priority: Minor org.apache.spark.util.collection.AppendOnlyMap's Documentation like this: This implementation uses quadratic probing with a power-of-2 However, the probe procedure in face with a hash collision is just using linear probing. the code below: val delta = i pos = (pos + delta) mask i += 1 Maybe a bug here? -- This message was sent by Atlassian JIRA (v6.3.4#6332) - To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org
[jira] [Commented] (SPARK-4690) AppendOnlyMap seems not using Quadratic probing as the JavaDoc
[ https://issues.apache.org/jira/browse/SPARK-4690?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=14233817#comment-14233817 ] Yijie Shen commented on SPARK-4690: --- Get it, I was thinking it should be _pos + delta * delta_ before, and didn't realize it is also changing _pos_ each time. Thanks Sean, Matei. AppendOnlyMap seems not using Quadratic probing as the JavaDoc -- Key: SPARK-4690 URL: https://issues.apache.org/jira/browse/SPARK-4690 Project: Spark Issue Type: Question Components: Spark Core Affects Versions: 1.1.0, 1.2.0, 1.3.0 Reporter: Yijie Shen Priority: Minor org.apache.spark.util.collection.AppendOnlyMap's Documentation like this: This implementation uses quadratic probing with a power-of-2 However, the probe procedure in face with a hash collision is just using linear probing. the code below: val delta = i pos = (pos + delta) mask i += 1 Maybe a bug here? -- This message was sent by Atlassian JIRA (v6.3.4#6332) - To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org
