Snap for 8564071 from 3dc30e23e1f24a7cf8862f6fed1166a68ddca94d to mainline-permission-releaseaml_per_331913010aml_per_331812030aml_per_331710050aml_per_331611010aml_per_331512020aml_per_331411000aml_per_331313010aml_per_331115020aml_per_331019040aml_per_330912010aml_per_330811030android13-mainline-permission-release

Change-Id: Ifbf3a6a6d3ca1dfda4cdb36664b7cd685d7e4ccc

25 files changed, 975 insertions, 192 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 6f8967e..bace32e 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
 {
   "git": {
-    "sha1": "80489689035c908f1096c07a8a0c51250f3dc979"
+    "sha1": "c4ac207b8f266ff3becd123f693f07536b97d088"
   }
 }
diff --git a/.github/dependabot.yml b/.github/dependabot.yml
new file mode 100644
index 0000000..cf039be
--- /dev/null
+++ b/.github/dependabot.yml
@@ -0,0 +1,8 @@
+version: 2
+updates:
+- package-ecosystem: cargo
+  directory: "/"
+  schedule:
+    interval: daily
+    time: "11:00"
+  open-pull-requests-limit: 10
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
new file mode 100644
index 0000000..df81fe8
--- /dev/null
+++ b/.github/workflows/ci.yml
@@ -0,0 +1,71 @@
+on: [push, pull_request]
+
+name: CI
+
+jobs:
+  check:
+    name: Check
+    runs-on: ubuntu-latest
+    strategy:
+      matrix:
+        rust:
+          - stable
+          - 1.46.0
+        features:
+          - --features=std
+          - --no-default-features --features=alloc,ahash
+    steps:
+      - uses: actions/checkout@v2
+      - uses: actions-rs/toolchain@v1
+        with:
+          profile: minimal
+          toolchain: ${{ matrix.rust }}
+          override: true
+      - uses: actions-rs/cargo@v1
+        with:
+          command: check
+          args: --all-targets ${{ matrix.features }}
+
+  test:
+    name: Test Suite
+    runs-on: ubuntu-latest
+    strategy:
+      matrix:
+        rust:
+          - stable
+          - 1.46.0
+        features:
+          - --features=std
+          - --no-default-features --features=alloc,ahash
+    steps:
+      - uses: actions/checkout@v2
+      - uses: actions-rs/toolchain@v1
+        with:
+          profile: minimal
+          toolchain: ${{ matrix.rust }}
+          override: true
+      - uses: actions-rs/cargo@v1
+        with:
+          command: test
+          args: ${{ matrix.features }}
+
+  clippy:
+    name: Clippy
+    runs-on: ubuntu-latest
+    strategy:
+      matrix:
+        rust:
+          - stable
+          - 1.46.0
+    steps:
+      - uses: actions/checkout@v2
+      - uses: actions-rs/toolchain@v1
+        with:
+          profile: minimal
+          toolchain: ${{ matrix.rust }}
+          override: true
+      - run: rustup component add clippy
+      - uses: actions-rs/cargo@v1
+        with:
+          command: clippy
+          args: -- -D warnings
diff --git a/.travis.yml b/.travis.yml
deleted file mode 100644
index 563df5b..0000000
--- a/.travis.yml
+++ /dev/null
@@ -1,23 +0,0 @@
-language: rust
-rust:
-  - stable
-  - beta
-  - nightly
-# Oldest supported version:
-  - 1.32.0
-
-dist: trusty
-sudo: false
-
-matrix:
-  allow_failures:
-    - rust: nightly
-
-notifications:
-  email:
-    on_success: never
-
-addons:
-  apt:
-    packages:
-      - texinfo
diff --git a/Android.bp b/Android.bp
index 33c19f1..2ff1215 100644
--- a/Android.bp
+++ b/Android.bp
@@ -1,4 +1,5 @@
-// This file is generated by cargo2android.py --device --run --dependencies.
+// This file is generated by cargo2android.py --config cargo2android.json.
+// Do not modify this file as changes will be overridden on upgrade.
 
 package {
     default_applicable_licenses: ["external_rust_crates_weak-table_license"],
@@ -21,6 +22,12 @@ rust_library {
     name: "libweak_table",
     host_supported: true,
     crate_name: "weak_table",
+    cargo_env_compat: true,
+    cargo_pkg_version: "0.3.2",
     srcs: ["src/lib.rs"],
     edition: "2018",
+    features: [
+        "default",
+        "std",
+    ],
 }
diff --git a/CHANGELOG.md b/CHANGELOG.md
new file mode 100644
index 0000000..68c526e
--- /dev/null
+++ b/CHANGELOG.md
@@ -0,0 +1,89 @@
+# Changelog
+
+All notable changes to this project will be documented in this file.
+
+The format is based on [Keep a Changelog] and this project adheres to
+[Semantic Versioning].
+
+[Keep a Changelog]: http://keepachangelog.com/en/1.0.0/
+[Semantic Versioning]: http://semver.org/spec/v2.0.0.html
+
+## [Next Release]
+
+## [0.3.2] - 2021-12-01
+
+## [0.3.1] - 2021-11-30
+
+### Added
+- `no_std` compatibility (h/t @tsao-chi)
+
+## [0.2.4] - 2020-06-27
+
+### Fixed
+- Bad bucket selection on collision (h/t Andrew Browne
+  `<dersaidin@dersaidin.net>`).
+
+## [0.2.3] - 2018-05-30
+
+### Fixed
+- Use `Rc::ptr_eq` to compare `Rc`s by address.
+
+## [0.2.2] - 2018-05-22
+
+### Fixed
+- Weak–weak submap operations were missing a line of code.
+
+### Added
+- `{PtrWeakHashSet,PtrWeakKeyHashMap}::is_empty()` methods.
+
+## [0.2.1] - 2018-05-22
+
+### Fixed
+- documentation
+- a test that was breaking on an older `rustc`
+
+## [0.2.0] - 2018-05-22
+
+### Renamed
+- from `WeakElement::expired` to `WeakElement::is_expired`
+
+### Improved
+- documentation
+
+## [0.1.3] - 2018-05-22
+
+### Added
+- documentation of minimum supported `rustc`
+- a test
+
+## [0.1.2] - 2018-05-21
+
+### Added
+- `WeakKeyHashMap::{get_key, get_both, get_both_mut}` methods
+- `WeakWeakHashMap::{get_key, get_both}` methods
+- `WeakHashSet::get` method
+
+### Changed
+- Values stored behind `Rc`s can now be `?Sized`.
+
+### Removed
+- `struct RcKey<K>`
+
+### Improved
+- documentation
+
+## [0.1.1] - 2018-03-05
+
+Initial release.
+
+[Next Release]: <https://github.com/tov/weak-table-rs/compare/v0.3.2...HEAD>
+[0.3.2]: <https://github.com/tov/weak-table-rs/compare/v0.3.1...v0.3.2>
+[0.3.1]: <https://github.com/tov/weak-table-rs/compare/v0.3.1-alpha.0...v0.3.1>
+[0.2.4]: <https://github.com/tov/weak-table-rs/compare/0.2.3...0.2.4>
+[0.2.3]: <https://github.com/tov/weak-table-rs/compare/0.2.2...0.2.3>
+[0.2.2]: <https://github.com/tov/weak-table-rs/compare/0.2.1...0.2.2>
+[0.2.1]: <https://github.com/tov/weak-table-rs/compare/0.2.0...0.2.1>
+[0.2.0]: <https://github.com/tov/weak-table-rs/compare/0.1.3...0.2.0>
+[0.1.3]: <https://github.com/tov/weak-table-rs/compare/0.1.2...0.1.3>
+[0.1.2]: <https://github.com/tov/weak-table-rs/compare/0.1.1...0.1.2>
+[0.1.1]: <https://github.com/tov/weak-table-rs/tree/0.1.1>
diff --git a/Cargo.toml b/Cargo.toml
index 343cfab..b2e6cc8 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,27 +3,33 @@
 # When uploading crates to the registry Cargo will automatically
 # "normalize" Cargo.toml files for maximal compatibility
 # with all versions of Cargo and also rewrite `path` dependencies
-# to registry (e.g., crates.io) dependencies
+# to registry (e.g., crates.io) dependencies.
 #
-# If you believe there's an error in this file please file an
-# issue against the rust-lang/cargo repository. If you're
-# editing this file be aware that the upstream Cargo.toml
-# will likely look very different (and much more reasonable)
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
 
 [package]
 edition = "2018"
 name = "weak-table"
-version = "0.3.0"
+version = "0.3.2"
 authors = ["Jesse A. Tov <jesse.tov@gmail.com>"]
 description = "Weak hash maps and sets"
 readme = "README.md"
-keywords = ["containers", "Rc", "Arc", "weak"]
+keywords = ["containers", "Rc", "Arc", "weak", "no_std"]
 license = "MIT"
 repository = "https://github.com/tov/weak-table-rs"
-
-[dependencies]
+[dependencies.ahash]
+version = "0.7.6"
+features = []
+optional = true
 [dev-dependencies.quickcheck]
-version = "0.9"
+version = "1"
 
 [dev-dependencies.rand]
-version = "0.7.2"
+version = "0.8.4"
+
+[features]
+alloc = []
+default = ["std"]
+std = []
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 7cb87e3..3594791 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,17 +1,24 @@
 [package]
 name = "weak-table"
-version = "0.3.0"
+version = "0.3.2"
 authors = ["Jesse A. Tov <jesse.tov@gmail.com>"]
 description = "Weak hash maps and sets"
 repository = "https://github.com/tov/weak-table-rs"
 readme = "README.md"
 license = "MIT"
-keywords = ["containers", "Rc", "Arc", "weak"]
+keywords = ["containers", "Rc", "Arc", "weak", "no_std"]
 edition = "2018"
 
 [dependencies]
+ahash = { version = "0.7.6", optional = true, features = [] }
 
 [dev-dependencies]
-quickcheck = "0.9"
-rand = "0.7.2"
+quickcheck = "1"
+rand = "0.8.4"
 
+[features]
+default = ["std"]
+std = []
+
+# This feature doesn’t actually do anything. TODO: remove in v0.4.
+alloc = []
diff --git a/METADATA b/METADATA
index 29097c3..3317bcc 100644
--- a/METADATA
+++ b/METADATA
@@ -1,7 +1,5 @@
 name: "weak-table"
-description:
-    "Weak hash maps and sets"
-
+description: "Weak hash maps and sets"
 third_party {
   url {
     type: HOMEPAGE
@@ -9,9 +7,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/weak-table/weak-table-0.3.0.crate"
+    value: "https://static.crates.io/crates/weak-table/weak-table-0.3.2.crate"
   }
-  version: "0.3.0"
-  last_upgrade_date { year: 2020 month: 10 day: 9 }
+  version: "0.3.2"
   license_type: NOTICE
+  last_upgrade_date {
+    year: 2022
+    month: 3
+    day: 1
+  }
 }
diff --git a/README.md b/README.md
index 56fa462..9d4ac80 100644
--- a/README.md
+++ b/README.md
@@ -1,13 +1,25 @@
 # weak-table: weak hash maps and sets for Rust
 
-[![Build Status](https://travis-ci.org/tov/weak-table-rs.svg?branch=master)](https://travis-ci.org/tov/weak-table-rs)
+[![Build Status](https://github.com/tov/weak-table-rs/actions/workflows/ci.yml/badge.svg)](https://github.com/tov/weak-table-rs/actions)
 [![Crates.io](https://img.shields.io/crates/v/weak-table.svg?maxAge=2592000)](https://crates.io/crates/weak-table)
 [![License: MIT](https://img.shields.io/badge/license-MIT-blue.svg)](LICENSE-MIT)
 
 This crate defines several kinds of weak hash maps and sets. See 
 the [full API documentation](http://docs.rs/weak-table/) for details.
 
-This crate supports Rust version 1.32 and later.
+### Rust version support
+
+This crate supports Rust version 1.46 and later.
+
+### Crate features
+
+`weak-table` is built with the `std` feature, which enables
+functionality dependent on the `std` library, enabled by default.
+Optionally, the following dependency may be enabled:
+
+  - `ahash`: use `ahash`’s hasher rather than the `std` hasher
+
+If the `std` feature is disabled (for no_std) then the `ahash` dependency **must** be enabled.
 
 ### Examples
 
diff --git a/cargo2android.json b/cargo2android.json
new file mode 100644
index 0000000..bf78496
--- /dev/null
+++ b/cargo2android.json
@@ -0,0 +1,4 @@
+{
+  "device": true,
+  "run": true
+}
\ No newline at end of file
diff --git a/release.toml b/release.toml
index 5d7a460..03d6f0d 100644
--- a/release.toml
+++ b/release.toml
@@ -1,3 +1,17 @@
-pre-release-replacements = [
-  { file="src/lib.rs", search="https://docs[.]rs/weak-table/[0-9.]*", replace="https://docs.rs/weak-table/{{version}}" }
-]
+tag-name    = "v{{version}}"
+
+[[pre-release-replacements]]
+file        = "src/lib.rs"
+search      = "https://docs[.]rs/weak-table/[0-9.]*"
+replace     = "https://docs.rs/weak-table/{{version}}"
+
+[[pre-release-replacements]]
+file        = "CHANGELOG.md"
+search      = "## \\[Next Release\\]"
+replace     = "## [Next Release]\n\n## [{{version}}] - {{date}}"
+
+[[pre-release-replacements]]
+file        = "CHANGELOG.md"
+search      = "\\[Next Release\\]: <https://github.com/tov/weak-table-rs/compare/v*[0-9.]*[.][.][.]HEAD>"
+replace     = '''[Next Release]: <https://github.com/tov/weak-table-rs/compare/v{{version}}...HEAD>
+[{{version}}]: <https://github.com/tov/weak-table-rs/compare/v{{prev_version}}...v{{version}}>'''
diff --git a/src/by_ptr.rs b/src/by_ptr.rs
index b541f9e..7dc4c77 100644
--- a/src/by_ptr.rs
+++ b/src/by_ptr.rs
@@ -1,4 +1,4 @@
-use std::ops::Deref;
+use crate::compat::*;
 
 use super::traits::*;
 
diff --git a/src/compat.rs b/src/compat.rs
new file mode 100644
index 0000000..4644b17
--- /dev/null
+++ b/src/compat.rs
@@ -0,0 +1,56 @@
+//! `no_std` compatibility
+
+// If we depend on `ahash`, use its hasher.
+#[cfg(feature = "ahash")]
+pub use ahash::RandomState;
+
+// Use the `std` hasher if we don’t depend on `ahash` but do depend on
+// `std`.
+#[cfg(all(not(feature = "ahash"), feature = "std"))]
+pub use std::collections::hash_map::RandomState;
+
+// If we depend on neither `ahash` nor `std` then it’s an error.
+#[cfg(not(any(feature = "ahash", feature = "std")))]
+compile_error!("weak-table: no_std requires that you enable the `ahash` feature.");
+
+// If we depend on `std`, alias `lib` to `std`.
+#[cfg(feature = "std")]
+mod lib {
+    extern crate std;
+    pub use std::*;
+}
+
+// Otherwise, we are `no_std`, so alias `lib` to `alloc`.
+#[cfg(not(feature = "std"))]
+mod lib {
+    extern crate alloc;
+    pub use alloc::*;
+}
+
+// Stuff from `std`/`alloc` that we use often.
+pub use lib::{
+    boxed::Box,
+    rc,
+    slice,
+    string::String,
+    sync,
+    vec::{self, Vec},
+};
+
+// Stuff from `core` that we use often:
+pub use core::{
+    borrow::Borrow,
+    cmp::max,
+    hash::{BuildHasher, Hash, Hasher},
+    iter::{self, FromIterator},
+    fmt::{self, Debug, Formatter},
+    mem,
+    ops::{self, Deref, Index, IndexMut},
+};
+
+// When testing, we need the `eprintln` macro from `std`:
+#[cfg(test)]
+extern crate std;
+
+#[cfg(test)]
+pub use std::eprintln;
diff --git a/src/lib.rs b/src/lib.rs
index ce5e596..6851e7b 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,4 +1,3 @@
-#![doc(html_root_url = "https://docs.rs/weak-table/0.3.0")]
 //! This library offers a variety of weak hash tables:
 //!
 //!   - For a hash map where the keys are held by weak pointers and compared by key value, see
@@ -27,7 +26,32 @@
 //! To add support for your own weak pointers, see
 //! [the traits `WeakElement` and `WeakKey`](traits/).
 //!
-//! This crate supports Rust version 1.32 and later.
+//! ## Rust version support
+//!
+//! This crate supports Rust version 1.46 and later.
+//!
+//! ## Asymptotic complexity
+//!
+//! Most operations have documented asymptotic time complexities. When time complexities are
+//! given in big-*O* notation, the following parameters are used consistently:
+//!
+//!   - *n*: the *capacity* of the map or set being accessed or constructed
+//!
+//!   - *m*: the *capacity* of a second map/set involved in a submap/subset operation
+//!
+//!   - *p*: the length of the probe sequence for the key in question
+//!
+//! Note that *p* ∈ *O*(*n*), but we expect it to be *O*(1).
+//!
+//! # Crate features
+//!
+//! `weak-table` is built with the `std` feature, which enables
+//! functionality dependent on the `std` library, enabled by default.
+//! Optionally, the following dependency may be enabled:
+//!
+//!   - `ahash`: use `ahash`’s hasher rather than the `std` hasher
+//!
+//! If the `std` feature is disabled (for no_std) then the `ahash` dependency **must** be enabled.
 //!
 //! # Examples
 //!
@@ -117,7 +141,11 @@
 //! }
 //! ```
 
-use std::collections::hash_map::RandomState;
+#![doc(html_root_url = "https://docs.rs/weak-table/0.3.2")]
+
+#![cfg_attr(not(feature = "std"), no_std)]
+
+use self::compat::*;
 
 pub mod traits;
 pub mod weak_key_hash_map;
@@ -128,6 +156,7 @@ pub mod ptr_weak_weak_hash_map;
 pub mod weak_hash_set;
 pub mod ptr_weak_hash_set;
 
+mod compat;
 mod util;
 mod by_ptr;
 mod size_policy;
diff --git a/src/ptr_weak_hash_set.rs b/src/ptr_weak_hash_set.rs
index 9a38b4e..9f6cb71 100644
--- a/src/ptr_weak_hash_set.rs
+++ b/src/ptr_weak_hash_set.rs
@@ -1,10 +1,6 @@
 //! A hash set where the elements are held by weak pointers and compared by pointer.
 
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::BuildHasher;
-use std::iter::FromIterator;
-use std::ops::Deref;
+use crate::compat::*;
 
 use super::traits::*;
 use super::ptr_weak_key_hash_map as base;
@@ -16,11 +12,15 @@ impl <T: WeakElement> PtrWeakHashSet<T, RandomState>
     where T::Strong: Deref
 {
     /// Creates an empty `PtrWeakHashSet`.
+    ///
+    /// *O*(1) time
     pub fn new() -> Self {
         PtrWeakHashSet(base::PtrWeakKeyHashMap::new())
     }
 
     /// Creates an empty `PtrWeakHashSet` with the given capacity.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity(capacity: usize) -> Self {
         PtrWeakHashSet(base::PtrWeakKeyHashMap::with_capacity(capacity))
     }
@@ -30,41 +30,57 @@ impl <T: WeakElement, S: BuildHasher> PtrWeakHashSet<T, S>
     where T::Strong: Deref
 {
     /// Creates an empty `PtrWeakHashSet` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_hasher(hash_builder: S) -> Self {
         PtrWeakHashSet(base::PtrWeakKeyHashMap::with_hasher(hash_builder))
     }
 
     /// Creates an empty `PtrWeakHashSet` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
         PtrWeakHashSet(base::PtrWeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder))
     }
 
     /// Returns a reference to the map's `BuildHasher`.
+    ///
+    /// *O*(1) time
     pub fn hasher(&self) -> &S {
         self.0.hasher()
     }
 
     /// Returns the number of elements the map can hold without reallocating.
+    ///
+    /// *O*(1) time
     pub fn capacity(&self) -> usize {
         self.0.capacity()
     }
 
     /// Removes all mappings whose keys have expired.
+    ///
+    /// *O*(*n*) time
     pub fn remove_expired(&mut self) {
         self.0.remove_expired()
     }
 
     /// Reserves room for additional elements.
+    ///
+    /// *O*(*n*) time
     pub fn reserve(&mut self, additional_capacity: usize) {
         self.0.reserve(additional_capacity)
     }
 
     /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+    ///
+    /// *O*(*n*) time
     pub fn shrink_to_fit(&mut self) {
         self.0.shrink_to_fit()
     }
 
     /// Returns an over-approximation of the number of elements.
+    ///
+    /// *O*(1) time
     pub fn len(&self) -> usize {
         self.0.len()
     }
@@ -73,6 +89,8 @@ impl <T: WeakElement, S: BuildHasher> PtrWeakHashSet<T, S>
     ///
     /// This could answer `false` for an empty set whose elements have
     /// expired but have yet to be collected.
+    ///
+    /// *O*(1) time
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
@@ -81,27 +99,37 @@ impl <T: WeakElement, S: BuildHasher> PtrWeakHashSet<T, S>
     /// The proportion of buckets that are used.
     ///
     /// This is an over-approximation because of expired elements.
+    ///
+    /// *O*(1) time
     pub fn load_factor(&self) -> f32 {
         self.0.load_factor()
     }
 
     /// Removes all associations from the map.
+    ///
+    /// *O*(*n*) time
     pub fn clear(&mut self) {
         self.0.clear()
     }
 
     /// Returns true if the map contains the specified key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn contains(&self, key: &T::Strong) -> bool {
         self.0.contains_key(key)
     }
 
     /// Unconditionally inserts the value, returning the old value if already present. Does not
     /// replace the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(&mut self, key: T::Strong) -> bool {
         self.0.insert(key, ()).is_some()
     }
 
     /// Removes the entry with the given key, if it exists, and returns the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove(&mut self, key: &T::Strong) -> bool {
         self.0.remove(key).is_some()
     }
@@ -109,6 +137,8 @@ impl <T: WeakElement, S: BuildHasher> PtrWeakHashSet<T, S>
     /// Removes all mappings not satisfying the given predicate.
     ///
     /// Also removes any expired mappings.
+    ///
+    /// *O*(*n*) time
     pub fn retain<F>(&mut self, mut f: F)
         where F: FnMut(T::Strong) -> bool
     {
@@ -116,6 +146,10 @@ impl <T: WeakElement, S: BuildHasher> PtrWeakHashSet<T, S>
     }
 
     /// Is self a subset of other?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_subset<S1>(&self, other: &PtrWeakHashSet<T, S1>) -> bool
         where S1: BuildHasher
     {
@@ -172,11 +206,15 @@ impl<T: WeakElement, S> PtrWeakHashSet<T, S>
     where T::Strong: Deref
 {
     /// Gets an iterator over the keys and values.
+    ///
+    /// *O*(1) time
     pub fn iter(&self) -> Iter<T> {
         Iter(self.0.keys())
     }
 
     /// Gets a draining iterator, which removes all the values but retains the storage.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     pub fn drain(&mut self) -> Drain<T> {
         Drain(self.0.drain())
     }
@@ -239,6 +277,9 @@ impl<T: WeakElement, S> IntoIterator for PtrWeakHashSet<T, S> {
     type Item = T::Strong;
     type IntoIter = IntoIter<T>;
 
+    /// Creates an owning iterator from `self`.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     fn into_iter(self) -> Self::IntoIter {
         IntoIter(self.0.into_iter())
     }
@@ -250,6 +291,9 @@ impl<'a, T: WeakElement, S> IntoIterator for &'a PtrWeakHashSet<T, S>
     type Item = T::Strong;
     type IntoIter = Iter<'a, T>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         Iter(self.0.keys())
     }
diff --git a/src/ptr_weak_key_hash_map.rs b/src/ptr_weak_key_hash_map.rs
index cd48809..2cd5591 100644
--- a/src/ptr_weak_key_hash_map.rs
+++ b/src/ptr_weak_key_hash_map.rs
@@ -1,10 +1,6 @@
 //! A hash map where the keys are held by weak pointers and compared by pointer.
 
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::BuildHasher;
-use std::iter::FromIterator;
-use std::ops::{Deref, Index, IndexMut};
+use crate::compat::*;
 
 use super::by_ptr::*;
 use super::traits::*;
@@ -17,11 +13,15 @@ impl <K: WeakElement, V> PtrWeakKeyHashMap<K, V, RandomState>
     where K::Strong: Deref
 {
     /// Creates an empty `PtrWeakKeyHashMap`.
+    ///
+    /// *O*(1) time
     pub fn new() -> Self {
         PtrWeakKeyHashMap(base::WeakKeyHashMap::new())
     }
 
     /// Creates an empty `PtrWeakKeyHashMap` with the given capacity.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity(capacity: usize) -> Self {
         PtrWeakKeyHashMap(base::WeakKeyHashMap::with_capacity(capacity))
     }
@@ -31,41 +31,57 @@ impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
     where K::Strong: Deref
 {
     /// Creates an empty `PtrWeakKeyHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_hasher(hash_builder: S) -> Self {
         PtrWeakKeyHashMap(base::WeakKeyHashMap::with_hasher(hash_builder))
     }
 
     /// Creates an empty `PtrWeakKeyHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
         PtrWeakKeyHashMap(base::WeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder))
     }
 
     /// Returns a reference to the map's `BuildHasher`.
+    ///
+    /// *O*(1) time
     pub fn hasher(&self) -> &S {
         self.0.hasher()
     }
 
     /// Returns the number of elements the map can hold without reallocating.
+    ///
+    /// *O*(1) time
     pub fn capacity(&self) -> usize {
         self.0.capacity()
     }
 
     /// Removes all mappings whose keys have expired.
+    ///
+    /// *O*(*n*) time
     pub fn remove_expired(&mut self) {
         self.0.remove_expired()
     }
 
     /// Reserves room for additional elements.
+    ///
+    /// *O*(*n*) time
     pub fn reserve(&mut self, additional_capacity: usize) {
         self.0.reserve(additional_capacity)
     }
 
     /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+    ///
+    /// *O*(*n*) time
     pub fn shrink_to_fit(&mut self) {
         self.0.shrink_to_fit()
     }
 
     /// Returns an over-approximation of the number of elements.
+    ///
+    /// *O*(1) time
     pub fn len(&self) -> usize {
         self.0.len()
     }
@@ -74,6 +90,8 @@ impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
     ///
     /// This could answer `false` for an empty map whose keys have
     /// expired but have yet to be collected.
+    ///
+    /// *O*(1) time
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
@@ -81,42 +99,58 @@ impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
     /// The proportion of buckets that are used.
     ///
     /// This is an over-approximation because of expired keys.
+    ///
+    /// *O*(1) time
     pub fn load_factor(&self) -> f32 {
         self.0.load_factor()
     }
 
     /// Gets the requested entry.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> {
         self.0.entry(key)
     }
 
     /// Removes all associations from the map.
+    ///
+    /// *O*(*n*) time
     pub fn clear(&mut self) {
         self.0.clear()
     }
 
     /// Returns a reference to the value corresponding to the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get(&self, key: &K::Strong) -> Option<&V> {
         self.0.get(&(key.deref() as *const _))
     }
 
     /// Returns true if the map contains the specified key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn contains_key(&self, key:&K::Strong) -> bool {
         self.0.contains_key(&(key.deref() as *const _))
     }
 
     /// Returns a mutable reference to the value corresponding to the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get_mut(&mut self, key: &K::Strong) -> Option<&mut V> {
         self.0.get_mut(&(key.deref() as *const _))
     }
 
     /// Unconditionally inserts the value, returning the old value if already present. Does not
     /// replace the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
         self.0.insert(key, value)
     }
 
     /// Removes the entry with the given key, if it exists, and returns the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove(&mut self, key: &K::Strong) -> Option<V> {
         self.0.remove(&(key.deref() as *const _))
     }
@@ -124,6 +158,8 @@ impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
     /// Removes all mappings not satisfying the given predicate.
     ///
     /// Also removes any expired mappings.
+    ///
+    /// *O*(*n*) time
     pub fn retain<F>(&mut self, f: F)
         where F: FnMut(K::Strong, &mut V) -> bool
     {
@@ -134,6 +170,10 @@ impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
     ///
     /// In particular, all the keys of self must be in other and the values must compare true with
     /// value_equal.
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn submap_with<F, S1, V1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>, value_equal: F) -> bool
     where F: FnMut(&V, &V1) -> bool,
           S1: BuildHasher
@@ -142,6 +182,10 @@ impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
     }
 
     /// Is self a submap of other?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool
         where V: PartialEq<V1>,
             S1: BuildHasher
@@ -150,6 +194,10 @@ impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
     }
 
     /// Are the keys of self a subset of the keys of other?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool
         where S1: BuildHasher
     {
@@ -161,31 +209,43 @@ impl<K: WeakElement, V, S> PtrWeakKeyHashMap<K, V, S>
     where K::Strong: Deref
 {
     /// Gets an iterator over the keys and values.
+    ///
+    /// *O*(1) time
     pub fn iter(&self) -> Iter<ByPtr<K>, V> {
         self.0.iter()
     }
 
     /// Gets an iterator over the keys.
+    ///
+    /// *O*(1) time
     pub fn keys(&self) -> Keys<ByPtr<K>, V> {
         self.0.keys()
     }
 
     /// Gets an iterator over the values.
+    ///
+    /// *O*(1) time
     pub fn values(&self) -> Values<ByPtr<K>, V> {
         self.0.values()
     }
 
     /// Gets an iterator over the keys and mutable values.
+    ///
+    /// *O*(1) time
     pub fn iter_mut(&mut self) -> IterMut<ByPtr<K>, V> {
         self.0.iter_mut()
     }
 
     /// Gets an iterator over the mutable values.
+    ///
+    /// *O*(1) time
     pub fn values_mut(&mut self) -> ValuesMut<ByPtr<K>, V> {
         self.0.values_mut()
     }
 
     /// Gets a draining iterator, which removes all the values but retains the storage.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     pub fn drain(&mut self) -> Drain<ByPtr<K>, V> {
         self.0.drain()
     }
@@ -283,6 +343,9 @@ impl<K: WeakElement, V, S> IntoIterator for PtrWeakKeyHashMap<K, V, S> {
     type Item = (K::Strong, V);
     type IntoIter = IntoIter<ByPtr<K>, V>;
 
+    /// Creates an owning iterator from `self`.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     fn into_iter(self) -> Self::IntoIter {
         self.0.into_iter()
     }
@@ -292,6 +355,9 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a PtrWeakKeyHashMap<K, V, S> {
     type Item = (K::Strong, &'a V);
     type IntoIter = Iter<'a, ByPtr<K>, V>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         (&self.0).into_iter()
     }
@@ -301,17 +367,22 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut PtrWeakKeyHashMap<K, V,
     type Item = (K::Strong, &'a mut V);
     type IntoIter = IterMut<'a, ByPtr<K>, V>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         (&mut self.0).into_iter()
     }
 }
 
 #[cfg(test)]
-mod test
-{
-    use crate::PtrWeakKeyHashMap;
-    use crate::weak_key_hash_map::Entry;
-    use std::rc::{Rc, Weak};
+mod test {
+    use crate::compat::{
+        eprintln,
+        rc::{Rc, Weak},
+        Vec,
+    };
+    use super::{Entry, PtrWeakKeyHashMap};
 
 //    fn show_me(weakmap: &PtrWeakKeyHashMap<Weak<u32>, f32>) {
 //        for (key, _) in weakmap {
diff --git a/src/ptr_weak_weak_hash_map.rs b/src/ptr_weak_weak_hash_map.rs
index e842cd2..fb49ae7 100644
--- a/src/ptr_weak_weak_hash_map.rs
+++ b/src/ptr_weak_weak_hash_map.rs
@@ -1,11 +1,7 @@
 //! A hash map where the keys and values are both held by weak pointers, and keys are compared by
 //! pointer.
 
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::BuildHasher;
-use std::iter::FromIterator;
-use std::ops::Deref;
+use crate::compat::*;
 
 use super::by_ptr::*;
 use super::traits::*;
@@ -18,11 +14,15 @@ impl <K: WeakElement, V: WeakElement> PtrWeakWeakHashMap<K, V, RandomState>
     where K::Strong: Deref
 {
     /// Creates an empty `PtrWeakWeakHashMap`.
+    ///
+    /// *O*(1) time
     pub fn new() -> Self {
         PtrWeakWeakHashMap(base::WeakWeakHashMap::new())
     }
 
     /// Creates an empty `PtrWeakWeakHashMap` with the given capacity.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity(capacity: usize) -> Self {
         PtrWeakWeakHashMap(base::WeakWeakHashMap::with_capacity(capacity))
     }
@@ -32,41 +32,57 @@ impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S
     where K::Strong: Deref
 {
     /// Creates an empty `PtrWeakWeakHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_hasher(hash_builder: S) -> Self {
         PtrWeakWeakHashMap(base::WeakWeakHashMap::with_hasher(hash_builder))
     }
 
     /// Creates an empty `PtrWeakWeakHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
         PtrWeakWeakHashMap(base::WeakWeakHashMap::with_capacity_and_hasher(capacity, hash_builder))
     }
 
     /// Returns a reference to the map's `BuildHasher`.
+    ///
+    /// *O*(1) time
     pub fn hasher(&self) -> &S {
         self.0.hasher()
     }
 
     /// Returns the number of elements the map can hold without reallocating.
+    ///
+    /// *O*(1) time
     pub fn capacity(&self) -> usize {
         self.0.capacity()
     }
 
     /// Removes all mappings whose keys have expired.
+    ///
+    /// *O*(*n*) time
     pub fn remove_expired(&mut self) {
         self.0.remove_expired()
     }
 
     /// Reserves room for additional elements.
+    ///
+    /// *O*(*n*) time
     pub fn reserve(&mut self, additional_capacity: usize) {
         self.0.reserve(additional_capacity)
     }
 
     /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+    ///
+    /// *O*(*n*) time
     pub fn shrink_to_fit(&mut self) {
         self.0.shrink_to_fit()
     }
 
     /// Returns an over-approximation of the number of elements.
+    ///
+    /// *O*(1) time
     pub fn len(&self) -> usize {
         self.0.len()
     }
@@ -75,6 +91,8 @@ impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S
     ///
     /// Note that this may return false even if all keys in the map have
     /// expired, if they haven't been collected yet.
+    ///
+    /// *O*(1) time
     pub fn is_empty(&self) -> bool {
         self.0.is_empty()
     }
@@ -82,37 +100,51 @@ impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S
     /// The proportion of buckets that are used.
     ///
     /// This is an over-approximation because of expired keys.
+    ///
+    /// *O*(1) time
     pub fn load_factor(&self) -> f32 {
         self.0.load_factor()
     }
 
     /// Gets the requested entry.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> {
         self.0.entry(key)
     }
 
     /// Removes all associations from the map.
+    ///
+    /// *O*(*n*) time
     pub fn clear(&mut self) {
         self.0.clear()
     }
 
     /// Returns a reference to the value corresponding to the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get(&self, key: &K::Strong) -> Option<V::Strong> {
         self.0.get(&(key.deref() as *const _))
     }
 
     /// Returns true if the map contains the specified key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn contains_key(&self, key: &K::Strong) -> bool {
         self.0.contains_key(&(key.deref() as *const _))
     }
 
     /// Unconditionally inserts the value, returning the old value if already present. Does not
     /// replace the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> {
         self.0.insert(key, value)
     }
 
     /// Removes the entry with the given key, if it exists, and returns the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove(&mut self, key: &K::Strong) -> Option<V::Strong> {
         self.0.remove(&(key.deref() as *const _))
     }
@@ -120,6 +152,8 @@ impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S
     /// Removes all mappings not satisfying the given predicate.
     ///
     /// Also removes any expired mappings.
+    ///
+    /// *O*(*n*) time
     pub fn retain<F>(&mut self, f: F)
         where F: FnMut(K::Strong, V::Strong) -> bool
     {
@@ -130,6 +164,10 @@ impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S
     ///
     /// In particular, all the keys of self must be in other and the values must compare true with
     /// value_equal.
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn submap_with<F, S1, V1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>, value_equal: F) -> bool
     where F: FnMut(V::Strong, V1::Strong) -> bool,
           V1: WeakElement,
@@ -139,6 +177,10 @@ impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S
     }
 
     /// Is self a submap of other?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool
         where V1: WeakElement,
               V::Strong: PartialEq<V1::Strong>,
@@ -148,6 +190,10 @@ impl <K: WeakElement, V: WeakElement, S: BuildHasher> PtrWeakWeakHashMap<K, V, S
     }
 
     /// Are the keys of self a subset of the keys of other?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool
         where V1: WeakElement,
               S1: BuildHasher
@@ -160,21 +206,29 @@ impl<K: WeakElement, V: WeakElement, S> PtrWeakWeakHashMap<K, V, S>
     where K::Strong: Deref
 {
     /// Gets an iterator over the keys and values.
+    ///
+    /// *O*(1) time
     pub fn iter(&self) -> Iter<ByPtr<K>, V> {
         self.0.iter()
     }
 
     /// Gets an iterator over the keys.
+    ///
+    /// *O*(1) time
     pub fn keys(&self) -> Keys<ByPtr<K>, V> {
         self.0.keys()
     }
 
     /// Gets an iterator over the values.
+    ///
+    /// *O*(1) time
     pub fn values(&self) -> Values<ByPtr<K>, V> {
         self.0.values()
     }
 
     /// Gets a draining iterator, which removes all the values but retains the storage.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     pub fn drain(&mut self) -> Drain<ByPtr<K>, V> {
         self.0.drain()
     }
@@ -245,6 +299,9 @@ impl<K: WeakElement, V: WeakElement, S> IntoIterator for PtrWeakWeakHashMap<K, V
     type Item = (K::Strong, V::Strong);
     type IntoIter = IntoIter<ByPtr<K>, V>;
 
+    /// Creates an owning iterator from `self`.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     fn into_iter(self) -> Self::IntoIter {
         self.0.into_iter()
     }
@@ -254,17 +311,22 @@ impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a PtrWeakWeakHash
     type Item = (K::Strong, V::Strong);
     type IntoIter = Iter<'a, ByPtr<K>, V>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         (&self.0).into_iter()
     }
 }
 
 #[cfg(test)]
-mod test
-{
-    use crate::PtrWeakWeakHashMap;
-    use crate::weak_weak_hash_map::Entry;
-    use std::rc::{Rc, Weak};
+mod test {
+    use crate::compat::{
+        eprintln,
+        rc::{Rc, Weak},
+        Vec,
+    };
+    use super::{Entry, PtrWeakWeakHashMap};
 
 //    fn show_me(weakmap: &PtrWeakWeakHashMap<Weak<u32>, Weak<f32>>) {
 //        for (key, _) in weakmap {
diff --git a/src/traits.rs b/src/traits.rs
index 440a6c9..878e5a3 100644
--- a/src/traits.rs
+++ b/src/traits.rs
@@ -7,8 +7,7 @@
 //! as a weak element, you need to implement `WeakElement` for your weak pointer type; to use it
 //! as a weak key, implement `WeakKey` as well.
 
-use std::hash::Hash;
-use std::{rc, sync};
+use crate::compat::*;
 
 /// Interface for elements that can be stored in weak hash tables.
 ///
@@ -70,6 +69,19 @@ pub trait WeakKey : WeakElement {
     /// strong pointer.
     fn with_key<F, R>(view: &Self::Strong, f: F) -> R
         where F: FnOnce(&Self::Key) -> R;
+
+    /// Hashes the key `view` into the given `Hasher`.
+    fn hash<H: Hasher>(view: &Self::Strong, h: &mut H) {
+        Self::with_key(view, |k| k.hash(h));
+    }
+
+    /// Returns whether the key `view` equals the given `key`.
+    fn equals<Q>(view: &Self::Strong, key: &Q) -> bool
+        where Q: ?Sized + Eq,
+              Self::Key: Borrow<Q>
+    {
+        Self::with_key(view, |k| k.borrow() == key)
+    }
 }
 
 impl<T: ?Sized> WeakElement for rc::Weak<T> {
@@ -94,7 +106,7 @@ impl<T: ?Sized + Eq + Hash> WeakKey for rc::Weak<T> {
     fn with_key<F, R>(view: &Self::Strong, f: F) -> R
         where F: FnOnce(&Self::Key) -> R
     {
-        f(&view)
+        f(view)
     }
 }
 
@@ -121,7 +133,7 @@ impl<T: ?Sized + Eq + Hash> WeakKey for sync::Weak<T>
     fn with_key<F, R>(view: &Self::Strong, f: F) -> R
         where F: FnOnce(&Self::Key) -> R
     {
-        f(&view)
+        f(view)
     }
 }
 
diff --git a/src/util.rs b/src/util.rs
index 3792ec7..9affd7f 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -1,3 +1,5 @@
+use crate::compat::*;
+
 pub fn new_boxed_option_slice<T>(size: usize) -> Box<[Option<T>]> {
     let mut vector = Vec::with_capacity(size);
     for _ in 0 .. size {
diff --git a/src/weak_hash_set.rs b/src/weak_hash_set.rs
index a3bc151..bbff3b8 100644
--- a/src/weak_hash_set.rs
+++ b/src/weak_hash_set.rs
@@ -1,10 +1,6 @@
 //! A hash set where the elements are held by weak pointers and compared by value.
 
-use std::borrow::Borrow;
-use std::collections::hash_map::RandomState;
-use std::fmt::{self, Debug};
-use std::hash::{BuildHasher, Hash};
-use std::iter::FromIterator;
+use crate::compat::*;
 
 use super::traits::*;
 use super::weak_key_hash_map as base;
@@ -13,11 +9,15 @@ pub use super::WeakHashSet;
 
 impl <T: WeakKey> WeakHashSet<T, RandomState> {
     /// Creates an empty `WeakHashSet`.
+    ///
+    /// *O*(1) time
     pub fn new() -> Self {
         WeakHashSet(base::WeakKeyHashMap::new())
     }
 
     /// Creates an empty `WeakHashSet` with the given capacity.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity(capacity: usize) -> Self {
         WeakHashSet(base::WeakKeyHashMap::with_capacity(capacity))
     }
@@ -25,41 +25,57 @@ impl <T: WeakKey> WeakHashSet<T, RandomState> {
 
 impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
     /// Creates an empty `WeakHashSet` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_hasher(hash_builder: S) -> Self {
         WeakHashSet(base::WeakKeyHashMap::with_hasher(hash_builder))
     }
 
     /// Creates an empty `WeakHashSet` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
         WeakHashSet(base::WeakKeyHashMap::with_capacity_and_hasher(capacity, hash_builder))
     }
 
     /// Returns a reference to the map's `BuildHasher`.
+    ///
+    /// *O*(1) time
     pub fn hasher(&self) -> &S {
         self.0.hasher()
     }
 
     /// Returns the number of elements the map can hold without reallocating.
+    ///
+    /// *O*(1) time
     pub fn capacity(&self) -> usize {
         self.0.capacity()
     }
 
     /// Removes all mappings whose keys have expired.
+    ///
+    /// *O*(*n*) time
     pub fn remove_expired(&mut self) {
         self.0.remove_expired()
     }
 
     /// Reserves room for additional elements.
+    ///
+    /// *O*(*n*) time
     pub fn reserve(&mut self, additional_capacity: usize) {
         self.0.reserve(additional_capacity)
     }
 
     /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+    ///
+    /// *O*(*n*) time
     pub fn shrink_to_fit(&mut self) {
         self.0.shrink_to_fit()
     }
 
     /// Returns an over-approximation of the number of elements.
+    ///
+    /// *O*(1) time
     pub fn len(&self) -> usize {
         self.0.len()
     }
@@ -68,6 +84,8 @@ impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
     ///
     /// Note that this may return false even if all keys in the set have
     /// expired, if they haven't been collected yet.
+    ///
+    /// *O*(1) time
     pub fn is_empty(&self) -> bool {
         self.0.is_empty()
     }
@@ -75,11 +93,15 @@ impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
     /// The proportion of buckets that are used.
     ///
     /// This is an over-approximation because of expired elements.
+    ///
+    /// *O*(1) time
     pub fn load_factor(&self) -> f32 {
         self.0.load_factor()
     }
 
     /// Removes all associations from the map.
+    ///
+    /// *O*(*n*) time
     pub fn clear(&mut self) {
         self.0.clear()
     }
@@ -87,6 +109,8 @@ impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
     // Non-ptr WeakHashSet should probably have `get` method.
 
     /// Returns true if the map contains the specified key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn contains<Q>(&self, key: &Q) -> bool
         where Q: ?Sized + Eq + Hash,
               T::Key: Borrow<Q>
@@ -112,6 +136,8 @@ impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
     ///
     /// assert!(Rc::ptr_eq( &a, &also_a ));
     /// ```
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get<Q>(&self, key: &Q) -> Option<T::Strong>
         where Q: ?Sized + Eq + Hash,
               T::Key: Borrow<Q>
@@ -121,11 +147,15 @@ impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
 
     /// Unconditionally inserts the value, returning the old value if already present. Does not
     /// replace the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(&mut self, key: T::Strong) -> bool {
         self.0.insert(key, ()).is_some()
     }
 
     /// Removes the entry with the given key, if it exists, and returns the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove<Q>(&mut self, key: &Q) -> bool
         where Q: ?Sized + Eq + Hash,
               T::Key: Borrow<Q>
@@ -136,6 +166,8 @@ impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
     /// Removes all mappings not satisfying the given predicate.
     ///
     /// Also removes any expired mappings.
+    ///
+    /// *O*(*n*) time
     pub fn retain<F>(&mut self, mut f: F)
         where F: FnMut(T::Strong) -> bool
     {
@@ -143,6 +175,10 @@ impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
     }
 
     /// Is self a subset of other?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_subset<S1>(&self, other: &WeakHashSet<T, S1>) -> bool
         where S1: BuildHasher
     {
@@ -197,11 +233,15 @@ impl<'a, T: WeakElement> Iterator for Drain<'a, T> {
 
 impl<T: WeakKey, S> WeakHashSet<T, S> {
     /// Gets an iterator over the keys and values.
+    ///
+    /// *O*(1) time
     pub fn iter(&self) -> Iter<T> {
         Iter(self.0.keys())
     }
 
     /// Gets a draining iterator, which removes all the values but retains the storage.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     pub fn drain(&mut self) -> Drain<T> {
         Drain(self.0.drain())
     }
@@ -255,6 +295,9 @@ impl<T: WeakKey, S> IntoIterator for WeakHashSet<T, S> {
     type Item = T::Strong;
     type IntoIter = IntoIter<T>;
 
+    /// Creates an owning iterator from `self`.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     fn into_iter(self) -> Self::IntoIter {
         IntoIter(self.0.into_iter())
     }
@@ -264,6 +307,9 @@ impl<'a, T: WeakKey, S> IntoIterator for &'a WeakHashSet<T, S> {
     type Item = T::Strong;
     type IntoIter = Iter<'a, T>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         Iter(self.0.keys())
     }
diff --git a/src/weak_key_hash_map.rs b/src/weak_key_hash_map.rs
index 91bee2a..7dcb8c4 100644
--- a/src/weak_key_hash_map.rs
+++ b/src/weak_key_hash_map.rs
@@ -1,12 +1,5 @@
 //! A hash map where the keys are held by weak pointers and compared by key value.
 
-use std::borrow::Borrow;
-use std::cmp::max;
-use std::collections::hash_map::RandomState;
-use std::hash::{BuildHasher, Hash, Hasher};
-use std::fmt::{self, Debug, Formatter};
-use std::mem;
-
 use super::*;
 use super::size_policy::*;
 use super::traits::*;
@@ -36,7 +29,7 @@ struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> {
 /// An iterator over the keys and values of the weak hash map.
 #[derive(Clone, Debug)]
 pub struct Iter<'a, K: 'a, V: 'a> {
-    base: ::std::slice::Iter<'a, Bucket<K, V>>,
+    base: slice::Iter<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -44,7 +37,7 @@ impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> {
     type Item = (K::Strong, &'a V);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
+        for bucket in &mut self.base {
             if let Some((ref weak_ptr, ref value, _)) = *bucket {
                 self.size -= 1;
                 if let Some(strong_ptr) = weak_ptr.view() {
@@ -64,7 +57,7 @@ impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> {
 #[derive(Debug)]
 /// An iterator over the keys and mutable values of the weak hash map.
 pub struct IterMut<'a, K: 'a, V: 'a> {
-    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    base: slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -72,7 +65,7 @@ impl<'a, K: WeakElement, V> Iterator for IterMut<'a, K, V> {
     type Item = (K::Strong, &'a mut V);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
+        for bucket in &mut self.base {
             if let Some((ref weak_ptr, ref mut value, _)) = *bucket {
                 self.size -= 1;
                 if let Some(strong_ptr) = weak_ptr.view() {
@@ -140,7 +133,7 @@ impl<'a, K: WeakElement, V> Iterator for ValuesMut<'a, K, V> {
 #[derive(Debug)]
 /// An iterator that consumes the values of a weak hash map, leaving it empty.
 pub struct Drain<'a, K: 'a, V: 'a> {
-    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    base: slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -148,7 +141,7 @@ impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> {
     type Item = (K::Strong, V);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
+        for bucket in &mut self.base {
             if let Some((weak_ptr, value, _)) = bucket.take() {
                 self.size -= 1;
                 if let Some(strong_ptr) = weak_ptr.view() {
@@ -167,7 +160,7 @@ impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> {
 
 impl<'a, K, V> Drop for Drain<'a, K, V> {
     fn drop(&mut self) {
-        while let Some(option) = self.base.next() {
+        for option in &mut self.base {
             *option = None;
         }
     }
@@ -175,7 +168,7 @@ impl<'a, K, V> Drop for Drain<'a, K, V> {
 
 /// An iterator that consumes the values of a weak hash map, leaving it empty.
 pub struct IntoIter<K, V> {
-    base: ::std::vec::IntoIter<Bucket<K, V>>,
+    base: vec::IntoIter<Bucket<K, V>>,
     size: usize,
 }
 
@@ -183,12 +176,10 @@ impl<K: WeakElement, V> Iterator for IntoIter<K, V> {
     type Item = (K::Strong, V);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
-            if let Some((weak_ptr, value, _)) = bucket {
-                self.size -= 1;
-                if let Some(strong_ptr) = weak_ptr.view() {
-                    return Some((strong_ptr, value));
-                }
+        for (weak_ptr, value, _) in (&mut self.base).flatten() {
+            self.size -= 1;
+            if let Some(strong_ptr) = weak_ptr.view() {
+                return Some((strong_ptr, value));
             }
         }
 
@@ -203,11 +194,15 @@ impl<K: WeakElement, V> Iterator for IntoIter<K, V> {
 impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState>
 {
     /// Creates an empty `WeakKeyHashMap`.
+    ///
+    /// *O*(1) time
     pub fn new() -> Self {
         Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
     }
 
     /// Creates an empty `WeakKeyHashMap` with the given capacity.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity(capacity: usize) -> Self {
         Self::with_capacity_and_hasher(capacity, Default::default())
     }
@@ -216,11 +211,15 @@ impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState>
 impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
 {
     /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_hasher(hash_builder: S) -> Self {
         Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
     }
 
     /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
         WeakKeyHashMap {
             hash_builder,
@@ -232,11 +231,15 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Returns a reference to the map's `BuildHasher`.
+    ///
+    /// *O*(1) time
     pub fn hasher(&self) -> &S {
         &self.hash_builder
     }
 
     /// Returns the number of elements the map can hold without reallocating.
+    ///
+    /// *O*(1) time
     pub fn capacity(&self) -> usize {
         self.inner.capacity()
     }
@@ -259,17 +262,23 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Removes all mappings whose keys have expired.
+    ///
+    /// *O*(*n*) time
     pub fn remove_expired(&mut self) {
         self.retain(|_, _| true)
     }
 
     /// Reserves room for additional elements.
+    ///
+    /// *O*(*n*) time
     pub fn reserve(&mut self, additional_capacity: usize) {
         let new_capacity = additional_capacity + self.capacity();
         self.resize(new_capacity);
     }
 
     /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+    ///
+    /// *O*(*n*) time
     pub fn shrink_to_fit(&mut self) {
         self.remove_expired();
         let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
@@ -277,6 +286,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Returns an over-approximation of the number of elements.
+    ///
+    /// *O*(1) time
     pub fn len(&self) -> usize {
         self.inner.len
     }
@@ -285,6 +296,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     ///
     /// Note that this may return false even if all keys in the map have
     /// expired, if they haven't been collected yet.
+    ///
+    /// *O*(1) time
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
@@ -292,6 +305,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     /// The proportion of buckets that are used.
     ///
     /// This is an over-approximation because of expired keys.
+    ///
+    /// *O*(1) time
     pub fn load_factor(&self) -> f32 {
         (self.len() as f32 + 1.0) / self.capacity() as f32
     }
@@ -311,6 +326,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Gets the requested entry.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
         self.maybe_adjust_size();
         self.entry_no_grow(key)
@@ -318,7 +335,7 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
 
     fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
         let mut inner = {
-            let hash_code = K::with_key(&key, |k| self.hash(k));
+            let hash_code = self.hash(&key, K::hash);
             InnerEntry {
                 pos:        self.which_bucket(hash_code),
                 map:        &mut self.inner,
@@ -347,6 +364,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Removes all associations from the map.
+    ///
+    /// *O*(*n*) time
     pub fn clear(&mut self) {
         self.drain();
     }
@@ -357,14 +376,14 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     {
         if self.capacity() == 0 { return None; }
 
-        let hash_code = self.hash(key);
+        let hash_code = self.hash(key, Q::hash);
         let mut pos = self.which_bucket(hash_code);
 
         for dist in 0 .. self.capacity() {
             if let Some((ref weak_key, _, bucket_hash_code)) = self.inner.buckets[pos] {
                 if bucket_hash_code == hash_code {
                     if let Some(bucket_key) = weak_key.view() {
-                        if K::with_key(&bucket_key, |k| k.borrow() == key) {
+                        if K::equals(&bucket_key, key) {
                             return Some((pos, bucket_key, bucket_hash_code));
                         }
                     }
@@ -386,6 +405,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Returns a reference to the value corresponding to the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get<Q>(&self, key: &Q) -> Option<&V>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -395,6 +416,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Returns true if the map contains the specified key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn contains_key<Q>(&self, key: &Q) -> bool
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -403,6 +426,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Returns a strong reference to the key, if found.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -411,6 +436,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Returns a pair of a strong reference to the key, and a reference to the value, if present.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, &V)>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -420,6 +447,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Returns a mutable reference to the value corresponding to the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -430,6 +459,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
 
     /// Returns a pair of a strong reference to the key, and a mutable reference to the value,
     /// if present.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get_both_mut<Q>(&mut self, key: &Q) -> Option<(K::Strong, &mut V)>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -441,6 +472,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     /// Unconditionally inserts the value, returning the old value if already present.
     ///
     /// Unlike `std::collections::HashMap`, this replaced the key even if occupied.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
         match self.entry(key) {
             Entry::Occupied(mut occupied) => {
@@ -454,6 +487,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Removes the entry with the given key, if it exists, and returns the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -471,6 +506,8 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     /// Removes all mappings not satisfying the given predicate.
     ///
     /// Also removes any expired mappings.
+    ///
+    /// *O*(*n*) time
     pub fn retain<F>(&mut self, mut f: F)
         where F: FnMut(K::Strong, &mut V) -> bool
     {
@@ -490,18 +527,24 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
         }
     }
 
-    /// Is this map a submap of the other, using the given value comparison.
+    /// Is this map a submap of the other under the given value comparison `cmp`?
     ///
-    /// In particular, all the keys of `self` must be in `other` and the values must compare
-    /// `true` with `value_equal`.
+    /// In particular, for every key `k` of `self`,
+    ///
+    ///  - `k` must also be a key of `other` and
+    ///  - `cmp(self[k], other[k])` must hold.
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>,
-                                     mut value_equal: F) -> bool
+                                     mut cmp: F) -> bool
         where F: FnMut(&V, &V1) -> bool,
               S1: BuildHasher
     {
         for (key, value1) in self {
             if let Some(value2) = K::with_key(&key, |k| other.get(k)) {
-                if !value_equal(value1, value2) {
+                if !cmp(value1, value2) {
                     return false;
                 }
             } else {
@@ -513,6 +556,10 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Is `self` a submap of `other`?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
         where V: PartialEq<V1>,
               S1: BuildHasher
@@ -521,18 +568,21 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     }
 
     /// Are the keys of `self` a subset of the keys of `other`?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn domain_is_subset<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
         where S1: BuildHasher
     {
         self.is_submap_with(other, |_, _| true)
     }
 
-    fn hash<Q>(&self, key: &Q) -> HashCode
-        where Q: ?Sized + Hash,
-              K::Key: Borrow<Q>
+    fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode
+        where H: FnOnce(Q, &mut S::Hasher)
     {
-        let mut hasher = self.hash_builder.build_hasher();
-        key.hash(&mut hasher);
+        let hasher = &mut self.hash_builder.build_hasher();
+        hash(key, hasher);
         HashCode(hasher.finish())
     }
 }
@@ -556,7 +606,7 @@ impl<K: WeakKey, V, S: BuildHasher + Default> Default for WeakKeyHashMap<K, V, S
     }
 }
 
-impl<'a, K, V, S, Q> ::std::ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           K::Key: Borrow<Q>,
           S: BuildHasher,
@@ -569,7 +619,7 @@ impl<'a, K, V, S, Q> ::std::ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
     }
 }
 
-impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           K::Key: Borrow<Q>,
           S: BuildHasher,
@@ -580,7 +630,7 @@ impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
     }
 }
 
-impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           S: BuildHasher + Default
 {
@@ -591,7 +641,7 @@ impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V,
     }
 }
 
-impl<K, V, S> ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           S: BuildHasher
 {
@@ -602,7 +652,7 @@ impl<K, V, S> ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
     }
 }
 
-impl<'a, K, V, S> ::std::iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
     where K: 'a + WeakKey,
           K::Strong: Clone,
           V: 'a + Clone,
@@ -628,7 +678,7 @@ impl<'a, K: WeakKey, V> InnerEntry<'a, K, V> {
             Some(bucket) => {
                 if bucket.2 == self.hash_code {
                     if let Some(key) = bucket.0.view() {
-                        if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
+                        if K::with_key(&self.key, |k| K::equals(&key, k)) {
                             return BucketStatus::MatchesKey;
                         }
                     }
@@ -647,6 +697,8 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> {
     /// Ensures a value is in the entry by inserting a default value
     /// if empty, and returns a mutable reference to the value in the
     /// entry.
+    ///
+    /// *O*(1) time
     pub fn or_insert(self, default: V) -> &'a mut V {
         self.or_insert_with(|| default)
     }
@@ -654,6 +706,8 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> {
     /// Ensures a value is in the entry by inserting the result of the
     /// default function if empty, and returns a mutable reference to
     /// the value in the entry.
+    ///
+    /// *O*(1) time
     pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
         match self {
             Entry::Occupied(occupied) => occupied.into_mut(),
@@ -662,6 +716,8 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> {
     }
 
     /// Returns a reference to this entry's key.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K::Strong {
         match *self {
             Entry::Occupied(ref occupied) => occupied.key(),
@@ -672,11 +728,15 @@ impl<'a, K: WeakKey, V> Entry<'a, K, V> {
 
 impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
     /// Gets a reference to the key held by the entry.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K::Strong {
         &self.0.key
     }
 
     /// Takes ownership of the key and value from the map.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove_entry(self) -> (K::Strong, V) {
         let (_, value, _) = self.0.map.buckets[self.0.pos].take().unwrap();
         self.0.map.remove_index(self.0.pos);
@@ -684,21 +744,29 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
     }
 
     /// Gets a reference to the value in the entry.
+    ///
+    /// *O*(1) time
     pub fn get(&self) -> &V {
         &self.0.map.buckets[self.0.pos].as_ref().unwrap().1
     }
 
     /// Gets a mutable reference to the value in the entry.
+    ///
+    /// *O*(1) time
     pub fn get_mut(&mut self) -> &mut V {
         &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
     }
 
     /// Turns the entry into a mutable reference to the value borrowed from the map.
+    ///
+    /// *O*(1) time
     pub fn into_mut(self) -> &'a mut V {
         &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
     }
 
     /// Replaces the value in the entry with the given value.
+    ///
+    /// *O*(1) time
     pub fn insert(&mut self, mut value: V) -> V {
         self.0.map.buckets[self.0.pos].as_mut().unwrap().0 = K::new(&self.0.key);
         mem::swap(self.get_mut(), &mut value);
@@ -706,6 +774,8 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
     }
 
     /// Removes the entry, returning the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove(self) -> V {
         self.remove_entry().1
     }
@@ -714,17 +784,23 @@ impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
 impl<'a, K: WeakKey, V> VacantEntry<'a, K, V> {
     /// Gets a reference to the key that would be used when inserting a
     /// value through the `VacantEntry`.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K::Strong {
         &self.0.key
     }
 
     /// Returns ownership of the key.
+    ///
+    /// *O*(1) time
     pub fn into_key(self) -> K::Strong {
         self.0.key
     }
 
     /// Inserts the key and value into the map and return a mutable
     /// reference to the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(self, value: V) -> &'a mut V {
         let old_bucket = mem::replace(
             &mut self.0.map.buckets[self.0.pos],
@@ -934,6 +1010,9 @@ impl<K: WeakElement, V, S> IntoIterator for WeakKeyHashMap<K, V, S> {
     type Item = (K::Strong, V);
     type IntoIter = IntoIter<K, V>;
 
+    /// Creates an owning iterator from `self`.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     fn into_iter(self) -> Self::IntoIter {
         IntoIter {
             size: self.inner.len,
@@ -946,6 +1025,9 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a WeakKeyHashMap<K, V, S> {
     type Item = (K::Strong, &'a V);
     type IntoIter = Iter<'a, K, V>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         Iter {
             base: self.inner.buckets.iter(),
@@ -958,6 +1040,9 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap<K, V, S>
     type Item = (K::Strong, &'a mut V);
     type IntoIter = IterMut<'a, K, V>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         IterMut {
             base: self.inner.buckets.iter_mut(),
@@ -968,31 +1053,43 @@ impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut WeakKeyHashMap<K, V, S>
 
 impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
     /// Gets an iterator over the keys and values.
+    ///
+    /// *O*(1) time
     pub fn iter(&self) -> Iter<K, V> {
         self.into_iter()
     }
 
     /// Gets an iterator over the keys.
+    ///
+    /// *O*(1) time
     pub fn keys(&self) -> Keys<K, V> {
         Keys(self.iter())
     }
 
     /// Gets an iterator over the values.
+    ///
+    /// *O*(1) time
     pub fn values(&self) -> Values<K, V> {
         Values(self.iter())
     }
 
     /// Gets an iterator over the keys and mutable values.
+    ///
+    /// *O*(1) time
     pub fn iter_mut(&mut self) -> IterMut<K, V> {
         self.into_iter()
     }
 
     /// Gets an iterator over the mutable values.
+    ///
+    /// *O*(1) time
     pub fn values_mut(&mut self) -> ValuesMut<K, V> {
         ValuesMut(self.iter_mut())
     }
 
     /// Gets a draining iterator, which removes all the values but retains the storage.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     pub fn drain(&mut self) -> Drain<K, V> {
         let old_len = self.inner.len;
         self.inner.len = 0;
@@ -1004,8 +1101,13 @@ impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
 }
 
 #[cfg(test)]
-mod tests {
-    use std::rc::{Rc, Weak};
+mod test {
+    use crate::compat::{
+        eprintln,
+        rc::{Rc, Weak},
+        String,
+        Vec,
+    };
     use super::{Entry, WeakKeyHashMap};
 
     #[test]
@@ -1014,7 +1116,7 @@ mod tests {
         assert_eq!( map.len(), 0 );
         assert!( !map.contains_key("five") );
 
-        let five: Rc<str> = Rc::from("five".to_string());
+        let five: Rc<str> = Rc::from(String::from("five"));
         map.insert(five.clone(), 5);
 
         assert_eq!( map.len(), 1 );
diff --git a/src/weak_value_hash_map.rs b/src/weak_value_hash_map.rs
index 8b60a17..7177e41 100644
--- a/src/weak_value_hash_map.rs
+++ b/src/weak_value_hash_map.rs
@@ -1,12 +1,5 @@
 //! A hash map where the values are held by weak pointers.
 
-use std::borrow::Borrow;
-use std::cmp::max;
-use std::collections::hash_map::RandomState;
-use std::hash::{BuildHasher, Hash, Hasher};
-use std::fmt::{self, Debug, Formatter};
-use std::mem;
-
 use super::*;
 use super::size_policy::*;
 use super::traits::*;
@@ -41,7 +34,7 @@ struct InnerEntry<'a, K: 'a, V: 'a + WeakElement> {
 /// An iterator over the keys and values of the weak hash map.
 #[derive(Clone, Debug)]
 pub struct Iter<'a, K: 'a, V: 'a> {
-    base: ::std::slice::Iter<'a, Bucket<K, V>>,
+    base: slice::Iter<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -49,7 +42,7 @@ impl<'a, K, V: WeakElement> Iterator for Iter<'a, K, V> {
     type Item = (&'a K, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
+        for bucket in &mut self.base {
             if let Some((ref key, ref weak_value, _)) = *bucket {
                 self.size -= 1;
                 if let Some(value) = weak_value.view() {
@@ -101,7 +94,7 @@ impl<'a, K, V: WeakElement> Iterator for Values<'a, K, V> {
 #[derive(Debug)]
 /// An iterator that consumes the values of a weak hash map, leaving it empty.
 pub struct Drain<'a, K: 'a, V: 'a> {
-    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    base: slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -109,7 +102,7 @@ impl<'a, K, V: WeakElement> Iterator for Drain<'a, K, V> {
     type Item = (K, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
+        for bucket in &mut self.base {
             if let Some((key, weak_value, _)) = bucket.take() {
                 self.size -= 1;
                 if let Some(value) = weak_value.view() {
@@ -128,7 +121,7 @@ impl<'a, K, V: WeakElement> Iterator for Drain<'a, K, V> {
 
 impl<'a, K, V> Drop for Drain<'a, K, V> {
     fn drop(&mut self) {
-        while let Some(option) = self.base.next() {
+        for option in &mut self.base {
             *option = None;
         }
     }
@@ -136,7 +129,7 @@ impl<'a, K, V> Drop for Drain<'a, K, V> {
 
 /// An iterator that consumes the values of a weak hash map, leaving it empty.
 pub struct IntoIter<K, V> {
-    base: ::std::vec::IntoIter<Bucket<K, V>>,
+    base: vec::IntoIter<Bucket<K, V>>,
     size: usize,
 }
 
@@ -144,12 +137,10 @@ impl<K, V: WeakElement> Iterator for IntoIter<K, V> {
     type Item = (K, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
-            if let Some((key, weak_value, _)) = bucket {
-                self.size -= 1;
-                if let Some(value) = weak_value.view() {
-                    return Some((key, value));
-                }
+        for (key, weak_value, _) in (&mut self.base).flatten() {
+            self.size -= 1;
+            if let Some(value) = weak_value.view() {
+                return Some((key, value));
             }
         }
 
@@ -164,11 +155,15 @@ impl<K, V: WeakElement> Iterator for IntoIter<K, V> {
 impl<K: Eq + Hash, V: WeakElement> WeakValueHashMap<K, V, RandomState>
 {
     /// Creates an empty `WeakValueHashMap`.
+    ///
+    /// *O*(1) time
     pub fn new() -> Self {
         Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
     }
 
     /// Creates an empty `WeakValueHashMap` with the given capacity.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity(capacity: usize) -> Self {
         Self::with_capacity_and_hasher(capacity, Default::default())
     }
@@ -177,11 +172,15 @@ impl<K: Eq + Hash, V: WeakElement> WeakValueHashMap<K, V, RandomState>
 impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
 {
     /// Creates an empty `WeakValueHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_hasher(hash_builder: S) -> Self {
         Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
     }
 
     /// Creates an empty `WeakValueHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
         WeakValueHashMap {
             hash_builder,
@@ -193,11 +192,15 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Returns a reference to the map's `BuildHasher`.
+    ///
+    /// *O*(1) time
     pub fn hasher(&self) -> &S {
         &self.hash_builder
     }
 
     /// Returns the number of elements the map can hold without reallocating.
+    ///
+    /// *O*(1) time
     pub fn capacity(&self) -> usize {
         self.inner.capacity()
     }
@@ -220,17 +223,23 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Removes all mappings whose keys have expired.
+    ///
+    /// *O*(*n*) time
     pub fn remove_expired(&mut self) {
         self.retain(|_, _| true)
     }
 
     /// Reserves room for additional elements.
+    ///
+    /// *O*(*n*) time
     pub fn reserve(&mut self, additional_capacity: usize) {
         let new_capacity = additional_capacity + self.capacity();
         self.resize(new_capacity);
     }
 
     /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+    ///
+    /// *O*(*n*) time
     pub fn shrink_to_fit(&mut self) {
         self.remove_expired();
         let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
@@ -238,6 +247,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Returns an over-approximation of the number of elements.
+    ///
+    /// *O*(1) time
     pub fn len(&self) -> usize {
         self.inner.len
     }
@@ -246,6 +257,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     ///
     /// Note that this may return false even if all keys in the map have
     /// expired, if they haven't been collected yet.
+    ///
+    /// *O*(1) time
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
@@ -253,6 +266,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     /// The proportion of buckets that are used.
     ///
     /// This is an over-approximation because of expired keys.
+    ///
+    /// *O*(1) time
     pub fn load_factor(&self) -> f32 {
         (self.len() as f32 + 1.0) / self.capacity() as f32
     }
@@ -272,6 +287,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Gets the requested entry.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn entry(&mut self, key: K) -> Entry<K, V> {
         self.maybe_adjust_size();
         self.entry_no_grow(key)
@@ -309,6 +326,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Removes all associations from the map.
+    ///
+    /// *O*(*n*) time
     pub fn clear(&mut self) {
         self.drain();
     }
@@ -348,6 +367,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Returns a reference to the value corresponding to the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get<Q>(&self, key: &Q) -> Option<V::Strong>
         where Q: ?Sized + Hash + Eq,
               K: Borrow<Q>
@@ -356,6 +377,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Returns true if the map contains the specified key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn contains_key<Q>(&self, key: &Q) -> bool
         where Q: ?Sized + Hash + Eq,
               K: Borrow<Q>
@@ -366,6 +389,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     /// Unconditionally inserts the value, returning the old value if already present.
     ///
     /// Like `std::collections::HashMap`, this does not replace the key if occupied.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(&mut self, key: K, value: V::Strong) -> Option<V::Strong> {
         match self.entry(key) {
             Entry::Occupied(mut occupied) => {
@@ -379,6 +404,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Removes the entry with the given key, if it exists, and returns the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong>
         where Q: ?Sized + Hash + Eq,
               K: Borrow<Q>
@@ -394,6 +421,8 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     /// Removes all mappings not satisfying the given predicate.
     ///
     /// Also removes any expired mappings.
+    ///
+    /// *O*(*n*) time
     pub fn retain<F>(&mut self, mut f: F)
         where F: FnMut(&K, V::Strong) -> bool
     {
@@ -417,6 +446,10 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     ///
     /// In particular, all the keys of `self` must be in `other` and the values must compare
     /// `true` with `value_equal`.
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap_with<F, S1, V1>(&self, other: &WeakValueHashMap<K, V1, S1>,
                                      mut value_equal: F) -> bool
         where V1: WeakElement,
@@ -437,6 +470,10 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Is `self` a submap of `other`?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool
         where V1: WeakElement,
               V::Strong: PartialEq<V1::Strong>,
@@ -446,6 +483,10 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
     }
 
     /// Are the keys of `self` a subset of the keys of `other`?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn domain_is_subset<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool
         where V1: WeakElement,
               S1: BuildHasher
@@ -486,7 +527,7 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher + Default> Default for WeakVal
     }
 }
 
-impl<K, V, S> ::std::iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S>
+impl<K, V, S> iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S>
     where K: Eq + Hash,
           V: WeakElement,
           S: BuildHasher + Default
@@ -554,12 +595,16 @@ impl<'a, K: Eq + Hash, V: WeakElement> InnerEntry<'a, K, V> {
 impl<'a, K, V: WeakElement> Entry<'a, K, V> {
     /// Ensures a value is in the entry by inserting a default value
     /// if empty.
+    ///
+    /// *O*(1) time
     pub fn or_insert(self, default: V::Strong) -> V::Strong {
         self.or_insert_with(|| default)
     }
 
     /// Ensures a value is in the entry by inserting the result of the
     /// default function if empty.
+    ///
+    /// *O*(1) time
     pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong {
         match self {
             Entry::Occupied(occupied) => occupied.get_strong(),
@@ -568,6 +613,8 @@ impl<'a, K, V: WeakElement> Entry<'a, K, V> {
     }
 
     /// Returns a reference to this entry's key.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K {
         match *self {
             Entry::Occupied(ref occupied) => occupied.key(),
@@ -578,11 +625,15 @@ impl<'a, K, V: WeakElement> Entry<'a, K, V> {
 
 impl<'a, K, V: WeakElement> OccupiedEntry<'a, K, V> {
     /// Gets a reference to the key held by the entry.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K {
         &self.inner.key
     }
 
     /// Takes ownership of the key and value from the map.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove_entry(self) -> (K, V::Strong) {
         let (key, w_value, _) = self.inner.map.buckets[self.inner.pos].take().unwrap();
         let value = w_value.view().unwrap();
@@ -591,22 +642,30 @@ impl<'a, K, V: WeakElement> OccupiedEntry<'a, K, V> {
     }
 
     /// Gets a reference to the value in the entry.
+    ///
+    /// *O*(1) time
     pub fn get(&self) -> &V::Strong {
         &self.value
     }
 
     /// Gets a copy of the strong value reference stored in the entry.
+    ///
+    /// *O*(1) time
     pub fn get_strong(&self) -> V::Strong {
         V::clone(&self.value)
     }
 
     /// Replaces the value in the entry with the given value, returning the old value.
+    ///
+    /// *O*(1) time
     pub fn insert(&mut self, value: V::Strong) -> V::Strong {
         self.inner.map.buckets[self.inner.pos].as_mut().unwrap().1 = V::new(&value);
         mem::replace(&mut self.value, value)
     }
 
     /// Removes the entry, returning the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove(self) -> V::Strong {
         self.remove_entry().1
     }
@@ -615,16 +674,22 @@ impl<'a, K, V: WeakElement> OccupiedEntry<'a, K, V> {
 impl<'a, K, V: WeakElement> VacantEntry<'a, K, V> {
     /// Gets a reference to the key that would be used when inserting a
     /// value through the `VacantEntry`.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K {
         &self.inner.key
     }
 
     /// Returns ownership of the key.
+    ///
+    /// *O*(1) time
     pub fn into_key(self) -> K {
         self.inner.key
     }
 
     /// Inserts the value into the map, returning the same value.
+    ///
+    /// *O*(1) time
     pub fn insert(self, value: V::Strong) -> V::Strong {
         let InnerEntry { map, key, hash_code, pos } = self.inner;
 
@@ -836,6 +901,9 @@ impl<K, V: WeakElement, S> IntoIterator for WeakValueHashMap<K, V, S> {
     type Item = (K, V::Strong);
     type IntoIter = IntoIter<K, V>;
 
+    /// Creates an owning iterator from `self`.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     fn into_iter(self) -> Self::IntoIter {
         IntoIter {
             size: self.inner.len,
@@ -848,6 +916,9 @@ impl<'a, K, V: WeakElement, S> IntoIterator for &'a WeakValueHashMap<K, V, S> {
     type Item = (&'a K, V::Strong);
     type IntoIter = Iter<'a, K, V>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         Iter {
             base: self.inner.buckets.iter(),
@@ -858,21 +929,29 @@ impl<'a, K, V: WeakElement, S> IntoIterator for &'a WeakValueHashMap<K, V, S> {
 
 impl<K, V: WeakElement, S> WeakValueHashMap<K, V, S> {
     /// Gets an iterator over the keys and values.
+    ///
+    /// *O*(1) time
     pub fn iter(&self) -> Iter<K, V> {
         self.into_iter()
     }
 
     /// Gets an iterator over the keys.
+    ///
+    /// *O*(1) time
     pub fn keys(&self) -> Keys<K, V> {
         Keys(self.iter())
     }
 
     /// Gets an iterator over the values.
+    ///
+    /// *O*(1) time
     pub fn values(&self) -> Values<K, V> {
         Values(self.iter())
     }
 
     /// Gets a draining iterator, which removes all the values but retains the storage.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     pub fn drain(&mut self) -> Drain<K, V> {
         let old_len = self.inner.len;
         self.inner.len = 0;
diff --git a/src/weak_weak_hash_map.rs b/src/weak_weak_hash_map.rs
index 0ed89f6..801bc64 100644
--- a/src/weak_weak_hash_map.rs
+++ b/src/weak_weak_hash_map.rs
@@ -1,13 +1,6 @@
 //! A hash map where the keys and values are both held by weak pointers, and keys are compared by
 //! value.
 
-use std::borrow::Borrow;
-use std::cmp::max;
-use std::collections::hash_map::RandomState;
-use std::hash::{BuildHasher, Hash, Hasher};
-use std::fmt::{self, Debug, Formatter};
-use std::mem;
-
 use super::*;
 use super::size_policy::*;
 use super::traits::*;
@@ -42,7 +35,7 @@ struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> {
 /// An iterator over the keys and values of the weak hash map.
 #[derive(Clone, Debug)]
 pub struct Iter<'a, K: 'a, V: 'a> {
-    base: ::std::slice::Iter<'a, Bucket<K, V>>,
+    base: slice::Iter<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -50,7 +43,7 @@ impl<'a, K: WeakElement, V: WeakElement> Iterator for Iter<'a, K, V> {
     type Item = (K::Strong, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
+        for bucket in &mut self.base {
             if let Some((ref weak_key, ref weak_value, _)) = *bucket {
                 self.size -= 1;
                 if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
@@ -102,7 +95,7 @@ impl<'a, K: WeakElement, V: WeakElement> Iterator for Values<'a, K, V> {
 #[derive(Debug)]
 /// An iterator that consumes the values of a weak hash map, leaving it empty.
 pub struct Drain<'a, K: 'a, V: 'a> {
-    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    base: slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -110,7 +103,7 @@ impl<'a, K: WeakElement, V: WeakElement> Iterator for Drain<'a, K, V> {
     type Item = (K::Strong, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
+        for bucket in &mut self.base {
             if let Some((weak_key, weak_value, _)) = bucket.take() {
                 self.size -= 1;
                 if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
@@ -129,7 +122,7 @@ impl<'a, K: WeakElement, V: WeakElement> Iterator for Drain<'a, K, V> {
 
 impl<'a, K, V> Drop for Drain<'a, K, V> {
     fn drop(&mut self) {
-        while let Some(option) = self.base.next() {
+        for option in &mut self.base {
             *option = None;
         }
     }
@@ -137,7 +130,7 @@ impl<'a, K, V> Drop for Drain<'a, K, V> {
 
 /// An iterator that consumes the values of a weak hash map, leaving it empty.
 pub struct IntoIter<K, V> {
-    base: ::std::vec::IntoIter<Bucket<K, V>>,
+    base: vec::IntoIter<Bucket<K, V>>,
     size: usize,
 }
 
@@ -145,12 +138,10 @@ impl<K: WeakElement, V: WeakElement> Iterator for IntoIter<K, V> {
     type Item = (K::Strong, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        while let Some(bucket) = self.base.next() {
-            if let Some((weak_key, weak_value, _)) = bucket {
-                self.size -= 1;
-                if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
-                    return Some((key, value));
-                }
+        for (weak_key, weak_value, _) in (&mut self.base).flatten() {
+            self.size -= 1;
+            if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
+                return Some((key, value));
             }
         }
 
@@ -165,11 +156,15 @@ impl<K: WeakElement, V: WeakElement> Iterator for IntoIter<K, V> {
 impl<K: WeakKey, V: WeakElement> WeakWeakHashMap<K, V, RandomState>
 {
     /// Creates an empty `WeakWeakHashMap`.
+    ///
+    /// *O*(1) time
     pub fn new() -> Self {
         Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
     }
 
     /// Creates an empty `WeakWeakHashMap` with the given capacity.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity(capacity: usize) -> Self {
         Self::with_capacity_and_hasher(capacity, Default::default())
     }
@@ -177,11 +172,15 @@ impl<K: WeakKey, V: WeakElement> WeakWeakHashMap<K, V, RandomState>
 
 impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     /// Creates an empty `WeakWeakHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_hasher(hash_builder: S) -> Self {
         Self::with_capacity_and_hasher(DEFAULT_INITIAL_CAPACITY, hash_builder)
     }
 
     /// Creates an empty `WeakWeakHashMap` with the given capacity and hasher.
+    ///
+    /// *O*(*n*) time
     pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
         WeakWeakHashMap {
             hash_builder,
@@ -193,11 +192,15 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Returns a reference to the map's `BuildHasher`.
+    ///
+    /// *O*(1) time
     pub fn hasher(&self) -> &S {
         &self.hash_builder
     }
 
     /// Returns the number of elements the map can hold without reallocating.
+    ///
+    /// *O*(1) time
     pub fn capacity(&self) -> usize {
         self.inner.capacity()
     }
@@ -220,17 +223,23 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Removes all mappings whose keys have expired.
+    ///
+    /// *O*(*n*) time
     pub fn remove_expired(&mut self) {
         self.retain(|_, _| true)
     }
 
     /// Reserves room for additional elements.
+    ///
+    /// *O*(*n*) time
     pub fn reserve(&mut self, additional_capacity: usize) {
         let new_capacity = additional_capacity + self.capacity();
         self.resize(new_capacity);
     }
 
     /// Shrinks the capacity to the minimum allowed to hold the current number of elements.
+    ///
+    /// *O*(*n*) time
     pub fn shrink_to_fit(&mut self) {
         self.remove_expired();
         let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
@@ -238,6 +247,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Returns an over-approximation of the number of elements.
+    ///
+    /// *O*(1) time
     pub fn len(&self) -> usize {
         self.inner.len
     }
@@ -246,6 +257,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     ///
     /// Note that this may return false even if all keys in the map have
     /// expired, if they haven't been collected yet.
+    ///
+    /// *O*(1) time
     pub fn is_empty(&self) -> bool {
         self.len() == 0
     }
@@ -253,6 +266,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     /// The proportion of buckets that are used.
     ///
     /// This is an over-approximation because of expired keys.
+    ///
+    /// *O*(1) time
     pub fn load_factor(&self) -> f32 {
         (self.len() as f32 + 1.0) / self.capacity() as f32
     }
@@ -272,6 +287,10 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Gets the requested entry.
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
         self.maybe_adjust_size();
         self.entry_no_grow(key)
@@ -279,7 +298,7 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
 
     fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
         let mut inner = {
-            let hash_code = K::with_key(&key, |k| self.hash(k));
+            let hash_code = self.hash(&key, K::hash);
             InnerEntry {
                 pos:        self.which_bucket(hash_code),
                 map:        &mut self.inner,
@@ -308,6 +327,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Removes all associations from the map.
+    ///
+    /// *O*(*n*) time
     pub fn clear(&mut self) {
         self.drain();
     }
@@ -318,14 +339,14 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     {
         if self.capacity() == 0 { return None; }
 
-        let hash_code = self.hash(key);
+        let hash_code = self.hash(key, Q::hash);
         let mut pos = self.which_bucket(hash_code);
 
         for dist in 0 .. self.capacity() {
             if let Some((ref w_key, ref w_value, b_hash_code)) = self.inner.buckets[pos] {
                 if b_hash_code == hash_code {
                     if let (Some(b_key), Some(b_value)) = (w_key.view(), w_value.view()) {
-                        if K::with_key(&b_key, |k| k.borrow() == key) {
+                        if K::equals(&b_key, key) {
                             return Some((pos, b_key, b_value));
                         }
                     }
@@ -347,6 +368,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Returns a reference to the value corresponding to the key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get<Q>(&self, key: &Q) -> Option<V::Strong>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -355,6 +378,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Returns the strong reference to the key, if present.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -363,6 +388,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Returns strong references to both the key and the value, if present.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, V::Strong)>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -371,6 +398,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Returns true if the map contains the specified key.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn contains_key<Q>(&self, key: &Q) -> bool
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -381,6 +410,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     /// Unconditionally inserts the value, returning the old value if already present.
     ///
     /// Unlike `std::collections::HashMap`, this replaces the key even if occupied.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> {
         match self.entry(key) {
             Entry::Occupied(mut occupied) => {
@@ -394,6 +425,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Removes the entry with the given key, if it exists, and returns the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong>
         where Q: ?Sized + Hash + Eq,
               K::Key: Borrow<Q>
@@ -409,6 +442,8 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     /// Removes all mappings not satisfying the given predicate.
     ///
     /// Also removes any expired mappings.
+    ///
+    /// *O*(*n*) time
     pub fn retain<F>(&mut self, mut f: F)
         where F: FnMut(K::Strong, V::Strong) -> bool
     {
@@ -432,6 +467,10 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     ///
     /// In particular, all the keys of `self` must be in `other` and the values must compare
     /// `true` with `value_equal`.
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap_with<F, S1, V1>(&self, other: &WeakWeakHashMap<K, V1, S1>,
                                      mut value_equal: F) -> bool
         where V1: WeakElement,
@@ -452,6 +491,10 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Is `self` a submap of `other`?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn is_submap<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
         where V1: WeakElement,
               V::Strong: PartialEq<V1::Strong>,
@@ -461,6 +504,10 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     }
 
     /// Are the keys of `self` a subset of the keys of `other`?
+    ///
+    /// expected *O*(*n*) time; worst-case *O*(*nq*) time (where *n* is
+    /// `self.capacity()` and *q* is the length of the probe sequences
+    /// in `other`)
     pub fn domain_is_subset<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
         where V1: WeakElement,
               S1: BuildHasher
@@ -468,12 +515,11 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
         self.is_submap_with(other, |_, _| true)
     }
 
-    fn hash<Q>(&self, key: &Q) -> HashCode
-        where Q: ?Sized + Hash,
-              K::Key: Borrow<Q>
+    fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode
+        where H: FnOnce(Q, &mut S::Hasher)
     {
-        let mut hasher = self.hash_builder.build_hasher();
-        key.hash(&mut hasher);
+        let hasher = &mut self.hash_builder.build_hasher();
+        hash(key, hasher);
         HashCode(hasher.finish())
     }
 }
@@ -501,7 +547,7 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher + Default> Default for WeakWeakH
     }
 }
 
-impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
+impl<K, V, S> iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
     where K: WeakKey,
           V: WeakElement,
           S: BuildHasher + Default
@@ -538,7 +584,7 @@ impl<'a, K: WeakKey, V: WeakElement> InnerEntry<'a, K, V> {
             Some(bucket) => {
                 if bucket.2 == self.hash_code {
                     if let (Some(key), Some(value)) = (bucket.0.view(), bucket.1.view()) {
-                        if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
+                        if K::with_key(&self.key, |k| K::equals(&key, k)) {
                             return BucketStatus::MatchesKey(value);
                         }
                     }
@@ -557,6 +603,8 @@ impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> {
     /// Ensures a value is in the entry by inserting a default value
     /// if empty, and returns a mutable reference to the value in the
     /// entry.
+    ///
+    /// *O*(1) time
     pub fn or_insert(self, default: V::Strong) -> V::Strong {
         self.or_insert_with(|| default)
     }
@@ -564,6 +612,8 @@ impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> {
     /// Ensures a value is in the entry by inserting the result of the
     /// default function if empty, and returns a mutable reference to
     /// the value in the entry.
+    ///
+    /// *O*(1) time
     pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong {
         match self {
             Entry::Occupied(occupied) => occupied.get_strong(),
@@ -572,6 +622,8 @@ impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> {
     }
 
     /// Returns a reference to this entry's key.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K::Strong {
         match *self {
             Entry::Occupied(ref occupied) => occupied.key(),
@@ -582,11 +634,15 @@ impl<'a, K: WeakKey, V: WeakElement> Entry<'a, K, V> {
 
 impl<'a, K: WeakKey, V: WeakElement> OccupiedEntry<'a, K, V> {
     /// Gets a reference to the key held by the entry.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K::Strong {
         &self.inner.key
     }
 
     /// Takes ownership of the key and value from the map.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove_entry(self) -> (K::Strong, V::Strong) {
         let (_, w_value, _) = self.inner.map.buckets[self.inner.pos].take().unwrap();
         let value = w_value.view().unwrap();
@@ -595,22 +651,30 @@ impl<'a, K: WeakKey, V: WeakElement> OccupiedEntry<'a, K, V> {
     }
 
     /// Gets a reference to the value in the entry.
+    ///
+    /// *O*(1) time
     pub fn get(&self) -> &V::Strong {
         &self.value
     }
 
     /// Gets a clone of the reference to the value in the entry.
+    ///
+    /// *O*(1) time
     pub fn get_strong(&self) -> V::Strong {
         V::clone(&self.value)
     }
 
     /// Replaces the value in the entry with the given value.
+    ///
+    /// *O*(1) time
     pub fn insert(&mut self, value: V::Strong) -> V::Strong {
         self.inner.map.buckets[self.inner.pos].as_mut().unwrap().1 = V::new(&value);
         mem::replace(&mut self.value, value)
     }
 
     /// Removes the entry, returning the value.
+    ///
+    /// expected *O*(1) time; worst-case *O*(*p*) time
     pub fn remove(self) -> V::Strong {
         self.remove_entry().1
     }
@@ -619,16 +683,22 @@ impl<'a, K: WeakKey, V: WeakElement> OccupiedEntry<'a, K, V> {
 impl<'a, K: WeakKey, V: WeakElement> VacantEntry<'a, K, V> {
     /// Gets a reference to the key that would be used when inserting a
     /// value through the `VacantEntry`.
+    ///
+    /// *O*(1) time
     pub fn key(&self) -> &K::Strong {
         &self.inner.key
     }
 
     /// Returns ownership of the key.
+    ///
+    /// *O*(1) time
     pub fn into_key(self) -> K::Strong {
         self.inner.key
     }
 
     /// Inserts the key and value into the map, returning the same value.
+    ///
+    /// *O*(1) time
     pub fn insert(self, value: V::Strong) -> V::Strong {
         let old_bucket = mem::replace(
             &mut self.inner.map.buckets[self.inner.pos],
@@ -853,6 +923,9 @@ impl<K: WeakElement, V: WeakElement, S> IntoIterator for WeakWeakHashMap<K, V, S
     type Item = (K::Strong, V::Strong);
     type IntoIter = IntoIter<K, V>;
 
+    /// Creates an owning iterator from `self`.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     fn into_iter(self) -> Self::IntoIter {
         IntoIter {
             size: self.inner.len,
@@ -865,6 +938,9 @@ impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a WeakWeakHashMap
     type Item = (K::Strong, V::Strong);
     type IntoIter = Iter<'a, K, V>;
 
+    /// Creates a borrowing iterator from `self`.
+    ///
+    /// *O*(1) time
     fn into_iter(self) -> Self::IntoIter {
         Iter {
             base: self.inner.buckets.iter(),
@@ -875,21 +951,29 @@ impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a WeakWeakHashMap
 
 impl<K: WeakElement, V: WeakElement, S> WeakWeakHashMap<K, V, S> {
     /// Gets an iterator over the keys and values.
+    ///
+    /// *O*(1) time
     pub fn iter(&self) -> Iter<K, V> {
         self.into_iter()
     }
 
     /// Gets an iterator over the keys.
+    ///
+    /// *O*(1) time
     pub fn keys(&self) -> Keys<K, V> {
         Keys(self.iter())
     }
 
     /// Gets an iterator over the values.
+    ///
+    /// *O*(1) time
     pub fn values(&self) -> Values<K, V> {
         Values(self.iter())
     }
 
     /// Gets a draining iterator, which removes all the values but retains the storage.
+    ///
+    /// *O*(1) time (and *O*(*n*) time to dispose of the result)
     pub fn drain(&mut self) -> Drain<K, V> {
         let old_len = self.inner.len;
         self.inner.len = 0;
diff --git a/tests/weak_key_hash_map.rs b/tests/weak_key_hash_map.rs
index fe18890..5d50764 100644
--- a/tests/weak_key_hash_map.rs
+++ b/tests/weak_key_hash_map.rs
@@ -3,7 +3,6 @@ use std::fmt::Debug;
 use std::hash::Hash;
 use std::rc::{Rc, Weak};
 
-use rand::Rng;
 use quickcheck::{Arbitrary, Gen, quickcheck};
 
 use weak_table::WeakKeyHashMap;
@@ -138,22 +137,22 @@ impl<K, V> Tester<K, V>
 }
 
 impl<K: Arbitrary, V: Arbitrary> Arbitrary for Cmd<K, V> {
-    fn arbitrary<G: Gen>(g: &mut G) -> Self {
-        let choice = g.gen_range(0, 100);
-
-        match choice {
-            00..=39 => Insert(K::arbitrary(g), V::arbitrary(g)),
-            40..=49 => Reinsert(usize::arbitrary(g), V::arbitrary(g)),
-            50..=69 => RemoveInserted(usize::arbitrary(g)),
-            70..=79 => RemoveOther(K::arbitrary(g)),
-            80..=99 => ForgetInserted(usize::arbitrary(g)),
+    fn arbitrary(g: &mut Gen) -> Self {
+        let choice = u8::arbitrary(g);
+
+        match choice % 10 {
+            0..=3 => Insert(K::arbitrary(g), V::arbitrary(g)),
+            4     => Reinsert(usize::arbitrary(g), V::arbitrary(g)),
+            5..=6 => RemoveInserted(usize::arbitrary(g)),
+            7     => RemoveOther(K::arbitrary(g)),
+            8..=9 => ForgetInserted(usize::arbitrary(g)),
             _       => unreachable!(),
         }
     }
 }
 
 impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> {
-    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+    fn arbitrary(g: &mut Gen) -> Self {
         Script(Vec::<Cmd<K, V>>::arbitrary(g))
     }