From 1fb32fcf04386f52e72522bd688e69edafd95414 Mon Sep 17 00:00:00 2001 From: Performant Data LLC Date: Sat, 10 Oct 2015 00:02:25 -0700 Subject: SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused --- src/library/scala/collection/mutable/OpenHashMap.scala | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 24f5761cf5..094f7eb63e 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -136,7 +136,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 } -- cgit v1.2.3 From 30d704df5c66986b82cd3158e8e36a0f1b5284ab Mon Sep 17 00:00:00 2001 From: Performant Data LLC Date: Sat, 10 Oct 2015 00:04:09 -0700 Subject: Document some OpenHashMap internal methods. --- src/library/scala/collection/mutable/OpenHashMap.scala | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'src') diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 094f7eb63e..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 -- cgit v1.2.3