[jira] [Commented] (SPARK-4690) AppendOnlyMap seems not using Quadratic probing as the JavaDoc

["Sean Owen (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/SPARK-4690?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org