Snap for 8730993 from a429f9215f3b261ed1dd0072afa024e44d32a172 to mainline-tzdata3-releaseaml_tz3_314012070aml_tz3_314012050aml_tz3_314012010aml_tz3_313110000aml_tz3_312511020aml_tz3_312511010aml_tz3_312410020aml_tz3_312410010android12-mainline-tzdata3-releaseaml_tz3_314012010

Change-Id: Ife0ef4aff2cb1a58f54dcdf7dabab687a5e01146

25 files changed, 192 insertions, 975 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index bace32e..6f8967e 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,5 @@
 {
   "git": {
-    "sha1": "c4ac207b8f266ff3becd123f693f07536b97d088"
+    "sha1": "80489689035c908f1096c07a8a0c51250f3dc979"
   }
 }
diff --git a/.github/dependabot.yml b/.github/dependabot.yml
deleted file mode 100644
index cf039be..0000000
--- a/.github/dependabot.yml
+++ /dev/null
@@ -1,8 +0,0 @@
-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
deleted file mode 100644
index df81fe8..0000000
--- a/.github/workflows/ci.yml
+++ /dev/null
@@ -1,71 +0,0 @@
-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
new file mode 100644
index 0000000..563df5b
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,23 @@
+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 2ff1215..33c19f1 100644
--- a/Android.bp
+++ b/Android.bp
@@ -1,5 +1,4 @@
-// This file is generated by cargo2android.py --config cargo2android.json.
-// Do not modify this file as changes will be overridden on upgrade.
+// This file is generated by cargo2android.py --device --run --dependencies.
 
 package {
     default_applicable_licenses: ["external_rust_crates_weak-table_license"],
@@ -22,12 +21,6 @@ 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
deleted file mode 100644
index 68c526e..0000000
--- a/CHANGELOG.md
+++ /dev/null
@@ -1,89 +0,0 @@
-# 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 b2e6cc8..343cfab 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,33 +3,27 @@
 # 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 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.
+# 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)
 
 [package]
 edition = "2018"
 name = "weak-table"
-version = "0.3.2"
+version = "0.3.0"
 authors = ["Jesse A. Tov <jesse.tov@gmail.com>"]
 description = "Weak hash maps and sets"
 readme = "README.md"
-keywords = ["containers", "Rc", "Arc", "weak", "no_std"]
+keywords = ["containers", "Rc", "Arc", "weak"]
 license = "MIT"
 repository = "https://github.com/tov/weak-table-rs"
-[dependencies.ahash]
-version = "0.7.6"
-features = []
-optional = true
+
+[dependencies]
 [dev-dependencies.quickcheck]
-version = "1"
+version = "0.9"
 
 [dev-dependencies.rand]
-version = "0.8.4"
-
-[features]
-alloc = []
-default = ["std"]
-std = []
+version = "0.7.2"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 3594791..7cb87e3 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,24 +1,17 @@
 [package]
 name = "weak-table"
-version = "0.3.2"
+version = "0.3.0"
 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", "no_std"]
+keywords = ["containers", "Rc", "Arc", "weak"]
 edition = "2018"
 
 [dependencies]
-ahash = { version = "0.7.6", optional = true, features = [] }
 
 [dev-dependencies]
-quickcheck = "1"
-rand = "0.8.4"
+quickcheck = "0.9"
+rand = "0.7.2"
 
-[features]
-default = ["std"]
-std = []
-
-# This feature doesn’t actually do anything. TODO: remove in v0.4.
-alloc = []
diff --git a/METADATA b/METADATA
index 3317bcc..29097c3 100644
--- a/METADATA
+++ b/METADATA
@@ -1,5 +1,7 @@
 name: "weak-table"
-description: "Weak hash maps and sets"
+description:
+    "Weak hash maps and sets"
+
 third_party {
   url {
     type: HOMEPAGE
@@ -7,13 +9,9 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/weak-table/weak-table-0.3.2.crate"
+    value: "https://static.crates.io/crates/weak-table/weak-table-0.3.0.crate"
   }
-  version: "0.3.2"
+  version: "0.3.0"
+  last_upgrade_date { year: 2020 month: 10 day: 9 }
   license_type: NOTICE
-  last_upgrade_date {
-    year: 2022
-    month: 3
-    day: 1
-  }
 }
diff --git a/README.md b/README.md
index 9d4ac80..56fa462 100644
--- a/README.md
+++ b/README.md
@@ -1,25 +1,13 @@
 # weak-table: weak hash maps and sets for Rust
 
-[![Build Status](https://github.com/tov/weak-table-rs/actions/workflows/ci.yml/badge.svg)](https://github.com/tov/weak-table-rs/actions)
+[![Build Status](https://travis-ci.org/tov/weak-table-rs.svg?branch=master)](https://travis-ci.org/tov/weak-table-rs)
 [![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.
 
-### 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.
+This crate supports Rust version 1.32 and later.
 
 ### Examples
 
diff --git a/cargo2android.json b/cargo2android.json
deleted file mode 100644
index bf78496..0000000
--- a/cargo2android.json
+++ /dev/null
@@ -1,4 +0,0 @@
-{
-  "device": true,
-  "run": true
-}
\ No newline at end of file
diff --git a/release.toml b/release.toml
index 03d6f0d..5d7a460 100644
--- a/release.toml
+++ b/release.toml
@@ -1,17 +1,3 @@
-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}}>'''
+pre-release-replacements = [
+  { file="src/lib.rs", search="https://docs[.]rs/weak-table/[0-9.]*", replace="https://docs.rs/weak-table/{{version}}" }
+]
diff --git a/src/by_ptr.rs b/src/by_ptr.rs
index 7dc4c77..b541f9e 100644
--- a/src/by_ptr.rs
+++ b/src/by_ptr.rs
@@ -1,4 +1,4 @@
-use crate::compat::*;
+use std::ops::Deref;
 
 use super::traits::*;
 
diff --git a/src/compat.rs b/src/compat.rs
deleted file mode 100644
index 4644b17..0000000
--- a/src/compat.rs
+++ /dev/null
@@ -1,56 +0,0 @@
-//! `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 6851e7b..ce5e596 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,3 +1,4 @@
+#![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
@@ -26,32 +27,7 @@
 //! To add support for your own weak pointers, see
 //! [the traits `WeakElement` and `WeakKey`](traits/).
 //!
-//! ## 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.
+//! This crate supports Rust version 1.32 and later.
 //!
 //! # Examples
 //!
@@ -141,11 +117,7 @@
 //! }
 //! ```
 
-#![doc(html_root_url = "https://docs.rs/weak-table/0.3.2")]
-
-#![cfg_attr(not(feature = "std"), no_std)]
-
-use self::compat::*;
+use std::collections::hash_map::RandomState;
 
 pub mod traits;
 pub mod weak_key_hash_map;
@@ -156,7 +128,6 @@ 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 9f6cb71..9a38b4e 100644
--- a/src/ptr_weak_hash_set.rs
+++ b/src/ptr_weak_hash_set.rs
@@ -1,6 +1,10 @@
 //! A hash set where the elements are held by weak pointers and compared by pointer.
 
-use crate::compat::*;
+use std::collections::hash_map::RandomState;
+use std::fmt::{self, Debug};
+use std::hash::BuildHasher;
+use std::iter::FromIterator;
+use std::ops::Deref;
 
 use super::traits::*;
 use super::ptr_weak_key_hash_map as base;
@@ -12,15 +16,11 @@ 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,57 +30,41 @@ 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()
     }
@@ -89,8 +73,6 @@ 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
     }
@@ -99,37 +81,27 @@ 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()
     }
@@ -137,8 +109,6 @@ 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
     {
@@ -146,10 +116,6 @@ 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
     {
@@ -206,15 +172,11 @@ 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())
     }
@@ -277,9 +239,6 @@ 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())
     }
@@ -291,9 +250,6 @@ 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 2cd5591..cd48809 100644
--- a/src/ptr_weak_key_hash_map.rs
+++ b/src/ptr_weak_key_hash_map.rs
@@ -1,6 +1,10 @@
 //! A hash map where the keys are held by weak pointers and compared by pointer.
 
-use crate::compat::*;
+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 super::by_ptr::*;
 use super::traits::*;
@@ -13,15 +17,11 @@ 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,57 +31,41 @@ 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()
     }
@@ -90,8 +74,6 @@ 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
     }
@@ -99,58 +81,42 @@ 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 _))
     }
@@ -158,8 +124,6 @@ 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
     {
@@ -170,10 +134,6 @@ 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
@@ -182,10 +142,6 @@ 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
@@ -194,10 +150,6 @@ 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
     {
@@ -209,43 +161,31 @@ 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()
     }
@@ -343,9 +283,6 @@ 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()
     }
@@ -355,9 +292,6 @@ 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()
     }
@@ -367,22 +301,17 @@ 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::compat::{
-        eprintln,
-        rc::{Rc, Weak},
-        Vec,
-    };
-    use super::{Entry, PtrWeakKeyHashMap};
+mod test
+{
+    use crate::PtrWeakKeyHashMap;
+    use crate::weak_key_hash_map::Entry;
+    use std::rc::{Rc, Weak};
 
 //    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 fb49ae7..e842cd2 100644
--- a/src/ptr_weak_weak_hash_map.rs
+++ b/src/ptr_weak_weak_hash_map.rs
@@ -1,7 +1,11 @@
 //! A hash map where the keys and values are both held by weak pointers, and keys are compared by
 //! pointer.
 
-use crate::compat::*;
+use std::collections::hash_map::RandomState;
+use std::fmt::{self, Debug};
+use std::hash::BuildHasher;
+use std::iter::FromIterator;
+use std::ops::Deref;
 
 use super::by_ptr::*;
 use super::traits::*;
@@ -14,15 +18,11 @@ 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,57 +32,41 @@ 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()
     }
@@ -91,8 +75,6 @@ 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()
     }
@@ -100,51 +82,37 @@ 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 _))
     }
@@ -152,8 +120,6 @@ 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
     {
@@ -164,10 +130,6 @@ 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,
@@ -177,10 +139,6 @@ 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>,
@@ -190,10 +148,6 @@ 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
@@ -206,29 +160,21 @@ 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()
     }
@@ -299,9 +245,6 @@ 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()
     }
@@ -311,22 +254,17 @@ 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::compat::{
-        eprintln,
-        rc::{Rc, Weak},
-        Vec,
-    };
-    use super::{Entry, PtrWeakWeakHashMap};
+mod test
+{
+    use crate::PtrWeakWeakHashMap;
+    use crate::weak_weak_hash_map::Entry;
+    use std::rc::{Rc, Weak};
 
 //    fn show_me(weakmap: &PtrWeakWeakHashMap<Weak<u32>, Weak<f32>>) {
 //        for (key, _) in weakmap {
diff --git a/src/traits.rs b/src/traits.rs
index 878e5a3..440a6c9 100644
--- a/src/traits.rs
+++ b/src/traits.rs
@@ -7,7 +7,8 @@
 //! 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 crate::compat::*;
+use std::hash::Hash;
+use std::{rc, sync};
 
 /// Interface for elements that can be stored in weak hash tables.
 ///
@@ -69,19 +70,6 @@ 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> {
@@ -106,7 +94,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)
     }
 }
 
@@ -133,7 +121,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 9affd7f..3792ec7 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -1,5 +1,3 @@
-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 bbff3b8..a3bc151 100644
--- a/src/weak_hash_set.rs
+++ b/src/weak_hash_set.rs
@@ -1,6 +1,10 @@
 //! A hash set where the elements are held by weak pointers and compared by value.
 
-use crate::compat::*;
+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 super::traits::*;
 use super::weak_key_hash_map as base;
@@ -9,15 +13,11 @@ 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,57 +25,41 @@ 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()
     }
@@ -84,8 +68,6 @@ 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()
     }
@@ -93,15 +75,11 @@ 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()
     }
@@ -109,8 +87,6 @@ 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>
@@ -136,8 +112,6 @@ 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>
@@ -147,15 +121,11 @@ 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>
@@ -166,8 +136,6 @@ 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
     {
@@ -175,10 +143,6 @@ 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
     {
@@ -233,15 +197,11 @@ 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())
     }
@@ -295,9 +255,6 @@ 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())
     }
@@ -307,9 +264,6 @@ 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 7dcb8c4..91bee2a 100644
--- a/src/weak_key_hash_map.rs
+++ b/src/weak_key_hash_map.rs
@@ -1,5 +1,12 @@
 //! 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::*;
@@ -29,7 +36,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: slice::Iter<'a, Bucket<K, V>>,
+    base: ::std::slice::Iter<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -37,7 +44,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> {
-        for bucket in &mut self.base {
+        while let Some(bucket) = self.base.next() {
             if let Some((ref weak_ptr, ref value, _)) = *bucket {
                 self.size -= 1;
                 if let Some(strong_ptr) = weak_ptr.view() {
@@ -57,7 +64,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: slice::IterMut<'a, Bucket<K, V>>,
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -65,7 +72,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> {
-        for bucket in &mut self.base {
+        while let Some(bucket) = self.base.next() {
             if let Some((ref weak_ptr, ref mut value, _)) = *bucket {
                 self.size -= 1;
                 if let Some(strong_ptr) = weak_ptr.view() {
@@ -133,7 +140,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: slice::IterMut<'a, Bucket<K, V>>,
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -141,7 +148,7 @@ impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> {
     type Item = (K::Strong, V);
 
     fn next(&mut self) -> Option<Self::Item> {
-        for bucket in &mut self.base {
+        while let Some(bucket) = self.base.next() {
             if let Some((weak_ptr, value, _)) = bucket.take() {
                 self.size -= 1;
                 if let Some(strong_ptr) = weak_ptr.view() {
@@ -160,7 +167,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) {
-        for option in &mut self.base {
+        while let Some(option) = self.base.next() {
             *option = None;
         }
     }
@@ -168,7 +175,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: vec::IntoIter<Bucket<K, V>>,
+    base: ::std::vec::IntoIter<Bucket<K, V>>,
     size: usize,
 }
 
@@ -176,10 +183,12 @@ impl<K: WeakElement, V> Iterator for IntoIter<K, V> {
     type Item = (K::Strong, V);
 
     fn next(&mut self) -> Option<Self::Item> {
-        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));
+        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));
+                }
             }
         }
 
@@ -194,15 +203,11 @@ 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())
     }
@@ -211,15 +216,11 @@ 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,
@@ -231,15 +232,11 @@ 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()
     }
@@ -262,23 +259,17 @@ 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;
@@ -286,8 +277,6 @@ 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
     }
@@ -296,8 +285,6 @@ 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
     }
@@ -305,8 +292,6 @@ 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
     }
@@ -326,8 +311,6 @@ 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)
@@ -335,7 +318,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 = self.hash(&key, K::hash);
+            let hash_code = K::with_key(&key, |k| self.hash(k));
             InnerEntry {
                 pos:        self.which_bucket(hash_code),
                 map:        &mut self.inner,
@@ -364,8 +347,6 @@ 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();
     }
@@ -376,14 +357,14 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
     {
         if self.capacity() == 0 { return None; }
 
-        let hash_code = self.hash(key, Q::hash);
+        let hash_code = self.hash(key);
         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::equals(&bucket_key, key) {
+                        if K::with_key(&bucket_key, |k| k.borrow() == key) {
                             return Some((pos, bucket_key, bucket_hash_code));
                         }
                     }
@@ -405,8 +386,6 @@ 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>
@@ -416,8 +395,6 @@ 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>
@@ -426,8 +403,6 @@ 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>
@@ -436,8 +411,6 @@ 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>
@@ -447,8 +420,6 @@ 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>
@@ -459,8 +430,6 @@ 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>
@@ -472,8 +441,6 @@ 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) => {
@@ -487,8 +454,6 @@ 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>
@@ -506,8 +471,6 @@ 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
     {
@@ -527,24 +490,18 @@ impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
         }
     }
 
-    /// Is this map a submap of the other under the given value comparison `cmp`?
+    /// Is this map a submap of the other, using the given value comparison.
     ///
-    /// 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`)
+    /// In particular, all the keys of `self` must be in `other` and the values must compare
+    /// `true` with `value_equal`.
     pub fn is_submap_with<F, S1, V1>(&self, other: &WeakKeyHashMap<K, V1, S1>,
-                                     mut cmp: F) -> bool
+                                     mut value_equal: 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 !cmp(value1, value2) {
+                if !value_equal(value1, value2) {
                     return false;
                 }
             } else {
@@ -556,10 +513,6 @@ 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
@@ -568,21 +521,18 @@ 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, H>(&self, key: Q, hash: H) -> HashCode
-        where H: FnOnce(Q, &mut S::Hasher)
+    fn hash<Q>(&self, key: &Q) -> HashCode
+        where Q: ?Sized + Hash,
+              K::Key: Borrow<Q>
     {
-        let hasher = &mut self.hash_builder.build_hasher();
-        hash(key, hasher);
+        let mut hasher = self.hash_builder.build_hasher();
+        key.hash(&mut hasher);
         HashCode(hasher.finish())
     }
 }
@@ -606,7 +556,7 @@ impl<K: WeakKey, V, S: BuildHasher + Default> Default for WeakKeyHashMap<K, V, S
     }
 }
 
-impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S, Q> ::std::ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           K::Key: Borrow<Q>,
           S: BuildHasher,
@@ -619,7 +569,7 @@ impl<'a, K, V, S, Q> ops::Index<&'a Q> for WeakKeyHashMap<K, V, S>
     }
 }
 
-impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S, Q> ::std::ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           K::Key: Borrow<Q>,
           S: BuildHasher,
@@ -630,7 +580,7 @@ impl<'a, K, V, S, Q> ops::IndexMut<&'a Q> for WeakKeyHashMap<K, V, S>
     }
 }
 
-impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           S: BuildHasher + Default
 {
@@ -641,7 +591,7 @@ impl<K, V, S> iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
     }
 }
 
-impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+impl<K, V, S> ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
     where K: WeakKey,
           S: BuildHasher
 {
@@ -652,7 +602,7 @@ impl<K, V, S> iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
     }
 }
 
-impl<'a, K, V, S> iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
+impl<'a, K, V, S> ::std::iter::Extend<(&'a K::Strong, &'a V)> for WeakKeyHashMap<K, V, S>
     where K: 'a + WeakKey,
           K::Strong: Clone,
           V: 'a + Clone,
@@ -678,7 +628,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, |k| K::equals(&key, k)) {
+                        if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
                             return BucketStatus::MatchesKey;
                         }
                     }
@@ -697,8 +647,6 @@ 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)
     }
@@ -706,8 +654,6 @@ 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(),
@@ -716,8 +662,6 @@ 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(),
@@ -728,15 +672,11 @@ 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);
@@ -744,29 +684,21 @@ 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);
@@ -774,8 +706,6 @@ 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
     }
@@ -784,23 +714,17 @@ 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],
@@ -1010,9 +934,6 @@ 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,
@@ -1025,9 +946,6 @@ 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(),
@@ -1040,9 +958,6 @@ 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(),
@@ -1053,43 +968,31 @@ 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;
@@ -1101,13 +1004,8 @@ impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
 }
 
 #[cfg(test)]
-mod test {
-    use crate::compat::{
-        eprintln,
-        rc::{Rc, Weak},
-        String,
-        Vec,
-    };
+mod tests {
+    use std::rc::{Rc, Weak};
     use super::{Entry, WeakKeyHashMap};
 
     #[test]
@@ -1116,7 +1014,7 @@ mod test {
         assert_eq!( map.len(), 0 );
         assert!( !map.contains_key("five") );
 
-        let five: Rc<str> = Rc::from(String::from("five"));
+        let five: Rc<str> = Rc::from("five".to_string());
         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 7177e41..8b60a17 100644
--- a/src/weak_value_hash_map.rs
+++ b/src/weak_value_hash_map.rs
@@ -1,5 +1,12 @@
 //! 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::*;
@@ -34,7 +41,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: slice::Iter<'a, Bucket<K, V>>,
+    base: ::std::slice::Iter<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -42,7 +49,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> {
-        for bucket in &mut self.base {
+        while let Some(bucket) = self.base.next() {
             if let Some((ref key, ref weak_value, _)) = *bucket {
                 self.size -= 1;
                 if let Some(value) = weak_value.view() {
@@ -94,7 +101,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: slice::IterMut<'a, Bucket<K, V>>,
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -102,7 +109,7 @@ impl<'a, K, V: WeakElement> Iterator for Drain<'a, K, V> {
     type Item = (K, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        for bucket in &mut self.base {
+        while let Some(bucket) = self.base.next() {
             if let Some((key, weak_value, _)) = bucket.take() {
                 self.size -= 1;
                 if let Some(value) = weak_value.view() {
@@ -121,7 +128,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) {
-        for option in &mut self.base {
+        while let Some(option) = self.base.next() {
             *option = None;
         }
     }
@@ -129,7 +136,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: vec::IntoIter<Bucket<K, V>>,
+    base: ::std::vec::IntoIter<Bucket<K, V>>,
     size: usize,
 }
 
@@ -137,10 +144,12 @@ impl<K, V: WeakElement> Iterator for IntoIter<K, V> {
     type Item = (K, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        for (key, weak_value, _) in (&mut self.base).flatten() {
-            self.size -= 1;
-            if let Some(value) = weak_value.view() {
-                return Some((key, value));
+        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));
+                }
             }
         }
 
@@ -155,15 +164,11 @@ 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())
     }
@@ -172,15 +177,11 @@ 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,
@@ -192,15 +193,11 @@ 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()
     }
@@ -223,23 +220,17 @@ 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;
@@ -247,8 +238,6 @@ 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
     }
@@ -257,8 +246,6 @@ 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
     }
@@ -266,8 +253,6 @@ 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
     }
@@ -287,8 +272,6 @@ 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)
@@ -326,8 +309,6 @@ 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();
     }
@@ -367,8 +348,6 @@ 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>
@@ -377,8 +356,6 @@ 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>
@@ -389,8 +366,6 @@ 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) => {
@@ -404,8 +379,6 @@ 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>
@@ -421,8 +394,6 @@ 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
     {
@@ -446,10 +417,6 @@ 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,
@@ -470,10 +437,6 @@ 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>,
@@ -483,10 +446,6 @@ 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
@@ -527,7 +486,7 @@ impl<K: Eq + Hash, V: WeakElement, S: BuildHasher + Default> Default for WeakVal
     }
 }
 
-impl<K, V, S> iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S>
+impl<K, V, S> ::std::iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S>
     where K: Eq + Hash,
           V: WeakElement,
           S: BuildHasher + Default
@@ -595,16 +554,12 @@ 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(),
@@ -613,8 +568,6 @@ 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(),
@@ -625,15 +578,11 @@ 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();
@@ -642,30 +591,22 @@ 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
     }
@@ -674,22 +615,16 @@ 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;
 
@@ -901,9 +836,6 @@ 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,
@@ -916,9 +848,6 @@ 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(),
@@ -929,29 +858,21 @@ 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 801bc64..0ed89f6 100644
--- a/src/weak_weak_hash_map.rs
+++ b/src/weak_weak_hash_map.rs
@@ -1,6 +1,13 @@
 //! 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::*;
@@ -35,7 +42,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: slice::Iter<'a, Bucket<K, V>>,
+    base: ::std::slice::Iter<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -43,7 +50,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> {
-        for bucket in &mut self.base {
+        while let Some(bucket) = self.base.next() {
             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()) {
@@ -95,7 +102,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: slice::IterMut<'a, Bucket<K, V>>,
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
     size: usize,
 }
 
@@ -103,7 +110,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> {
-        for bucket in &mut self.base {
+        while let Some(bucket) = self.base.next() {
             if let Some((weak_key, weak_value, _)) = bucket.take() {
                 self.size -= 1;
                 if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
@@ -122,7 +129,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) {
-        for option in &mut self.base {
+        while let Some(option) = self.base.next() {
             *option = None;
         }
     }
@@ -130,7 +137,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: vec::IntoIter<Bucket<K, V>>,
+    base: ::std::vec::IntoIter<Bucket<K, V>>,
     size: usize,
 }
 
@@ -138,10 +145,12 @@ impl<K: WeakElement, V: WeakElement> Iterator for IntoIter<K, V> {
     type Item = (K::Strong, V::Strong);
 
     fn next(&mut self) -> Option<Self::Item> {
-        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));
+        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));
+                }
             }
         }
 
@@ -156,15 +165,11 @@ 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())
     }
@@ -172,15 +177,11 @@ 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,
@@ -192,15 +193,11 @@ 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()
     }
@@ -223,23 +220,17 @@ 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;
@@ -247,8 +238,6 @@ 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
     }
@@ -257,8 +246,6 @@ 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
     }
@@ -266,8 +253,6 @@ 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
     }
@@ -287,10 +272,6 @@ 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)
@@ -298,7 +279,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 = self.hash(&key, K::hash);
+            let hash_code = K::with_key(&key, |k| self.hash(k));
             InnerEntry {
                 pos:        self.which_bucket(hash_code),
                 map:        &mut self.inner,
@@ -327,8 +308,6 @@ 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();
     }
@@ -339,14 +318,14 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
     {
         if self.capacity() == 0 { return None; }
 
-        let hash_code = self.hash(key, Q::hash);
+        let hash_code = self.hash(key);
         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::equals(&b_key, key) {
+                        if K::with_key(&b_key, |k| k.borrow() == key) {
                             return Some((pos, b_key, b_value));
                         }
                     }
@@ -368,8 +347,6 @@ 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>
@@ -378,8 +355,6 @@ 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>
@@ -388,8 +363,6 @@ 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>
@@ -398,8 +371,6 @@ 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>
@@ -410,8 +381,6 @@ 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) => {
@@ -425,8 +394,6 @@ 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>
@@ -442,8 +409,6 @@ 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
     {
@@ -467,10 +432,6 @@ 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,
@@ -491,10 +452,6 @@ 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>,
@@ -504,10 +461,6 @@ 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
@@ -515,11 +468,12 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
         self.is_submap_with(other, |_, _| true)
     }
 
-    fn hash<Q, H>(&self, key: Q, hash: H) -> HashCode
-        where H: FnOnce(Q, &mut S::Hasher)
+    fn hash<Q>(&self, key: &Q) -> HashCode
+        where Q: ?Sized + Hash,
+              K::Key: Borrow<Q>
     {
-        let hasher = &mut self.hash_builder.build_hasher();
-        hash(key, hasher);
+        let mut hasher = self.hash_builder.build_hasher();
+        key.hash(&mut hasher);
         HashCode(hasher.finish())
     }
 }
@@ -547,7 +501,7 @@ impl<K: WeakKey, V: WeakElement, S: BuildHasher + Default> Default for WeakWeakH
     }
 }
 
-impl<K, V, S> iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
+impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
     where K: WeakKey,
           V: WeakElement,
           S: BuildHasher + Default
@@ -584,7 +538,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, |k| K::equals(&key, k)) {
+                        if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
                             return BucketStatus::MatchesKey(value);
                         }
                     }
@@ -603,8 +557,6 @@ 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)
     }
@@ -612,8 +564,6 @@ 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(),
@@ -622,8 +572,6 @@ 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(),
@@ -634,15 +582,11 @@ 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();
@@ -651,30 +595,22 @@ 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
     }
@@ -683,22 +619,16 @@ 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],
@@ -923,9 +853,6 @@ 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,
@@ -938,9 +865,6 @@ 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(),
@@ -951,29 +875,21 @@ 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 5d50764..fe18890 100644
--- a/tests/weak_key_hash_map.rs
+++ b/tests/weak_key_hash_map.rs
@@ -3,6 +3,7 @@ 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;
@@ -137,22 +138,22 @@ impl<K, V> Tester<K, V>
 }
 
 impl<K: Arbitrary, V: Arbitrary> Arbitrary for Cmd<K, V> {
-    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)),
+    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)),
             _       => unreachable!(),
         }
     }
 }
 
 impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> {
-    fn arbitrary(g: &mut Gen) -> Self {
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
         Script(Vec::<Cmd<K, V>>::arbitrary(g))
     }