This pull request introduces CuckooSet, a set with constant-time insertions, deletions and lookups that uses a cuckoo hashing algorithm. It exposes the same API as Swift's Set and should feature quicker operations with larger sets, with slightly worse performance in smaller sets.
Implementation
The set only conforms to ExpressibleByArrayLiteral and Sequence since indices are meaningless.
The hash functions in use are FNV-1 and FNV-1a with a 64-bit digest. These are from the swift-fowler-noll-vo repository and are still in pre-release pending performance comparisons.
Objectives
This pull request introduces
CuckooSet
, a set with constant-time insertions, deletions and lookups that uses a cuckoo hashing algorithm. It exposes the same API as Swift'sSet
and should feature quicker operations with larger sets, with slightly worse performance in smaller sets.Implementation
The set only conforms to
ExpressibleByArrayLiteral
andSequence
since indices are meaningless. The hash functions in use areFNV-1
andFNV-1a
with a 64-bit digest. These are from the swift-fowler-noll-vo repository and are still in pre-release pending performance comparisons.Tasks