summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2022-05-04 13:21:23 -0700
committerGravatar Copybara-Service <copybara-worker@google.com>2022-05-04 13:22:27 -0700
commite8cda74967d1fa43182f88396e9030e93501e1a1 (patch)
tree6eae0c5da15c49af0c6518ca870c76bc9bf29839
parent384a25d5e19228ceb7641676aefd58c4ca7a9568 (diff)
Correct the comment about the probe sequence. It's (i/2 + i)/2 not (i/2 - i)/2.
Also note that this probe sequence visits every group exactly once. PiperOrigin-RevId: 446535602 Change-Id: I13169be3f8ee6a4ddbbe8be84f1e1a482444d0cc
-rw-r--r--absl/container/internal/raw_hash_set.h6
1 files changed, 5 insertions, 1 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index b69a77f0..56251b22 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -228,7 +228,7 @@ void SwapAlloc(AllocType& /*lhs*/, AllocType& /*rhs*/,
//
// Currently, the sequence is a triangular progression of the form
//
-// p(i) := Width * (i^2 - i)/2 + hash (mod mask + 1)
+// p(i) := Width * (i^2 + i)/2 + hash (mod mask + 1)
//
// The use of `Width` ensures that each probe step does not overlap groups;
// the sequence effectively outputs the addresses of *groups* (although not
@@ -241,6 +241,10 @@ void SwapAlloc(AllocType& /*lhs*/, AllocType& /*rhs*/,
// for selecting candidates. However, when those candidates' slots are
// actually inspected, there are no corresponding slots for the cloned bytes,
// so we need to make sure we've treated those offsets as "wrapping around".
+//
+// It turns out that this probe sequence visits every group exactly once if the
+// number of groups is a power of two, since (i^2+i)/2 is a bijection in
+// Z/(2^m). See https://en.wikipedia.org/wiki/Quadratic_probing
template <size_t Width>
class probe_seq {
public: