diff options
| author |  Abseil Team <absl-team@google.com> | 2022-05-04 13:21:23 -0700 |
|---|---|---|
| committer |  Copybara-Service <copybara-worker@google.com> | 2022-05-04 13:22:27 -0700 |
| commit | e8cda74967d1fa43182f88396e9030e93501e1a1 (patch) | |
| tree | 6eae0c5da15c49af0c6518ca870c76bc9bf29839 /absl/container/internal/raw_hash_set.h | |
| parent | 384a25d5e19228ceb7641676aefd58c4ca7a9568 (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
Diffstat (limited to 'absl/container/internal/raw_hash_set.h')
| -rw-r--r-- | absl/container/internal/raw_hash_set.h | 6 |
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: |