diff options
author | Seth Tisue <seth@tisue.net> | 2015-10-15 09:28:25 +0200 |
---|---|---|
committer | Seth Tisue <seth@tisue.net> | 2015-10-15 09:28:25 +0200 |
commit | fe762325ba76fc451fc6a73483429132a382b64e (patch) | |
tree | c1d6942e51511c55a18ad6dd342a2d422fabf4cd /src | |
parent | 14f875c8c9400fbd929de395881d2210165f8b8c (diff) | |
parent | 9c97a7fbf67a9710b87b48e1020bb3c00a1f07a2 (diff) | |
download | scala-fe762325ba76fc451fc6a73483429132a382b64e.tar.gz scala-fe762325ba76fc451fc6a73483429132a382b64e.tar.bz2 scala-fe762325ba76fc451fc6a73483429132a382b64e.zip |
Merge pull request #4798 from performantdata/issue/9513
SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/mutable/OpenHashMap.scala | 19 |
1 files changed, 18 insertions, 1 deletions
diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 24f5761cf5..5f8f5b9a0a 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -81,6 +81,9 @@ extends AbstractMap[Key, Value] h ^ (h >>> 7) ^ (h >>> 4) } + /** Increase the size of the table. + * Copy only the occupied slots, effectively eliminating the deleted slots. + */ private[this] def growTable() = { val oldSize = mask + 1 val newSize = 4 * oldSize @@ -92,8 +95,18 @@ extends AbstractMap[Key, Value] deleted = 0 } + /** Return the index of the first slot in the hash table (in probe order) + * that either is empty, or is or was last occupied by the given key. + */ private[this] def findIndex(key: Key) : Int = findIndex(key, hashOf(key)) + /** Return the index of the first slot in the hash table (in probe order) + * that either is empty, or is or was last occupied by the given key. + * + * This method is an optimization for when the hash value is in hand. + * + * @param hash hash value for `key` + */ private[this] def findIndex(key: Key, hash: Int): Int = { var j = hash @@ -136,7 +149,11 @@ extends AbstractMap[Key, Value] None } else { val res = entry.value - if (entry.value == None) { size += 1; modCount += 1 } + if (entry.value == None) { + size += 1 + deleted -= 1 + modCount += 1 + } entry.value = Some(value) res } |