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

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: