diff options
author | Xiangrui Meng <meng@databricks.com> | 2015-03-24 18:58:27 -0700 |
---|---|---|
committer | Andrew Or <andrew@databricks.com> | 2015-03-24 18:58:27 -0700 |
commit | c14ddd97ed662a8429b9b9078bd7c1a5a1dd3d6c (patch) | |
tree | 0cf2eab2c181fe6d549a22c6dfa37b545e6453b8 | |
parent | 94598653bc772e71709163db3fed4048aa7f5f75 (diff) | |
download | spark-c14ddd97ed662a8429b9b9078bd7c1a5a1dd3d6c.tar.gz spark-c14ddd97ed662a8429b9b9078bd7c1a5a1dd3d6c.tar.bz2 spark-c14ddd97ed662a8429b9b9078bd7c1a5a1dd3d6c.zip |
[SPARK-6515] update OpenHashSet impl
Though I don't see any bug in the existing code, the update in this PR makes it read better. rxin
Author: Xiangrui Meng <meng@databricks.com>
Closes #5176 from mengxr/SPARK-6515 and squashes the following commits:
134494d [Xiangrui Meng] update OpenHashSet impl
-rw-r--r-- | core/src/main/scala/org/apache/spark/util/collection/OpenHashSet.scala | 22 |
1 files changed, 9 insertions, 13 deletions
diff --git a/core/src/main/scala/org/apache/spark/util/collection/OpenHashSet.scala b/core/src/main/scala/org/apache/spark/util/collection/OpenHashSet.scala index c80057f95e..1501111a06 100644 --- a/core/src/main/scala/org/apache/spark/util/collection/OpenHashSet.scala +++ b/core/src/main/scala/org/apache/spark/util/collection/OpenHashSet.scala @@ -122,7 +122,7 @@ class OpenHashSet[@specialized(Long, Int) T: ClassTag]( */ def addWithoutResize(k: T): Int = { var pos = hashcode(hasher.hash(k)) & _mask - var i = 1 + var delta = 1 while (true) { if (!_bitset.get(pos)) { // This is a new key. @@ -134,14 +134,12 @@ class OpenHashSet[@specialized(Long, Int) T: ClassTag]( // Found an existing key. return pos } else { - val delta = i + // quadratic probing with values increase by 1, 2, 3, ... pos = (pos + delta) & _mask - i += 1 + delta += 1 } } - // Never reached here - assert(INVALID_POS != INVALID_POS) - INVALID_POS + throw new RuntimeException("Should never reach here.") } /** @@ -163,21 +161,19 @@ class OpenHashSet[@specialized(Long, Int) T: ClassTag]( */ def getPos(k: T): Int = { var pos = hashcode(hasher.hash(k)) & _mask - var i = 1 - val maxProbe = _data.size - while (i < maxProbe) { + var delta = 1 + while (true) { if (!_bitset.get(pos)) { return INVALID_POS } else if (k == _data(pos)) { return pos } else { - val delta = i + // quadratic probing with values increase by 1, 2, 3, ... pos = (pos + delta) & _mask - i += 1 + delta += 1 } } - // Never reached here - INVALID_POS + throw new RuntimeException("Should never reach here.") } /** Return the value at the specified position. */ |