Document implicit assumptions for "Cost of Collection Operations" table

Location (URL)

https://doc.rust-lang.org/stable/std/collections/index.html#cost-of-collection-operations

Summary

Some extra conditions are needed for achieving the specified time complexities for the different operations, which I think should be documented.

I think these are some of the implicit assumptions not currently documented:

• HashMap:
  • Comparison of two keys must take expected O(1) time and obey the Eq contract
  • Hashing a key must take expected O(1) time and obey the Hash contract
  • The BuildHasher used must either be RandomState or have similar properties (what exactly are the required properties for the costs in the table to hold?)
• BTreeMap:
  • Comparison of two keys must take worst-case O(1) time and obey the Ord contract

Variable-sized Strings is an example which breaks all of these assumption except for the BuildHasher one.
The BuildHasher assumption can be broken with a dummy Hasher that always returns 0 and probably also by any deterministic BuildHasher.

Another assumption is that the elements are O(1) in size, but depending on whether a [u8; k] is considered to have size O(1) (because the size is determined at compile-time) or O(k), this assumption is already always satifisfied. Note that Vec<u8> and similar has size O(1) and the containers can't contain dynamically-sized objects.

Start at the std::collections documentation's “Cost of Collection Operations” table at the linked URL. Review each listed complexity against the implicit key-comparison, hashing, hasher, and element-size assumptions described in the issue. Done means the relevant assumptions and their scope are documented clearly, including the unresolved requirements for BuildHasher.