We need a CertCollection type
openpgp/src/parse/stream.rs) has quadratic complexity.
The basic problem is: we have
n keys (actually, certificates, but that's irrelevant for this disucssion), which we store in a vector, and we need to lookup
m keys. Since we have to scan the vector for each lookup, the complexity is
n * m.
It would be nice to use a hash table: insert the
n keys into the hash table, and then do the
m lookups. This has a cost of
n + m.
Using the current definition of
KeyHandle this is not possible, because
KeyHandle does not implement
Eq. This is because
Eq must be transitive, and we can't assert that a fingerprint and a key id are the same as multiple fingerprints may have the same key id.
This wasn't always the case. Previously, fingerprints and key ids were always considered unequal. But, this required the caller to deconstruct the
KeyHandle manually, which partially defeats the purpose of the
KeyHandle, and it is error prone for the user.
Instead, we could use a multi-level hash. The top-level hash hashes all keys with the same key id into a bucket, and the second level hash maps fingerprints to certificates. Then, when we need to lookup a key by key id, we can iterate over all keys in the bucket. But, if we need to look up a key by fingerprint, we just need two hash lookups. This is optimal.
We could require our users to do this. But, it is complicated: the user not only has to manage the two hashes, they have to remember to merge certificates with the same fingerprint. Or, we could provide a new data structure that hides this complexity from users. The basic lookup interface would take a
KeyHandle and return all candidate certificates/keys.