diff options
| -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: |