Import weak-table-0.3.0

Test: None
Change-Id: Idcf231392e451e1de74377dce6804c91fd8ac868

24 files changed, 4910 insertions, 0 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
new file mode 100644
index 0000000..6f8967e
--- /dev/null
+++ b/.cargo_vcs_info.json
@@ -0,0 +1,5 @@
+{
+  "git": {
+    "sha1": "80489689035c908f1096c07a8a0c51250f3dc979"
+  }
+}
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..9035e79
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,10 @@
+# Generated by Cargo
+# will have compiled files and executables
+/target/
+
+# Remove Cargo.lock from gitignore if creating an executable, leave it for libraries
+# More information here http://doc.crates.io/guide.html#cargotoml-vs-cargolock
+Cargo.lock
+
+/.idea/
+/cmake-build-*/
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/CMakeLists.txt b/CMakeLists.txt
new file mode 100644
index 0000000..68d8985
--- /dev/null
+++ b/CMakeLists.txt
@@ -0,0 +1 @@
+# This file is here to make CLion happy.
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..343cfab
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,29 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# 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
+#
+# 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.0"
+authors = ["Jesse A. Tov <jesse.tov@gmail.com>"]
+description = "Weak hash maps and sets"
+readme = "README.md"
+keywords = ["containers", "Rc", "Arc", "weak"]
+license = "MIT"
+repository = "https://github.com/tov/weak-table-rs"
+
+[dependencies]
+[dev-dependencies.quickcheck]
+version = "0.9"
+
+[dev-dependencies.rand]
+version = "0.7.2"
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..7cb87e3
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,17 @@
+[package]
+name = "weak-table"
+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"]
+edition = "2018"
+
+[dependencies]
+
+[dev-dependencies]
+quickcheck = "0.9"
+rand = "0.7.2"
+
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..99d8eb6
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2018 Jesse A. Tov
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..6720eab
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,26 @@
+default: build
+hard: test
+
+CRATE = weak_table
+REPO  = weak-table-rs
+
+build:
+	clear
+	cargo build
+	make doc
+
+clippy:
+	rustup run nightly cargo build --features=clippy
+
+doc:
+	cargo doc
+	echo "<meta http-equiv='refresh' content='0;url=$(CRATE)/'>" > target/doc/index.html
+
+test:
+	clear
+	cargo test
+
+upload-doc:
+	make doc
+	ghp-import -n target/doc
+	git push -f https://github.com/tov/$(REPO).git gh-pages
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..56fa462
--- /dev/null
+++ b/README.md
@@ -0,0 +1,98 @@
+# weak-table: weak hash maps and sets for Rust
+
+[![Build Status](https://travis-ci.org/tov/weak-table-rs.svg?branch=master)](https://travis-ci.org/tov/weak-table-rs)
+[![Crates.io](https://img.shields.io/crates/v/weak-table.svg?maxAge=2592000)](https://crates.io/crates/weak-table)
+[![License: MIT](https://img.shields.io/badge/license-MIT-blue.svg)](LICENSE-MIT)
+
+This crate defines several kinds of weak hash maps and sets. See 
+the [full API documentation](http://docs.rs/weak-table/) for details.
+
+This crate supports Rust version 1.32 and later.
+
+### Examples
+
+Here we create a weak hash map and demonstrate that it forgets mappings
+whose keys expire:
+
+```rust
+use weak_table::WeakKeyHashMap;
+use std::sync::{Arc, Weak};
+
+let mut table = <WeakKeyHashMap<Weak<str>, u32>>::new();
+let one = Arc::<str>::from("one");
+let two = Arc::<str>::from("two");
+
+table.insert(one.clone(), 1);
+
+assert_eq!( table.get("one"), Some(&1) );
+assert_eq!( table.get("two"), None );
+
+table.insert(two.clone(), 2);
+*table.get_mut(&one).unwrap() += 10;
+
+assert_eq!( table.get("one"), Some(&11) );
+assert_eq!( table.get("two"), Some(&2) );
+
+drop(one);
+
+assert_eq!( table.get("one"), None );
+assert_eq!( table.get("two"), Some(&2) );
+```
+
+Here we use a weak hash set to implement a simple string interning facility:
+
+```rust
+use weak_table::WeakHashSet;
+use std::ops::Deref;
+use std::rc::{Rc, Weak};
+
+#[derive(Clone, Debug)]
+pub struct Symbol(Rc<str>);
+
+impl PartialEq for Symbol {
+    fn eq(&self, other: &Symbol) -> bool {
+        Rc::ptr_eq(&self.0, &other.0)
+    }
+}
+
+impl Eq for Symbol {}
+
+impl Deref for Symbol {
+    type Target = str;
+    fn deref(&self) -> &str {
+        &self.0
+    }
+}
+
+#[derive(Debug, Default)]
+pub struct SymbolTable(WeakHashSet<Weak<str>>);
+
+impl SymbolTable {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    pub fn intern(&mut self, name: &str) -> Symbol {
+        if let Some(rc) = self.0.get(name) {
+            Symbol(rc)
+        } else {
+            let rc = Rc::<str>::from(name);
+            self.0.insert(Rc::clone(&rc));
+            Symbol(rc)
+        }
+    }
+}
+
+#[test]
+fn interning() {
+    let mut tab = SymbolTable::new();
+
+    let a0 = tab.intern("a");
+    let a1 = tab.intern("a");
+    let b  = tab.intern("b");
+
+    assert_eq!(a0, a1);
+    assert_ne!(a0, b);
+}
+```
+
diff --git a/release.toml b/release.toml
new file mode 100644
index 0000000..5d7a460
--- /dev/null
+++ b/release.toml
@@ -0,0 +1,3 @@
+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
new file mode 100644
index 0000000..b541f9e
--- /dev/null
+++ b/src/by_ptr.rs
@@ -0,0 +1,33 @@
+use std::ops::Deref;
+
+use super::traits::*;
+
+/// Wrapper struct for using pointer equality and hashes rather
+/// than pointed-to value equality and hashes.
+#[derive(Clone, Debug)]
+pub struct ByPtr<K>(K);
+
+impl<K: WeakElement> WeakElement for ByPtr<K> {
+    type Strong = K::Strong;
+
+    fn new(view: &Self::Strong) -> Self {
+        ByPtr(K::new(view))
+    }
+
+    fn view(&self) -> Option<Self::Strong> {
+        self.0.view()
+    }
+}
+
+impl<K: WeakElement> WeakKey for ByPtr<K>
+    where K::Strong: Deref
+{
+    type Key = *const <K::Strong as Deref>::Target;
+
+    fn with_key<F, R>(view: &Self::Strong, f: F) -> R
+        where F: FnOnce(&Self::Key) -> R
+    {
+        f(&(view.deref() as *const _))
+    }
+}
+
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..ce5e596
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,237 @@
+#![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
+//!     [`WeakKeyHashMap`](struct.WeakKeyHashMap.html).
+//!
+//!   - For a hash map where the keys are held by weak pointers and compared by pointer, see
+//!     [`PtrWeakKeyHashMap`](struct.PtrWeakKeyHashMap.html).
+//!
+//!   - For a hash map where the values are held by weak pointers, see
+//!     [`WeakValueHashMap`](struct.WeakValueHashMap.html).
+//!
+//!   - For a hash map where the keys and values are both held by weak pointers and the keys are
+//!     compared by value, see
+//!     [`WeakWeakHashMap`](struct.WeakWeakHashMap.html).
+//!
+//!   - For a hash map where the keys and values are both held by weak pointers and the keys are
+//!     compared by pointer, see
+//!     [`PtrWeakWeakHashMap`](struct.PtrWeakWeakHashMap.html).
+//!
+//!   - For a hash set where the elements are held by weak pointers and compared by element value, see
+//!     [`WeakHashSet`](struct.WeakHashSet.html).
+//!
+//!   - For a hash set where the elements are held by weak pointers and compared by pointer, see
+//!     [`PtrWeakHashSet`](struct.PtrWeakHashSet.html).
+//!
+//! To add support for your own weak pointers, see
+//! [the traits `WeakElement` and `WeakKey`](traits/).
+//!
+//! This crate supports Rust version 1.32 and later.
+//!
+//! # Examples
+//!
+//! Here we create a weak hash table mapping strings to integers.
+//! Note that after dropping `one`, the key `"one"` is no longer present in the map.
+//! This is because the map holds the strings as `std::sync::Weak<str>`s.
+//!
+//! ```
+//! use weak_table::WeakKeyHashMap;
+//! use std::sync::{Arc, Weak};
+//!
+//! let mut table = <WeakKeyHashMap<Weak<str>, u32>>::new();
+//! let one = Arc::<str>::from("one");
+//! let two = Arc::<str>::from("two");
+//!
+//! table.insert(one.clone(), 1);
+//!
+//! assert_eq!( table.get("one"), Some(&1) );
+//! assert_eq!( table.get("two"), None );
+//!
+//! table.insert(two.clone(), 2);
+//! *table.get_mut(&one).unwrap() += 10;
+//!
+//! assert_eq!( table.get("one"), Some(&11) );
+//! assert_eq!( table.get("two"), Some(&2) );
+//!
+//! drop(one);
+//!
+//! assert_eq!( table.get("one"), None );
+//! assert_eq!( table.get("two"), Some(&2) );
+//! ```
+//!
+//! Here we use a weak hash set to implement a simple string interning facility:
+//!
+//! ```
+//! use weak_table::WeakHashSet;
+//! use std::ops::Deref;
+//! use std::rc::{Rc, Weak};
+//!
+//! #[derive(Clone, Debug)]
+//! pub struct Symbol(Rc<str>);
+//!
+//! impl PartialEq for Symbol {
+//!     fn eq(&self, other: &Symbol) -> bool {
+//!         Rc::ptr_eq(&self.0, &other.0)
+//!     }
+//! }
+//!
+//! impl Eq for Symbol {}
+//!
+//! impl Deref for Symbol {
+//!     type Target = str;
+//!     fn deref(&self) -> &str {
+//!         &self.0
+//!     }
+//! }
+//!
+//! #[derive(Debug, Default)]
+//! pub struct SymbolTable(WeakHashSet<Weak<str>>);
+//!
+//! impl SymbolTable {
+//!     pub fn new() -> Self {
+//!         Self::default()
+//!     }
+//!
+//!     pub fn intern(&mut self, name: &str) -> Symbol {
+//!         if let Some(rc) = self.0.get(name) {
+//!             Symbol(rc)
+//!         } else {
+//!             let rc = Rc::<str>::from(name);
+//!             self.0.insert(Rc::clone(&rc));
+//!             Symbol(rc)
+//!         }
+//!     }
+//! }
+//!
+//! #[test]
+//! fn interning() {
+//!     let mut tab = SymbolTable::new();
+//!
+//!     let a0 = tab.intern("a");
+//!     let a1 = tab.intern("a");
+//!     let b  = tab.intern("b");
+//!
+//!     assert_eq!(a0, a1);
+//!     assert_ne!(a0, b);
+//! }
+//! ```
+
+use std::collections::hash_map::RandomState;
+
+pub mod traits;
+pub mod weak_key_hash_map;
+pub mod ptr_weak_key_hash_map;
+pub mod weak_value_hash_map;
+pub mod weak_weak_hash_map;
+pub mod ptr_weak_weak_hash_map;
+pub mod weak_hash_set;
+pub mod ptr_weak_hash_set;
+
+mod util;
+mod by_ptr;
+mod size_policy;
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+struct HashCode(u64);
+
+type FullBucket<K, V> = (K, V, HashCode);
+type Bucket<K, V> = Option<FullBucket<K, V>>;
+type TablePtr<K, V> = Box<[Bucket<K, V>]>;
+
+/// A hash map with weak keys, hashed on key value.
+///
+/// When a weak pointer expires, its mapping is lazily removed.
+#[derive(Clone)]
+pub struct WeakKeyHashMap<K, V, S = RandomState> {
+    hash_builder: S,
+    inner: WeakKeyInnerMap<K, V>,
+}
+
+#[derive(Clone)]
+struct WeakKeyInnerMap<K, V> {
+    buckets: TablePtr<K, V>,
+    len: usize,
+}
+
+/// A hash map with weak keys, hashed on key pointer.
+///
+/// When a weak pointer expires, its mapping is lazily removed.
+///
+/// # Examples
+///
+/// ```
+/// use weak_table::PtrWeakKeyHashMap;
+/// use std::rc::{Rc, Weak};
+///
+/// type Table = PtrWeakKeyHashMap<Weak<str>, usize>;
+///
+/// let mut map = Table::new();
+/// let a = Rc::<str>::from("hello");
+/// let b = Rc::<str>::from("hello");
+///
+/// map.insert(a.clone(), 5);
+///
+/// assert_eq!( map.get(&a), Some(&5) );
+/// assert_eq!( map.get(&b), None );
+///
+/// map.insert(b.clone(), 7);
+///
+/// assert_eq!( map.get(&a), Some(&5) );
+/// assert_eq!( map.get(&b), Some(&7) );
+/// ```
+#[derive(Clone)]
+pub struct PtrWeakKeyHashMap<K, V, S = RandomState>(
+    WeakKeyHashMap<by_ptr::ByPtr<K>, V, S>
+);
+
+/// A hash map with weak values.
+///
+/// When a weak pointer expires, its mapping is lazily removed.
+#[derive(Clone)]
+pub struct WeakValueHashMap<K, V, S = RandomState> {
+    hash_builder: S,
+    inner: WeakValueInnerMap<K, V>,
+}
+
+#[derive(Clone)]
+struct WeakValueInnerMap<K, V> {
+    buckets: TablePtr<K, V>,
+    len: usize,
+}
+
+/// A hash map with weak keys and weak values, hashed on key value.
+///
+/// When a weak pointer expires, its mapping is lazily removed.
+#[derive(Clone)]
+pub struct WeakWeakHashMap<K, V, S = RandomState> {
+    hash_builder: S,
+    inner: WeakWeakInnerMap<K, V>,
+}
+
+#[derive(Clone)]
+struct WeakWeakInnerMap<K, V> {
+    buckets: TablePtr<K, V>,
+    len: usize,
+}
+
+/// A hash map with weak keys and weak values, hashed on key pointer.
+///
+/// When a weak pointer expires, its mapping is lazily removed.
+#[derive(Clone)]
+pub struct PtrWeakWeakHashMap<K, V, S = RandomState>(
+    WeakWeakHashMap<by_ptr::ByPtr<K>, V, S>
+);
+
+/// A hash set with weak elements, hashed on element value.
+///
+/// When a weak pointer expires, its mapping is lazily removed.
+#[derive(Clone)]
+pub struct WeakHashSet<T, S = RandomState>(WeakKeyHashMap<T, (), S>);
+
+/// A hash set with weak elements, hashed on element pointer.
+///
+/// When a weak pointer expires, its mapping is lazily removed.
+#[derive(Clone)]
+pub struct PtrWeakHashSet<T, S = RandomState>(PtrWeakKeyHashMap<T, (), S>);
+
diff --git a/src/ptr_weak_hash_set.rs b/src/ptr_weak_hash_set.rs
new file mode 100644
index 0000000..9a38b4e
--- /dev/null
+++ b/src/ptr_weak_hash_set.rs
@@ -0,0 +1,257 @@
+//! A hash set where the elements are held by weak pointers and compared by pointer.
+
+use std::collections::hash_map::RandomState;
+use std::fmt::{self, Debug};
+use std::hash::BuildHasher;
+use std::iter::FromIterator;
+use std::ops::Deref;
+
+use super::traits::*;
+use super::ptr_weak_key_hash_map as base;
+use super::by_ptr::ByPtr;
+
+pub use super::PtrWeakHashSet;
+
+impl <T: WeakElement> PtrWeakHashSet<T, RandomState>
+    where T::Strong: Deref
+{
+    /// Creates an empty `PtrWeakHashSet`.
+    pub fn new() -> Self {
+        PtrWeakHashSet(base::PtrWeakKeyHashMap::new())
+    }
+
+    /// Creates an empty `PtrWeakHashSet` with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        PtrWeakHashSet(base::PtrWeakKeyHashMap::with_capacity(capacity))
+    }
+}
+
+impl <T: WeakElement, S: BuildHasher> PtrWeakHashSet<T, S>
+    where T::Strong: Deref
+{
+    /// Creates an empty `PtrWeakHashSet` with the given capacity and hasher.
+    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.
+    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`.
+    pub fn hasher(&self) -> &S {
+        self.0.hasher()
+    }
+
+    /// Returns the number of elements the map can hold without reallocating.
+    pub fn capacity(&self) -> usize {
+        self.0.capacity()
+    }
+
+    /// Removes all mappings whose keys have expired.
+    pub fn remove_expired(&mut self) {
+        self.0.remove_expired()
+    }
+
+    /// Reserves room for additional elements.
+    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.
+    pub fn shrink_to_fit(&mut self) {
+        self.0.shrink_to_fit()
+    }
+
+    /// Returns an over-approximation of the number of elements.
+    pub fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    /// Is the set known to be empty?
+    ///
+    /// This could answer `false` for an empty set whose elements have
+    /// expired but have yet to be collected.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+
+    /// The proportion of buckets that are used.
+    ///
+    /// This is an over-approximation because of expired elements.
+    pub fn load_factor(&self) -> f32 {
+        self.0.load_factor()
+    }
+
+    /// Removes all associations from the map.
+    pub fn clear(&mut self) {
+        self.0.clear()
+    }
+
+    /// Returns true if the map contains the specified key.
+    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.
+    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.
+    pub fn remove(&mut self, key: &T::Strong) -> bool {
+        self.0.remove(key).is_some()
+    }
+
+    /// Removes all mappings not satisfying the given predicate.
+    ///
+    /// Also removes any expired mappings.
+    pub fn retain<F>(&mut self, mut f: F)
+        where F: FnMut(T::Strong) -> bool
+    {
+        self.0.retain(|k, _| f(k))
+    }
+
+    /// Is self a subset of other?
+    pub fn is_subset<S1>(&self, other: &PtrWeakHashSet<T, S1>) -> bool
+        where S1: BuildHasher
+    {
+        self.0.domain_is_subset(&other.0)
+    }
+}
+
+/// An iterator over the elements of a set.
+pub struct Iter<'a, T: 'a>(base::Keys<'a, ByPtr<T>, ()>);
+
+impl<'a, T: WeakElement> Iterator for Iter<'a, T> {
+    type Item = T::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+/// An iterator over the elements of a set.
+pub struct IntoIter<T>(base::IntoIter<ByPtr<T>, ()>);
+
+impl<T: WeakElement> Iterator for IntoIter<T> {
+    type Item = T::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|pair| pair.0)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+/// A draining iterator over the elements of a set.
+pub struct Drain<'a, T: 'a>(base::Drain<'a, ByPtr<T>, ()>);
+
+impl<'a, T: WeakElement> Iterator for Drain<'a, T> {
+    type Item = T::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|pair| pair.0)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+impl<T: WeakElement, S> PtrWeakHashSet<T, S>
+    where T::Strong: Deref
+{
+    /// Gets an iterator over the keys and values.
+    pub fn iter(&self) -> Iter<T> {
+        Iter(self.0.keys())
+    }
+
+    /// Gets a draining iterator, which removes all the values but retains the storage.
+    pub fn drain(&mut self) -> Drain<T> {
+        Drain(self.0.drain())
+    }
+}
+
+impl<T, S, S1> PartialEq<PtrWeakHashSet<T, S1>> for PtrWeakHashSet<T, S>
+    where T: WeakElement,
+          T::Strong: Deref,
+          S: BuildHasher,
+          S1: BuildHasher
+{
+    fn eq(&self, other: &PtrWeakHashSet<T, S1>) -> bool {
+        self.0 == other.0
+    }
+}
+
+impl<T: WeakElement, S: BuildHasher> Eq for PtrWeakHashSet<T, S>
+    where T::Strong: Deref
+{ }
+
+impl<T: WeakElement, S: BuildHasher + Default> Default for PtrWeakHashSet<T, S>
+    where T::Strong: Deref
+{
+    fn default() -> Self {
+        PtrWeakHashSet(base::PtrWeakKeyHashMap::<T, (), S>::default())
+    }
+}
+
+impl<T, S> FromIterator<T::Strong> for PtrWeakHashSet<T, S>
+    where T: WeakElement,
+          T::Strong: Deref,
+          S: BuildHasher + Default
+{
+    fn from_iter<I: IntoIterator<Item=T::Strong>>(iter: I) -> Self {
+        PtrWeakHashSet(base::PtrWeakKeyHashMap::<T, (), S>::from_iter(
+            iter.into_iter().map(|k| (k, ()))))
+    }
+}
+
+impl<T, S> Extend<T::Strong> for PtrWeakHashSet<T, S>
+    where T: WeakElement,
+          T::Strong: Deref,
+          S: BuildHasher
+{
+    fn extend<I: IntoIterator<Item=T::Strong>>(&mut self, iter: I) {
+        self.0.extend(iter.into_iter().map(|k| (k, ())))
+    }
+}
+
+impl<T, S> Debug for PtrWeakHashSet<T, S>
+    where T: WeakElement,
+          T::Strong: Debug
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl<T: WeakElement, S> IntoIterator for PtrWeakHashSet<T, S> {
+    type Item = T::Strong;
+    type IntoIter = IntoIter<T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter(self.0.into_iter())
+    }
+}
+
+impl<'a, T: WeakElement, S> IntoIterator for &'a PtrWeakHashSet<T, S>
+    where T::Strong: Deref
+{
+    type Item = T::Strong;
+    type IntoIter = Iter<'a, T>;
+
+    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
new file mode 100644
index 0000000..cd48809
--- /dev/null
+++ b/src/ptr_weak_key_hash_map.rs
@@ -0,0 +1,352 @@
+//! A hash map where the keys are held by weak pointers and compared by pointer.
+
+use std::collections::hash_map::RandomState;
+use std::fmt::{self, Debug};
+use std::hash::BuildHasher;
+use std::iter::FromIterator;
+use std::ops::{Deref, Index, IndexMut};
+
+use super::by_ptr::*;
+use super::traits::*;
+use super::weak_key_hash_map as base;
+
+pub use super::PtrWeakKeyHashMap;
+pub use super::weak_key_hash_map::{Entry, Iter, IterMut, Keys, Values, ValuesMut, Drain, IntoIter};
+
+impl <K: WeakElement, V> PtrWeakKeyHashMap<K, V, RandomState>
+    where K::Strong: Deref
+{
+    /// Creates an empty `PtrWeakKeyHashMap`.
+    pub fn new() -> Self {
+        PtrWeakKeyHashMap(base::WeakKeyHashMap::new())
+    }
+
+    /// Creates an empty `PtrWeakKeyHashMap` with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        PtrWeakKeyHashMap(base::WeakKeyHashMap::with_capacity(capacity))
+    }
+}
+
+impl <K: WeakElement, V, S: BuildHasher> PtrWeakKeyHashMap<K, V, S>
+    where K::Strong: Deref
+{
+    /// Creates an empty `PtrWeakKeyHashMap` with the given capacity and hasher.
+    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.
+    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`.
+    pub fn hasher(&self) -> &S {
+        self.0.hasher()
+    }
+
+    /// Returns the number of elements the map can hold without reallocating.
+    pub fn capacity(&self) -> usize {
+        self.0.capacity()
+    }
+
+    /// Removes all mappings whose keys have expired.
+    pub fn remove_expired(&mut self) {
+        self.0.remove_expired()
+    }
+
+    /// Reserves room for additional elements.
+    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.
+    pub fn shrink_to_fit(&mut self) {
+        self.0.shrink_to_fit()
+    }
+
+    /// Returns an over-approximation of the number of elements.
+    pub fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    /// Is the map known to be empty?
+    ///
+    /// This could answer `false` for an empty map whose keys have
+    /// expired but have yet to be collected.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// The proportion of buckets that are used.
+    ///
+    /// This is an over-approximation because of expired keys.
+    pub fn load_factor(&self) -> f32 {
+        self.0.load_factor()
+    }
+
+    /// Gets the requested entry.
+    pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> {
+        self.0.entry(key)
+    }
+
+    /// Removes all associations from the map.
+    pub fn clear(&mut self) {
+        self.0.clear()
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    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.
+    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.
+    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.
+    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.
+    pub fn remove(&mut self, key: &K::Strong) -> Option<V> {
+        self.0.remove(&(key.deref() as *const _))
+    }
+
+    /// Removes all mappings not satisfying the given predicate.
+    ///
+    /// Also removes any expired mappings.
+    pub fn retain<F>(&mut self, f: F)
+        where F: FnMut(K::Strong, &mut V) -> bool
+    {
+        self.0.retain(f)
+    }
+
+    /// Is this map a submap of the other, using the given value comparison.
+    ///
+    /// In particular, all the keys of self must be in other and the values must compare true with
+    /// value_equal.
+    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
+    {
+        self.0.is_submap_with(&other.0, value_equal)
+    }
+
+    /// Is self a submap of other?
+    pub fn is_submap<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool
+        where V: PartialEq<V1>,
+            S1: BuildHasher
+    {
+        self.0.is_submap(&other.0)
+    }
+
+    /// Are the keys of self a subset of the keys of other?
+    pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool
+        where S1: BuildHasher
+    {
+        self.0.domain_is_subset(&other.0)
+    }
+}
+
+impl<K: WeakElement, V, S> PtrWeakKeyHashMap<K, V, S>
+    where K::Strong: Deref
+{
+    /// Gets an iterator over the keys and values.
+    pub fn iter(&self) -> Iter<ByPtr<K>, V> {
+        self.0.iter()
+    }
+
+    /// Gets an iterator over the keys.
+    pub fn keys(&self) -> Keys<ByPtr<K>, V> {
+        self.0.keys()
+    }
+
+    /// Gets an iterator over the values.
+    pub fn values(&self) -> Values<ByPtr<K>, V> {
+        self.0.values()
+    }
+
+    /// Gets an iterator over the keys and mutable values.
+    pub fn iter_mut(&mut self) -> IterMut<ByPtr<K>, V> {
+        self.0.iter_mut()
+    }
+
+    /// Gets an iterator over the mutable values.
+    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.
+    pub fn drain(&mut self) -> Drain<ByPtr<K>, V> {
+        self.0.drain()
+    }
+}
+
+impl<K, V, V1, S, S1> PartialEq<PtrWeakKeyHashMap<K, V1, S1>>
+    for PtrWeakKeyHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Deref,
+          V: PartialEq<V1>,
+          S: BuildHasher,
+          S1: BuildHasher
+{
+    fn eq(&self, other: &PtrWeakKeyHashMap<K, V1, S1>) -> bool {
+        self.0 == other.0
+    }
+}
+
+impl<K: WeakElement, V: Eq, S: BuildHasher> Eq for PtrWeakKeyHashMap<K, V, S>
+    where K::Strong: Deref
+{ }
+
+impl<K: WeakElement, V, S: BuildHasher + Default> Default for PtrWeakKeyHashMap<K, V, S>
+    where K::Strong: Deref
+{
+    fn default() -> Self {
+        PtrWeakKeyHashMap(base::WeakKeyHashMap::<ByPtr<K>, V, S>::default())
+    }
+}
+
+impl<'a, K, V, S> Index<&'a K::Strong> for PtrWeakKeyHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Deref,
+          S: BuildHasher
+{
+    type Output = V;
+
+    fn index(&self, index: &'a K::Strong) -> &Self::Output {
+        self.0.index(&(index.deref() as *const _))
+    }
+}
+
+impl<'a, K, V, S> IndexMut<&'a K::Strong> for PtrWeakKeyHashMap<K, V, S>
+    where
+        K: WeakElement,
+        K::Strong: Deref,
+        S: BuildHasher
+{
+    fn index_mut(&mut self, index: &'a K::Strong) -> &mut Self::Output {
+        self.0.index_mut(&(index.deref() as *const _))
+    }
+}
+
+impl<K, V, S> FromIterator<(K::Strong, V)> for PtrWeakKeyHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Deref,
+          S: BuildHasher + Default
+{
+    fn from_iter<T: IntoIterator<Item=(K::Strong, V)>>(iter: T) -> Self {
+        PtrWeakKeyHashMap(base::WeakKeyHashMap::<ByPtr<K>, V, S>::from_iter(iter))
+    }
+}
+
+impl<K, V, S> Extend<(K::Strong, V)> for PtrWeakKeyHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Deref,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(K::Strong, V)>>(&mut self, iter: T) {
+        self.0.extend(iter)
+    }
+}
+
+impl<'a, K, V, S> Extend<(&'a K::Strong, &'a V)> for PtrWeakKeyHashMap<K, V, S>
+    where K: 'a + WeakElement,
+          K::Strong: Clone + Deref,
+          V: 'a + Clone,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(&'a K::Strong, &'a V)>>(&mut self, iter: T) {
+        self.0.extend(iter)
+    }
+}
+
+impl<K, V: Debug, S> Debug for PtrWeakKeyHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Debug
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl<K: WeakElement, V, S> IntoIterator for PtrWeakKeyHashMap<K, V, S> {
+    type Item = (K::Strong, V);
+    type IntoIter = IntoIter<ByPtr<K>, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.into_iter()
+    }
+}
+
+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>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        (&self.0).into_iter()
+    }
+}
+
+impl<'a, K: WeakElement, V, S> IntoIterator for &'a mut PtrWeakKeyHashMap<K, V, S> {
+    type Item = (K::Strong, &'a mut V);
+    type IntoIter = IterMut<'a, ByPtr<K>, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        (&mut self.0).into_iter()
+    }
+}
+
+#[cfg(test)]
+mod test
+{
+    use crate::PtrWeakKeyHashMap;
+    use crate::weak_key_hash_map::Entry;
+    use std::rc::{Rc, Weak};
+
+//    fn show_me(weakmap: &PtrWeakKeyHashMap<Weak<u32>, f32>) {
+//        for (key, _) in weakmap {
+//            eprint!(" {:2}", *key);
+//        }
+//        eprintln!();
+//    }
+
+    // From https://github.com/tov/weak-table-rs/issues/1#issuecomment-461858060
+    #[test]
+    fn insert_and_check() {
+        let mut rcs: Vec<Rc<u32>> = Vec::new();
+
+        for i in 0 .. 200 {
+            rcs.push(Rc::new(i));
+        }
+
+        let mut weakmap: PtrWeakKeyHashMap<Weak<u32>, f32> = PtrWeakKeyHashMap::new();
+
+        for item in rcs.iter().cloned() {
+            let f = *item as f32 + 0.1;
+            weakmap.insert(item, f);
+        }
+
+        let mut count = 0;
+
+        for item in &rcs {
+            assert!(weakmap.contains_key(item));
+
+            match weakmap.entry(Rc::clone(item)) {
+                Entry::Occupied(_) => count += 1,
+                Entry::Vacant(_) => eprintln!("PointerWeakKeyHashMap: missing: {}", *item),
+            }
+        }
+
+        assert_eq!( count, rcs.len() );
+    }
+}
diff --git a/src/ptr_weak_weak_hash_map.rs b/src/ptr_weak_weak_hash_map.rs
new file mode 100644
index 0000000..e842cd2
--- /dev/null
+++ b/src/ptr_weak_weak_hash_map.rs
@@ -0,0 +1,312 @@
+//! A hash map where the keys and values are both held by weak pointers, and keys are compared by
+//! pointer.
+
+use std::collections::hash_map::RandomState;
+use std::fmt::{self, Debug};
+use std::hash::BuildHasher;
+use std::iter::FromIterator;
+use std::ops::Deref;
+
+use super::by_ptr::*;
+use super::traits::*;
+use super::weak_weak_hash_map as base;
+
+pub use super::PtrWeakWeakHashMap;
+pub use super::weak_weak_hash_map::{Entry, Iter, Keys, Values, Drain, IntoIter};
+
+impl <K: WeakElement, V: WeakElement> PtrWeakWeakHashMap<K, V, RandomState>
+    where K::Strong: Deref
+{
+    /// Creates an empty `PtrWeakWeakHashMap`.
+    pub fn new() -> Self {
+        PtrWeakWeakHashMap(base::WeakWeakHashMap::new())
+    }
+
+    /// Creates an empty `PtrWeakWeakHashMap` with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        PtrWeakWeakHashMap(base::WeakWeakHashMap::with_capacity(capacity))
+    }
+}
+
+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.
+    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.
+    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`.
+    pub fn hasher(&self) -> &S {
+        self.0.hasher()
+    }
+
+    /// Returns the number of elements the map can hold without reallocating.
+    pub fn capacity(&self) -> usize {
+        self.0.capacity()
+    }
+
+    /// Removes all mappings whose keys have expired.
+    pub fn remove_expired(&mut self) {
+        self.0.remove_expired()
+    }
+
+    /// Reserves room for additional elements.
+    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.
+    pub fn shrink_to_fit(&mut self) {
+        self.0.shrink_to_fit()
+    }
+
+    /// Returns an over-approximation of the number of elements.
+    pub fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    /// Is the map empty?
+    ///
+    /// Note that this may return false even if all keys in the map have
+    /// expired, if they haven't been collected yet.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+
+    /// The proportion of buckets that are used.
+    ///
+    /// This is an over-approximation because of expired keys.
+    pub fn load_factor(&self) -> f32 {
+        self.0.load_factor()
+    }
+
+    /// Gets the requested entry.
+    pub fn entry(&mut self, key: K::Strong) -> Entry<ByPtr<K>, V> {
+        self.0.entry(key)
+    }
+
+    /// Removes all associations from the map.
+    pub fn clear(&mut self) {
+        self.0.clear()
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    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.
+    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.
+    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.
+    pub fn remove(&mut self, key: &K::Strong) -> Option<V::Strong> {
+        self.0.remove(&(key.deref() as *const _))
+    }
+
+    /// Removes all mappings not satisfying the given predicate.
+    ///
+    /// Also removes any expired mappings.
+    pub fn retain<F>(&mut self, f: F)
+        where F: FnMut(K::Strong, V::Strong) -> bool
+    {
+        self.0.retain(f)
+    }
+
+    /// Is this map a submap of the other, using the given value comparison.
+    ///
+    /// In particular, all the keys of self must be in other and the values must compare true with
+    /// value_equal.
+    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,
+          S1: BuildHasher
+    {
+        self.0.is_submap_with(&other.0, value_equal)
+    }
+
+    /// Is self a submap of other?
+    pub fn is_submap<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool
+        where V1: WeakElement,
+              V::Strong: PartialEq<V1::Strong>,
+              S1: BuildHasher
+    {
+        self.0.is_submap(&other.0)
+    }
+
+    /// Are the keys of self a subset of the keys of other?
+    pub fn domain_is_subset<V1, S1>(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool
+        where V1: WeakElement,
+              S1: BuildHasher
+    {
+        self.0.domain_is_subset(&other.0)
+    }
+}
+
+impl<K: WeakElement, V: WeakElement, S> PtrWeakWeakHashMap<K, V, S>
+    where K::Strong: Deref
+{
+    /// Gets an iterator over the keys and values.
+    pub fn iter(&self) -> Iter<ByPtr<K>, V> {
+        self.0.iter()
+    }
+
+    /// Gets an iterator over the keys.
+    pub fn keys(&self) -> Keys<ByPtr<K>, V> {
+        self.0.keys()
+    }
+
+    /// Gets an iterator over the values.
+    pub fn values(&self) -> Values<ByPtr<K>, V> {
+        self.0.values()
+    }
+
+    /// Gets a draining iterator, which removes all the values but retains the storage.
+    pub fn drain(&mut self) -> Drain<ByPtr<K>, V> {
+        self.0.drain()
+    }
+}
+
+impl<K, V, V1, S, S1> PartialEq<PtrWeakWeakHashMap<K, V1, S1>>
+    for PtrWeakWeakHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Deref,
+          V: WeakElement,
+          V1: WeakElement,
+          V::Strong: PartialEq<V1::Strong>,
+          S: BuildHasher,
+          S1: BuildHasher
+{
+    fn eq(&self, other: &PtrWeakWeakHashMap<K, V1, S1>) -> bool {
+        self.0 == other.0
+    }
+}
+
+impl<K: WeakElement, V: WeakElement, S: BuildHasher> Eq for PtrWeakWeakHashMap<K, V, S>
+    where K::Strong: Deref,
+          V::Strong: Eq
+{ }
+
+impl<K: WeakElement, V: WeakElement, S: BuildHasher + Default> Default for PtrWeakWeakHashMap<K, V, S>
+    where K::Strong: Deref
+{
+    fn default() -> Self {
+        PtrWeakWeakHashMap(base::WeakWeakHashMap::<ByPtr<K>, V, S>::default())
+    }
+}
+
+impl<K, V, S> FromIterator<(K::Strong, V::Strong)> for PtrWeakWeakHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Deref,
+          V: WeakElement,
+          S: BuildHasher + Default
+{
+    fn from_iter<T: IntoIterator<Item=(K::Strong, V::Strong)>>(iter: T) -> Self {
+        PtrWeakWeakHashMap(base::WeakWeakHashMap::<ByPtr<K>, V, S>::from_iter(iter))
+    }
+}
+
+impl<K, V, S> Extend<(K::Strong, V::Strong)> for PtrWeakWeakHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Deref,
+          V: WeakElement,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(K::Strong, V::Strong)>>(&mut self, iter: T) {
+        self.0.extend(iter)
+    }
+}
+
+impl<K, V, S> Debug for PtrWeakWeakHashMap<K, V, S>
+    where K: WeakElement,
+          K::Strong: Debug,
+          V: WeakElement,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl<K: WeakElement, V: WeakElement, S> IntoIterator for PtrWeakWeakHashMap<K, V, S> {
+    type Item = (K::Strong, V::Strong);
+    type IntoIter = IntoIter<ByPtr<K>, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.into_iter()
+    }
+}
+
+impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a PtrWeakWeakHashMap<K, V, S> {
+    type Item = (K::Strong, V::Strong);
+    type IntoIter = Iter<'a, ByPtr<K>, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        (&self.0).into_iter()
+    }
+}
+
+#[cfg(test)]
+mod test
+{
+    use crate::PtrWeakWeakHashMap;
+    use crate::weak_weak_hash_map::Entry;
+    use std::rc::{Rc, Weak};
+
+//    fn show_me(weakmap: &PtrWeakWeakHashMap<Weak<u32>, Weak<f32>>) {
+//        for (key, _) in weakmap {
+//            eprint!(" {:2}", *key);
+//        }
+//        eprintln!();
+//    }
+
+    // From https://github.com/tov/weak-table-rs/issues/1#issuecomment-461858060
+    #[test]
+    fn insert_and_check() {
+        let mut rcs: Vec<(Rc<u32>, Rc<f32>)> = Vec::new();
+
+        for i in 0 .. 200 {
+            rcs.push((Rc::new(i), Rc::new(i as f32 + 0.1)));
+        }
+
+        let mut weakmap: PtrWeakWeakHashMap<Weak<u32>, Weak<f32>> = PtrWeakWeakHashMap::new();
+
+        for (key, value) in rcs.iter().cloned() {
+            weakmap.insert(key, value);
+//            show_me(&weakmap);
+        }
+
+        let mut count = 0;
+
+        for (key, value) in &rcs {
+            assert!(weakmap.contains_key(key));
+
+            match weakmap.entry(Rc::clone(key)) {
+                Entry::Occupied(occ) => {
+                    assert_eq!( occ.get(), value );
+                    count += 1;
+                }
+                Entry::Vacant(_) => {
+                    eprintln!("PointerWeakWeakHashMap: missing: {}", *key);
+                }
+            }
+        }
+
+        assert_eq!( count, rcs.len() );
+    }
+}
+
+
diff --git a/src/size_policy.rs b/src/size_policy.rs
new file mode 100644
index 0000000..7eb5c6a
--- /dev/null
+++ b/src/size_policy.rs
@@ -0,0 +1,14 @@
+/// No reason for this number as of now.
+pub const DEFAULT_INITIAL_CAPACITY: usize = 8;
+
+/// When the approximate load factor reaches `COLLECT_LOAD_FACTOR`, we remove
+/// all the expired pointers and then consider resizing.
+pub const COLLECT_LOAD_FACTOR: f32 = 0.9;
+
+/// If, after collection, the load factor is above `GROW_LOAD_FACTOR`, we grow.
+pub const GROW_LOAD_FACTOR: f32 = 0.75;
+
+/// If, after collection, the load factor is below `SHRINK_LOAD_FACTOR`, we shrink.
+pub const SHRINK_LOAD_FACTOR: f32 = 0.25;
+
+
diff --git a/src/traits.rs b/src/traits.rs
new file mode 100644
index 0000000..440a6c9
--- /dev/null
+++ b/src/traits.rs
@@ -0,0 +1,127 @@
+//! Traits for describing strong and weak pointers and their use as elements and keys.
+//!
+//! These traits provide mechanisms for converting between weak and strong pointers
+//! ([`WeakElement`](trait.WeakElement.html)) and for dereferencing strong pointers
+//! ([`WeakKey`](trait.WeakKey.html)). Implementations of these traits are provided for
+//! `std::rc::Weak` and `std::sync::Weak`. If you would like to use your own pointer type
+//! as a weak element, you need to implement `WeakElement` for your weak pointer type; to use it
+//! as a weak key, implement `WeakKey` as well.
+
+use std::hash::Hash;
+use std::{rc, sync};
+
+/// Interface for elements that can be stored in weak hash tables.
+///
+/// This trait applies to the weak version of a reference-counted pointer; it can be used to
+/// convert a weak pointer into a strong pointer and back. For example, the impl for
+/// `std::rc::Weak<T>` defines the `Strong` associated type as `std::rc::Rc<T>`. Then method
+/// `new` can be used to downgrade an `Rc<T>` to a `Weak<T>`, and method `view` can be used to
+/// upgrade a `Weak<T>` into an `Rc<T>`, if it's still alive. If we think of the weak pointer as
+/// what is stored, then the strong pointer is a temporary view of it.
+pub trait WeakElement {
+    /// The type at which a weak element can be viewed.
+    ///
+    /// For example, for `std::rc::Weak<T>`, this will be `std::rc::Rc<T>`.
+    type Strong;
+
+    /// Constructs a weak pointer from a strong pointer.
+    ///
+    /// This is usually implemented by a `downgrade` method.
+    fn new(view: &Self::Strong) -> Self;
+
+    /// Acquires a strong pointer from a weak pointer.
+    ///
+    /// This is usually implemented by an `upgrade` method.
+    fn view(&self) -> Option<Self::Strong>;
+
+    /// Is the given weak element expired?
+    ///
+    /// The default implemention checks whether a strong pointer can be obtained via `view`.
+    fn is_expired(&self) -> bool {
+        self.view().is_none()
+    }
+
+    /// Clones a strong pointer.
+    ///
+    /// The default implementation uses `new` and `view`; you should override it.
+    fn clone(view: &Self::Strong) -> Self::Strong
+        where Self: Sized
+    {
+        Self::new(view).view().expect("WeakElement::clone")
+    }
+}
+
+/// Interface for elements that can act as keys in weak hash tables.
+///
+/// To use an element as a weak hash map key or weak hash set element), the hash table
+/// needs to be able to view the actual key values to hash and compare them. This trait
+/// provides the necessary mechanism.
+pub trait WeakKey : WeakElement {
+    /// The underlying key type.
+    ///
+    /// For example, for `std::rc::Weak<T>`, this will be `T`.
+    type Key: ?Sized + Eq + Hash;
+
+    /// Allows borrowing a view of the key, via a callback.
+    ///
+    /// Rather than returning a borrowed reference to the actual key, this method passes a
+    /// reference to the key to a callback with an implicit higher-order lifetime bound. This is
+    /// necessary to get the lifetimes right in cases where the key is not actually store in the
+    /// strong pointer.
+    fn with_key<F, R>(view: &Self::Strong, f: F) -> R
+        where F: FnOnce(&Self::Key) -> R;
+}
+
+impl<T: ?Sized> WeakElement for rc::Weak<T> {
+    type Strong = rc::Rc<T>;
+
+    fn new(view: &Self::Strong) -> Self {
+        rc::Rc::<T>::downgrade(view)
+    }
+
+    fn view(&self) -> Option<Self::Strong> {
+        self.upgrade()
+    }
+
+    fn clone(view: &Self::Strong) -> Self::Strong {
+        view.clone()
+    }
+}
+
+impl<T: ?Sized + Eq + Hash> WeakKey for rc::Weak<T> {
+    type Key = T;
+
+    fn with_key<F, R>(view: &Self::Strong, f: F) -> R
+        where F: FnOnce(&Self::Key) -> R
+    {
+        f(&view)
+    }
+}
+
+impl<T: ?Sized> WeakElement for sync::Weak<T> {
+    type Strong = sync::Arc<T>;
+
+    fn new(view: &Self::Strong) -> Self {
+        sync::Arc::<T>::downgrade(view)
+    }
+
+    fn view(&self) -> Option<Self::Strong> {
+        self.upgrade()
+    }
+
+    fn clone(view: &Self::Strong) -> Self::Strong {
+        view.clone()
+    }
+}
+
+impl<T: ?Sized + Eq + Hash> WeakKey for sync::Weak<T>
+{
+    type Key = T;
+
+    fn with_key<F, R>(view: &Self::Strong, f: F) -> R
+        where F: FnOnce(&Self::Key) -> R
+    {
+        f(&view)
+    }
+}
+
diff --git a/src/util.rs b/src/util.rs
new file mode 100644
index 0000000..3792ec7
--- /dev/null
+++ b/src/util.rs
@@ -0,0 +1,7 @@
+pub fn new_boxed_option_slice<T>(size: usize) -> Box<[Option<T>]> {
+    let mut vector = Vec::with_capacity(size);
+    for _ in 0 .. size {
+        vector.push(None)
+    }
+    vector.into_boxed_slice()
+}
diff --git a/src/weak_hash_set.rs b/src/weak_hash_set.rs
new file mode 100644
index 0000000..a3bc151
--- /dev/null
+++ b/src/weak_hash_set.rs
@@ -0,0 +1,270 @@
+//! A hash set where the elements are held by weak pointers and compared by value.
+
+use std::borrow::Borrow;
+use std::collections::hash_map::RandomState;
+use std::fmt::{self, Debug};
+use std::hash::{BuildHasher, Hash};
+use std::iter::FromIterator;
+
+use super::traits::*;
+use super::weak_key_hash_map as base;
+
+pub use super::WeakHashSet;
+
+impl <T: WeakKey> WeakHashSet<T, RandomState> {
+    /// Creates an empty `WeakHashSet`.
+    pub fn new() -> Self {
+        WeakHashSet(base::WeakKeyHashMap::new())
+    }
+
+    /// Creates an empty `WeakHashSet` with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        WeakHashSet(base::WeakKeyHashMap::with_capacity(capacity))
+    }
+}
+
+impl <T: WeakKey, S: BuildHasher> WeakHashSet<T, S> {
+    /// Creates an empty `WeakHashSet` with the given capacity and hasher.
+    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.
+    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`.
+    pub fn hasher(&self) -> &S {
+        self.0.hasher()
+    }
+
+    /// Returns the number of elements the map can hold without reallocating.
+    pub fn capacity(&self) -> usize {
+        self.0.capacity()
+    }
+
+    /// Removes all mappings whose keys have expired.
+    pub fn remove_expired(&mut self) {
+        self.0.remove_expired()
+    }
+
+    /// Reserves room for additional elements.
+    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.
+    pub fn shrink_to_fit(&mut self) {
+        self.0.shrink_to_fit()
+    }
+
+    /// Returns an over-approximation of the number of elements.
+    pub fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    /// Is the set empty?
+    ///
+    /// Note that this may return false even if all keys in the set have
+    /// expired, if they haven't been collected yet.
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+
+    /// The proportion of buckets that are used.
+    ///
+    /// This is an over-approximation because of expired elements.
+    pub fn load_factor(&self) -> f32 {
+        self.0.load_factor()
+    }
+
+    /// Removes all associations from the map.
+    pub fn clear(&mut self) {
+        self.0.clear()
+    }
+
+    // Non-ptr WeakHashSet should probably have `get` method.
+
+    /// Returns true if the map contains the specified key.
+    pub fn contains<Q>(&self, key: &Q) -> bool
+        where Q: ?Sized + Eq + Hash,
+              T::Key: Borrow<Q>
+    {
+        self.0.contains_key(key)
+    }
+
+    /// Gets a strong reference to the given key, if found.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use weak_table::WeakHashSet;
+    /// use std::rc::{Rc, Weak};
+    /// use std::ops::Deref;
+    ///
+    /// let mut set: WeakHashSet<Weak<String>> = WeakHashSet::new();
+    ///
+    /// let a = Rc::new("a".to_owned());
+    /// set.insert(a.clone());
+    ///
+    /// let also_a = set.get("a").unwrap();
+    ///
+    /// assert!(Rc::ptr_eq( &a, &also_a ));
+    /// ```
+    pub fn get<Q>(&self, key: &Q) -> Option<T::Strong>
+        where Q: ?Sized + Eq + Hash,
+              T::Key: Borrow<Q>
+    {
+        self.0.get_key(key)
+    }
+
+    /// Unconditionally inserts the value, returning the old value if already present. Does not
+    /// replace the key.
+    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.
+    pub fn remove<Q>(&mut self, key: &Q) -> bool
+        where Q: ?Sized + Eq + Hash,
+              T::Key: Borrow<Q>
+    {
+        self.0.remove(key).is_some()
+    }
+
+    /// Removes all mappings not satisfying the given predicate.
+    ///
+    /// Also removes any expired mappings.
+    pub fn retain<F>(&mut self, mut f: F)
+        where F: FnMut(T::Strong) -> bool
+    {
+        self.0.retain(|k, _| f(k))
+    }
+
+    /// Is self a subset of other?
+    pub fn is_subset<S1>(&self, other: &WeakHashSet<T, S1>) -> bool
+        where S1: BuildHasher
+    {
+        self.0.domain_is_subset(&other.0)
+    }
+}
+
+/// An iterator over the elements of a set.
+pub struct Iter<'a, T: 'a>(base::Keys<'a, T, ()>);
+
+impl<'a, T: WeakElement> Iterator for Iter<'a, T> {
+    type Item = T::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+/// An iterator over the elements of a set.
+pub struct IntoIter<T>(base::IntoIter<T, ()>);
+
+impl<T: WeakElement> Iterator for IntoIter<T> {
+    type Item = T::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|pair| pair.0)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+/// A draining iterator over the elements of a set.
+pub struct Drain<'a, T: 'a>(base::Drain<'a, T, ()>);
+
+impl<'a, T: WeakElement> Iterator for Drain<'a, T> {
+    type Item = T::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|pair| pair.0)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+impl<T: WeakKey, S> WeakHashSet<T, S> {
+    /// Gets an iterator over the keys and values.
+    pub fn iter(&self) -> Iter<T> {
+        Iter(self.0.keys())
+    }
+
+    /// Gets a draining iterator, which removes all the values but retains the storage.
+    pub fn drain(&mut self) -> Drain<T> {
+        Drain(self.0.drain())
+    }
+}
+
+impl<T, S, S1> PartialEq<WeakHashSet<T, S1>> for WeakHashSet<T, S>
+    where T: WeakKey,
+          S: BuildHasher,
+          S1: BuildHasher
+{
+    fn eq(&self, other: &WeakHashSet<T, S1>) -> bool {
+        self.0 == other.0
+    }
+}
+
+impl<T: WeakKey, S: BuildHasher> Eq for WeakHashSet<T, S>
+    where T::Key: Eq
+{ }
+
+impl<T: WeakKey, S: BuildHasher + Default> Default for WeakHashSet<T, S> {
+    fn default() -> Self {
+        WeakHashSet(base::WeakKeyHashMap::<T, (), S>::default())
+    }
+}
+
+impl<T, S> FromIterator<T::Strong> for WeakHashSet<T, S>
+    where T: WeakKey,
+          S: BuildHasher + Default
+{
+    fn from_iter<I: IntoIterator<Item=T::Strong>>(iter: I) -> Self {
+        WeakHashSet(base::WeakKeyHashMap::<T, (), S>::from_iter(
+            iter.into_iter().map(|k| (k, ()))))
+    }
+}
+
+impl<T: WeakKey, S: BuildHasher> Extend<T::Strong> for WeakHashSet<T, S> {
+    fn extend<I: IntoIterator<Item=T::Strong>>(&mut self, iter: I) {
+        self.0.extend(iter.into_iter().map(|k| (k, ())))
+    }
+}
+
+impl<T: WeakKey, S> Debug for WeakHashSet<T, S>
+    where T::Strong: Debug
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl<T: WeakKey, S> IntoIterator for WeakHashSet<T, S> {
+    type Item = T::Strong;
+    type IntoIter = IntoIter<T>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter(self.0.into_iter())
+    }
+}
+
+impl<'a, T: WeakKey, S> IntoIterator for &'a WeakHashSet<T, S> {
+    type Item = T::Strong;
+    type IntoIter = Iter<'a, T>;
+
+    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
new file mode 100644
index 0000000..91bee2a
--- /dev/null
+++ b/src/weak_key_hash_map.rs
@@ -0,0 +1,1063 @@
+//! 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::*;
+use super::util::*;
+
+pub use super::WeakKeyHashMap;
+
+/// Represents an entry in the table which may be occupied or vacant.
+pub enum Entry<'a, K: 'a + WeakKey, V: 'a> {
+    Occupied(OccupiedEntry<'a, K, V>),
+    Vacant(VacantEntry<'a, K, V>),
+}
+
+/// An occupied entry, which can be removed or viewed.
+pub struct OccupiedEntry<'a, K: 'a + WeakKey, V: 'a>(InnerEntry<'a, K, V>);
+
+/// A vacant entry, which can be inserted in or viewed.
+pub struct VacantEntry<'a, K: 'a + WeakKey, V: 'a>(InnerEntry<'a, K, V>);
+
+struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> {
+    map:        &'a mut WeakKeyInnerMap<K, V>,
+    pos:        usize,
+    key:        K::Strong,
+    hash_code:  HashCode,
+}
+
+/// An iterator over the keys and values of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Iter<'a, K: 'a, V: 'a> {
+    base: ::std::slice::Iter<'a, Bucket<K, V>>,
+    size: usize,
+}
+
+impl<'a, K: WeakElement, V> Iterator for Iter<'a, K, V> {
+    type Item = (K::Strong, &'a V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((ref weak_ptr, ref value, _)) = *bucket {
+                self.size -= 1;
+                if let Some(strong_ptr) = weak_ptr.view() {
+                    return Some((strong_ptr, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+#[derive(Debug)]
+/// An iterator over the keys and mutable values of the weak hash map.
+pub struct IterMut<'a, K: 'a, V: 'a> {
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    size: usize,
+}
+
+impl<'a, K: WeakElement, V> Iterator for IterMut<'a, K, V> {
+    type Item = (K::Strong, &'a mut V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((ref weak_ptr, ref mut value, _)) = *bucket {
+                self.size -= 1;
+                if let Some(strong_ptr) = weak_ptr.view() {
+                    return Some((strong_ptr, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+/// An iterator over the keys of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
+
+impl<'a, K: WeakElement, V> Iterator for Keys<'a, K, V> {
+    type Item = K::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(k, _)| k)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+/// An iterator over the values of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
+
+impl<'a, K: WeakElement, V> Iterator for Values<'a, K, V> {
+    type Item = &'a V;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(_, v)| v)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+#[derive(Debug)]
+/// An iterator over the mutable values of the weak hash map.
+pub struct ValuesMut<'a, K: 'a, V: 'a>(IterMut<'a, K, V>);
+
+impl<'a, K: WeakElement, V> Iterator for ValuesMut<'a, K, V> {
+    type Item = &'a mut V;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(_, v)| v)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+#[derive(Debug)]
+/// An iterator that consumes the values of a weak hash map, leaving it empty.
+pub struct Drain<'a, K: 'a, V: 'a> {
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    size: usize,
+}
+
+impl<'a, K: WeakElement, V> Iterator for Drain<'a, K, V> {
+    type Item = (K::Strong, V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((weak_ptr, value, _)) = bucket.take() {
+                self.size -= 1;
+                if let Some(strong_ptr) = weak_ptr.view() {
+                    return Some((strong_ptr, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+impl<'a, K, V> Drop for Drain<'a, K, V> {
+    fn drop(&mut self) {
+        while let Some(option) = self.base.next() {
+            *option = None;
+        }
+    }
+}
+
+/// An iterator that consumes the values of a weak hash map, leaving it empty.
+pub struct IntoIter<K, V> {
+    base: ::std::vec::IntoIter<Bucket<K, V>>,
+    size: usize,
+}
+
+impl<K: WeakElement, V> Iterator for IntoIter<K, V> {
+    type Item = (K::Strong, V);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((weak_ptr, value, _)) = bucket {
+                self.size -= 1;
+                if let Some(strong_ptr) = weak_ptr.view() {
+                    return Some((strong_ptr, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+impl<K: WeakKey, V> WeakKeyHashMap<K, V, RandomState>
+{
+    /// Creates an empty `WeakKeyHashMap`.
+    pub fn new() -> Self {
+        Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
+    }
+
+    /// Creates an empty `WeakKeyHashMap` with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self::with_capacity_and_hasher(capacity, Default::default())
+    }
+}
+
+impl<K: WeakKey, V, S: BuildHasher> WeakKeyHashMap<K, V, S>
+{
+    /// Creates an empty `WeakKeyHashMap` with the given capacity and hasher.
+    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.
+    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
+        WeakKeyHashMap {
+            hash_builder,
+            inner: WeakKeyInnerMap {
+                buckets: new_boxed_option_slice(capacity),
+                len: 0,
+            }
+        }
+    }
+
+    /// Returns a reference to the map's `BuildHasher`.
+    pub fn hasher(&self) -> &S {
+        &self.hash_builder
+    }
+
+    /// Returns the number of elements the map can hold without reallocating.
+    pub fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+
+    /// This has some preconditions.
+    fn resize(&mut self, capacity: usize) {
+        let old_buckets = mem::replace(&mut self.inner.buckets,
+                                       new_boxed_option_slice(capacity));
+
+        let iter = IntoIter {
+            base: old_buckets.into_vec().into_iter(),
+            size: self.inner.len,
+        };
+
+        self.inner.len = 0;
+
+        for (key, value) in iter {
+            self.entry_no_grow(key).or_insert(value);
+        }
+    }
+
+    /// Removes all mappings whose keys have expired.
+    pub fn remove_expired(&mut self) {
+        self.retain(|_, _| true)
+    }
+
+    /// Reserves room for additional elements.
+    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.
+    pub fn shrink_to_fit(&mut self) {
+        self.remove_expired();
+        let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
+        self.resize(new_capacity);
+    }
+
+    /// Returns an over-approximation of the number of elements.
+    pub fn len(&self) -> usize {
+        self.inner.len
+    }
+
+    /// Is the map empty?
+    ///
+    /// Note that this may return false even if all keys in the map have
+    /// expired, if they haven't been collected yet.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// The proportion of buckets that are used.
+    ///
+    /// This is an over-approximation because of expired keys.
+    pub fn load_factor(&self) -> f32 {
+        (self.len() as f32 + 1.0) / self.capacity() as f32
+    }
+
+    fn maybe_adjust_size(&mut self) {
+        if self.load_factor() > COLLECT_LOAD_FACTOR {
+            self.remove_expired();
+
+            let load_factor = self.load_factor();
+            let capacity = self.capacity();
+            if load_factor > GROW_LOAD_FACTOR {
+                self.resize(max(1, capacity * 2));
+            } else if load_factor < SHRINK_LOAD_FACTOR && capacity > DEFAULT_INITIAL_CAPACITY {
+                self.resize(max(1, capacity / 2));
+            }
+        }
+    }
+
+    /// Gets the requested entry.
+    pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
+        self.maybe_adjust_size();
+        self.entry_no_grow(key)
+    }
+
+    fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
+        let mut inner = {
+            let hash_code = K::with_key(&key, |k| self.hash(k));
+            InnerEntry {
+                pos:        self.which_bucket(hash_code),
+                map:        &mut self.inner,
+                hash_code,
+                key,
+            }
+        };
+
+        for dist in 0 .. inner.capacity() {
+            match inner.bucket_status() {
+                BucketStatus::Unoccupied =>
+                    return Entry::Vacant(VacantEntry(inner)),
+                BucketStatus::MatchesKey =>
+                    return Entry::Occupied(OccupiedEntry(inner)),
+                BucketStatus::ProbeDistance(bucket_distance) => {
+                    if bucket_distance < dist {
+                        return Entry::Vacant(VacantEntry(inner))
+                    } else {
+                        inner.pos = inner.next_bucket(inner.pos);
+                    }
+                }
+            }
+        }
+
+        panic!("WeakKeyHashTable::entry: out of space");
+    }
+
+    /// Removes all associations from the map.
+    pub fn clear(&mut self) {
+        self.drain();
+    }
+
+    fn find_bucket<Q>(&self, key: &Q) -> Option<(usize, K::Strong, HashCode)>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        if self.capacity() == 0 { return None; }
+
+        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::with_key(&bucket_key, |k| k.borrow() == key) {
+                            return Some((pos, bucket_key, bucket_hash_code));
+                        }
+                    }
+                }
+
+                let bucket_dist =
+                    self.probe_distance(pos, self.which_bucket(bucket_hash_code));
+                if bucket_dist < dist {
+                    return None;
+                }
+            } else {
+                return None;
+            }
+
+            pos = self.next_bucket(pos);
+        }
+
+        None
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    pub fn get<Q>(&self, key: &Q) -> Option<&V>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).and_then(move |tup|
+            self.inner.buckets[tup.0].as_ref().map(|bucket| &bucket.1))
+    }
+
+    /// Returns true if the map contains the specified key.
+    pub fn contains_key<Q>(&self, key: &Q) -> bool
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).is_some()
+    }
+
+    /// Returns a strong reference to the key, if found.
+    pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).map(|tup| tup.1)
+    }
+
+    /// Returns a pair of a strong reference to the key, and a reference to the value, if present.
+    pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, &V)>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).and_then(move |tup|
+            self.inner.buckets[tup.0].as_ref().map(|bucket| (tup.1, &bucket.1)))
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).and_then(move |tup|
+            self.inner.buckets[tup.0].as_mut().map(|bucket| &mut bucket.1))
+    }
+
+    /// Returns a pair of a strong reference to the key, and a mutable reference to the value,
+    /// if present.
+    pub fn get_both_mut<Q>(&mut self, key: &Q) -> Option<(K::Strong, &mut V)>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).and_then(move |tup|
+            self.inner.buckets[tup.0].as_mut().map(|bucket| (tup.1, &mut bucket.1)))
+    }
+
+    /// Unconditionally inserts the value, returning the old value if already present.
+    ///
+    /// Unlike `std::collections::HashMap`, this replaced the key even if occupied.
+    pub fn insert(&mut self, key: K::Strong, value: V) -> Option<V> {
+        match self.entry(key) {
+            Entry::Occupied(mut occupied) => {
+                Some(occupied.insert(value))
+            },
+            Entry::Vacant(vacant) => {
+                vacant.insert(value);
+                None
+            }
+        }
+    }
+
+    /// Removes the entry with the given key, if it exists, and returns the value.
+    pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).map(|(pos, strong_key, hash_code)| {
+            OccupiedEntry(InnerEntry {
+                map:        &mut self.inner,
+                pos,
+                key:        strong_key,
+                hash_code,
+            }).remove()
+        })
+    }
+
+    /// Removes all mappings not satisfying the given predicate.
+    ///
+    /// Also removes any expired mappings.
+    pub fn retain<F>(&mut self, mut f: F)
+        where F: FnMut(K::Strong, &mut V) -> bool
+    {
+        for i in 0 .. self.capacity() {
+            let remove = match self.inner.buckets[i] {
+                None => false,
+                Some(ref mut bucket) =>
+                    match bucket.0.view() {
+                        None => true,
+                        Some(key) => !f(key, &mut bucket.1),
+                    }
+            };
+
+            if remove {
+                self.inner.remove_index(i);
+            }
+        }
+    }
+
+    /// Is this map a submap of the other, using the given value comparison.
+    ///
+    /// 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 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 !value_equal(value1, value2) {
+                    return false;
+                }
+            } else {
+                return false;
+            }
+        }
+
+        true
+    }
+
+    /// Is `self` a submap of `other`?
+    pub fn is_submap<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
+        where V: PartialEq<V1>,
+              S1: BuildHasher
+    {
+        self.is_submap_with(other, PartialEq::eq)
+    }
+
+    /// Are the keys of `self` a subset of the keys of `other`?
+    pub fn domain_is_subset<V1, S1>(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool
+        where S1: BuildHasher
+    {
+        self.is_submap_with(other, |_, _| true)
+    }
+
+    fn hash<Q>(&self, key: &Q) -> HashCode
+        where Q: ?Sized + Hash,
+              K::Key: Borrow<Q>
+    {
+        let mut hasher = self.hash_builder.build_hasher();
+        key.hash(&mut hasher);
+        HashCode(hasher.finish())
+    }
+}
+
+impl<K, V, V1, S, S1> PartialEq<WeakKeyHashMap<K, V1, S1>> for WeakKeyHashMap<K, V, S>
+    where K: WeakKey,
+          V: PartialEq<V1>,
+          S: BuildHasher,
+          S1: BuildHasher
+{
+    fn eq(&self, other: &WeakKeyHashMap<K, V1, S1>) -> bool {
+        self.is_submap(other) && other.domain_is_subset(self)
+    }
+}
+
+impl<K: WeakKey, V: Eq, S: BuildHasher> Eq for WeakKeyHashMap<K, V, S> { }
+
+impl<K: WeakKey, V, S: BuildHasher + Default> Default for WeakKeyHashMap<K, V, S> {
+    fn default() -> Self {
+        WeakKeyHashMap::with_hasher(Default::default())
+    }
+}
+
+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,
+          Q: ?Sized + Eq + Hash
+{
+    type Output = V;
+
+    fn index(&self, index: &'a Q) -> &Self::Output {
+        self.get(index).expect("Index::index: key not found")
+    }
+}
+
+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,
+          Q: ?Sized + Eq + Hash
+{
+    fn index_mut(&mut self, index: &'a Q) -> &mut Self::Output {
+        self.get_mut(index).expect("IndexMut::index_mut: key not found")
+    }
+}
+
+impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+    where K: WeakKey,
+          S: BuildHasher + Default
+{
+    fn from_iter<T: IntoIterator<Item=(K::Strong, V)>>(iter: T) -> Self {
+        let mut result = WeakKeyHashMap::with_hasher(Default::default());
+        result.extend(iter);
+        result
+    }
+}
+
+impl<K, V, S> ::std::iter::Extend<(K::Strong, V)> for WeakKeyHashMap<K, V, S>
+    where K: WeakKey,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(K::Strong, V)>>(&mut self, iter: T) {
+        for (key, value) in iter {
+            self.insert(key, value);
+        }
+    }
+}
+
+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,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(&'a K::Strong, &'a V)>>(&mut self, iter: T) {
+        for (key, value) in iter {
+            self.insert(key.clone(), value.clone());
+        }
+    }
+}
+
+enum BucketStatus {
+    Unoccupied,
+    MatchesKey,
+    ProbeDistance(usize),
+}
+
+impl<'a, K: WeakKey, V> InnerEntry<'a, K, V> {
+    // Gets the status of the current bucket.
+    fn bucket_status(&self) -> BucketStatus {
+        match &self.map.buckets[self.pos] {
+            Some(bucket) => {
+                if bucket.2 == self.hash_code {
+                    if let Some(key) = bucket.0.view() {
+                        if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
+                            return BucketStatus::MatchesKey;
+                        }
+                    }
+                }
+
+                let dist = self.probe_distance(self.pos,
+                                               self.which_bucket(bucket.2));
+                BucketStatus::ProbeDistance(dist)
+            },
+            None => BucketStatus::Unoccupied,
+        }
+    }
+}
+
+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.
+    pub fn or_insert(self, default: V) -> &'a mut V {
+        self.or_insert_with(|| default)
+    }
+
+    /// 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.
+    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
+        match self {
+            Entry::Occupied(occupied) => occupied.into_mut(),
+            Entry::Vacant(vacant) => vacant.insert(default()),
+        }
+    }
+
+    /// Returns a reference to this entry's key.
+    pub fn key(&self) -> &K::Strong {
+        match *self {
+            Entry::Occupied(ref occupied) => occupied.key(),
+            Entry::Vacant(ref vacant) => vacant.key(),
+        }
+    }
+}
+
+impl<'a, K: WeakKey, V> OccupiedEntry<'a, K, V> {
+    /// Gets a reference to the key held by the entry.
+    pub fn key(&self) -> &K::Strong {
+        &self.0.key
+    }
+
+    /// Takes ownership of the key and value from the map.
+    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);
+        (self.0.key, value)
+    }
+
+    /// Gets a reference to the value in the entry.
+    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.
+    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.
+    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.
+    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);
+        value
+    }
+
+    /// Removes the entry, returning the value.
+    pub fn remove(self) -> V {
+        self.remove_entry().1
+    }
+}
+
+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`.
+    pub fn key(&self) -> &K::Strong {
+        &self.0.key
+    }
+
+    /// Returns ownership of the key.
+    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.
+    pub fn insert(self, value: V) -> &'a mut V {
+        let old_bucket = mem::replace(
+            &mut self.0.map.buckets[self.0.pos],
+            Some((K::new(&self.0.key), value, self.0.hash_code)));
+
+        if let Some(full_bucket) = old_bucket {
+            let next_bucket = self.next_bucket(self.0.pos);
+            self.0.map.steal(next_bucket, full_bucket);
+        }
+
+        self.0.map.len += 1;
+
+        &mut self.0.map.buckets[self.0.pos].as_mut().unwrap().1
+    }
+}
+
+impl<K: WeakKey, V> WeakKeyInnerMap<K, V> {
+    // Steals buckets starting at `pos`, replacing them with `bucket`.
+    fn steal(&mut self, mut pos: usize, mut bucket: FullBucket<K, V>) {
+        let mut my_dist = self.probe_distance(pos, self.which_bucket(bucket.2));
+
+        while let Some(hash_code) = self.buckets[pos].as_ref().and_then(
+            |bucket| if bucket.0.is_expired() {None} else {Some(bucket.2)}) {
+
+            let victim_dist = self.probe_distance(pos, self.which_bucket(hash_code));
+
+            if my_dist > victim_dist {
+                mem::swap(self.buckets[pos].as_mut().unwrap(), &mut bucket);
+                my_dist = victim_dist;
+            }
+
+            pos = self.next_bucket(pos);
+            my_dist += 1;
+        }
+
+        self.buckets[pos] = Some(bucket);
+    }
+
+    /// Removes the element at `dst`, shifting if necessary to preserve invariants.
+    fn remove_index(&mut self, mut dst: usize) {
+        let mut src = self.next_bucket(dst);
+
+        // We are going to remove the buckets in the range [dst, src)
+
+        loop {
+            let hash_code_option = self.buckets[src].as_ref().map(|tup| tup.2);
+
+            if let Some(hash_code) = hash_code_option {
+                let goal_pos = self.which_bucket(hash_code);
+                let dist = self.probe_distance(src, goal_pos);
+                if dist == 0 { break; }
+
+                if !self.buckets[src].as_ref().unwrap().0.is_expired() {
+                    if in_interval(dst, goal_pos, src) {
+                        self.erase_range(dst, goal_pos);
+                        self.buckets[goal_pos] = self.buckets[src].take();
+                        dst = self.next_bucket(goal_pos);
+                    } else {
+                        self.buckets[dst] = self.buckets[src].take();
+                        dst = self.next_bucket(dst);
+                    }
+                }
+            } else {
+                break;
+            }
+
+            src = self.next_bucket(src);
+        }
+
+        self.erase_range(dst, src);
+    }
+
+    /// Erases the (presumably expired, but not empty) elements in [start, limit).
+    fn erase_range(&mut self, mut start: usize, limit: usize)
+    {
+        while start != limit {
+            self.buckets[start] = None;
+            self.len -= 1;
+            start = self.next_bucket(start);
+        }
+    }
+}
+
+// Is value in [start, limit) modulo capacity?
+fn in_interval(start: usize, value: usize, limit: usize) -> bool
+{
+    if start <= limit {
+        start <= value && value < limit
+    } else {
+        start <= value || value < limit
+    }
+}
+
+// Helper trait for computing with indices modulo capacity.
+trait ModuloCapacity {
+    fn capacity(&self) -> usize;
+
+    fn probe_distance(&self, actual: usize, ideal: usize) -> usize {
+        if actual >= ideal {
+            actual - ideal
+        } else {
+            actual + self.capacity() - ideal
+        }
+    }
+
+    fn next_bucket(&self, pos: usize) -> usize {
+        assert_ne!( self.capacity(), 0 );
+        (pos + 1) % self.capacity()
+    }
+
+    fn which_bucket(&self, hash_code: HashCode) -> usize {
+        assert_ne!( self.capacity(), 0 );
+        (hash_code.0 as usize) % self.capacity()
+    }
+}
+
+impl<K, V> ModuloCapacity for WeakKeyInnerMap<K, V> {
+    fn capacity(&self) -> usize {
+        self.buckets.len()
+    }
+}
+
+impl<K, V, S> ModuloCapacity for WeakKeyHashMap<K, V, S> {
+    fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+}
+
+impl<'a, K: WeakKey, V> ModuloCapacity for InnerEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.map.capacity()
+    }
+}
+
+impl<'a, K: WeakKey, V> ModuloCapacity for OccupiedEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.0.capacity()
+    }
+}
+
+impl<'a, K: WeakKey, V> ModuloCapacity for VacantEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.0.capacity()
+    }
+}
+
+impl<K, V> Debug for WeakKeyInnerMap<K, V>
+    where K: WeakElement,
+          K::Strong: Debug,
+          V: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "{{ ")?;
+        for (i, bucket) in self.buckets.iter().enumerate() {
+            if let Some((ref k, ref v, _)) = *bucket {
+                write!(f, "[{}] {:?} => {:?}, ", i, k.view(), *v)?;
+            }
+        }
+        write!(f, "}}")
+    }
+}
+
+impl<K: WeakElement, V: Debug, S> Debug for WeakKeyHashMap<K, V, S>
+    where K::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K: WeakKey, V: Debug> Debug for Entry<'a, K, V>
+    where K::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        match *self {
+            Entry::Occupied(ref e)  => e.fmt(f),
+            Entry::Vacant(ref e)    => e.fmt(f),
+        }
+    }
+}
+
+impl<'a, K: WeakKey, V: Debug> Debug for OccupiedEntry<'a, K, V>
+    where K::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl<'a, K: WeakKey, V: Debug> Debug for VacantEntry<'a, K, V>
+    where K::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl<'a, K: WeakKey, V: Debug> Debug for InnerEntry<'a, K, V>
+    where K::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "InnerEntry {{ pos = {}, buckets = {:?} }}", self.pos, self.map)
+    }
+}
+
+impl<K: WeakElement, V, S> IntoIterator for WeakKeyHashMap<K, V, S> {
+    type Item = (K::Strong, V);
+    type IntoIter = IntoIter<K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            size: self.inner.len,
+            base: self.inner.buckets.into_vec().into_iter(),
+        }
+    }
+}
+
+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>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        Iter {
+            base: self.inner.buckets.iter(),
+            size: self.inner.len,
+        }
+    }
+}
+
+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>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IterMut {
+            base: self.inner.buckets.iter_mut(),
+            size: self.inner.len,
+        }
+    }
+}
+
+impl<K: WeakElement, V, S> WeakKeyHashMap<K, V, S> {
+    /// Gets an iterator over the keys and values.
+    pub fn iter(&self) -> Iter<K, V> {
+        self.into_iter()
+    }
+
+    /// Gets an iterator over the keys.
+    pub fn keys(&self) -> Keys<K, V> {
+        Keys(self.iter())
+    }
+
+    /// Gets an iterator over the values.
+    pub fn values(&self) -> Values<K, V> {
+        Values(self.iter())
+    }
+
+    /// Gets an iterator over the keys and mutable values.
+    pub fn iter_mut(&mut self) -> IterMut<K, V> {
+        self.into_iter()
+    }
+
+    /// Gets an iterator over the mutable values.
+    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.
+    pub fn drain(&mut self) -> Drain<K, V> {
+        let old_len = self.inner.len;
+        self.inner.len = 0;
+        Drain {
+            base: self.inner.buckets.iter_mut(),
+            size: old_len,
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use std::rc::{Rc, Weak};
+    use super::{Entry, WeakKeyHashMap};
+
+    #[test]
+    fn simple() {
+        let mut map: WeakKeyHashMap<Weak<str>, usize> = WeakKeyHashMap::new();
+        assert_eq!( map.len(), 0 );
+        assert!( !map.contains_key("five") );
+
+        let five: Rc<str> = Rc::from("five".to_string());
+        map.insert(five.clone(), 5);
+
+        assert_eq!( map.len(), 1 );
+        assert!( map.contains_key("five") );
+
+        drop(five);
+
+        assert_eq!( map.len(), 1 );
+        assert!( !map.contains_key("five") );
+
+        map.remove_expired();
+
+        assert_eq!( map.len(), 0 );
+        assert!( !map.contains_key("five") );
+    }
+
+    // From https://github.com/tov/weak-table-rs/issues/1#issuecomment-461858060
+    #[test]
+    fn insert_and_check() {
+        let mut rcs: Vec<Rc<u32>> = Vec::new();
+
+        for i in 0 .. 50 {
+            rcs.push(Rc::new(i));
+        }
+
+        let mut weakmap: WeakKeyHashMap<Weak<u32>, f32> = WeakKeyHashMap::new();
+
+        for key in rcs.iter().cloned() {
+            let f = *key as f32 + 0.1;
+            weakmap.insert(key, f);
+        }
+
+        let mut count = 0;
+
+        for key in &rcs {
+            assert_eq!(weakmap.get(key), Some(&(**key as f32 + 0.1)));
+
+            match weakmap.entry(Rc::clone(key)) {
+                Entry::Occupied(_) => count += 1,
+                Entry::Vacant(_) => eprintln!("WeakKeyHashMap: missing: {}", *key),
+            }
+        }
+
+        assert_eq!( count, rcs.len() );
+    }
+}
diff --git a/src/weak_value_hash_map.rs b/src/weak_value_hash_map.rs
new file mode 100644
index 0000000..8b60a17
--- /dev/null
+++ b/src/weak_value_hash_map.rs
@@ -0,0 +1,886 @@
+//! 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::*;
+use super::util::*;
+
+pub use super::WeakValueHashMap;
+
+/// Represents an entry in the table which may be occupied or vacant.
+pub enum Entry<'a, K: 'a, V: 'a + WeakElement> {
+    Occupied(OccupiedEntry<'a, K, V>),
+    Vacant(VacantEntry<'a, K, V>),
+}
+
+/// An occupied entry, which can be removed or viewed.
+pub struct OccupiedEntry<'a, K: 'a, V: 'a + WeakElement> {
+    inner: InnerEntry<'a, K, V>,
+    value: V::Strong,
+}
+
+/// A vacant entry, which can be inserted in or viewed.
+pub struct VacantEntry<'a, K: 'a, V: 'a + WeakElement> {
+    inner: InnerEntry<'a, K, V>,
+}
+
+struct InnerEntry<'a, K: 'a, V: 'a + WeakElement> {
+    map:        &'a mut WeakValueInnerMap<K, V>,
+    pos:        usize,
+    key:        K,
+    hash_code:  HashCode,
+}
+
+/// An iterator over the keys and values of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Iter<'a, K: 'a, V: 'a> {
+    base: ::std::slice::Iter<'a, Bucket<K, V>>,
+    size: usize,
+}
+
+impl<'a, K, V: WeakElement> Iterator for Iter<'a, K, V> {
+    type Item = (&'a K, V::Strong);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((ref key, ref weak_value, _)) = *bucket {
+                self.size -= 1;
+                if let Some(value) = weak_value.view() {
+                    return Some((key, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+/// An iterator over the keys of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
+
+impl<'a, K, V: WeakElement> Iterator for Keys<'a, K, V> {
+    type Item = &'a K;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(k, _)| k)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+/// An iterator over the values of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
+
+impl<'a, K, V: WeakElement> Iterator for Values<'a, K, V> {
+    type Item = V::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(_, v)| v)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+#[derive(Debug)]
+/// An iterator that consumes the values of a weak hash map, leaving it empty.
+pub struct Drain<'a, K: 'a, V: 'a> {
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    size: usize,
+}
+
+impl<'a, K, V: WeakElement> Iterator for Drain<'a, K, V> {
+    type Item = (K, V::Strong);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((key, weak_value, _)) = bucket.take() {
+                self.size -= 1;
+                if let Some(value) = weak_value.view() {
+                    return Some((key, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+impl<'a, K, V> Drop for Drain<'a, K, V> {
+    fn drop(&mut self) {
+        while let Some(option) = self.base.next() {
+            *option = None;
+        }
+    }
+}
+
+/// An iterator that consumes the values of a weak hash map, leaving it empty.
+pub struct IntoIter<K, V> {
+    base: ::std::vec::IntoIter<Bucket<K, V>>,
+    size: usize,
+}
+
+impl<K, V: WeakElement> Iterator for IntoIter<K, V> {
+    type Item = (K, V::Strong);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((key, weak_value, _)) = bucket {
+                self.size -= 1;
+                if let Some(value) = weak_value.view() {
+                    return Some((key, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+impl<K: Eq + Hash, V: WeakElement> WeakValueHashMap<K, V, RandomState>
+{
+    /// Creates an empty `WeakValueHashMap`.
+    pub fn new() -> Self {
+        Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
+    }
+
+    /// Creates an empty `WeakValueHashMap` with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self::with_capacity_and_hasher(capacity, Default::default())
+    }
+}
+
+impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> WeakValueHashMap<K, V, S>
+{
+    /// Creates an empty `WeakValueHashMap` with the given capacity and hasher.
+    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.
+    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
+        WeakValueHashMap {
+            hash_builder,
+            inner: WeakValueInnerMap {
+                buckets: new_boxed_option_slice(capacity),
+                len: 0,
+            }
+        }
+    }
+
+    /// Returns a reference to the map's `BuildHasher`.
+    pub fn hasher(&self) -> &S {
+        &self.hash_builder
+    }
+
+    /// Returns the number of elements the map can hold without reallocating.
+    pub fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+
+    /// This has some preconditions.
+    fn resize(&mut self, capacity: usize) {
+        let old_buckets = mem::replace(&mut self.inner.buckets,
+                                       new_boxed_option_slice(capacity));
+
+        let iter = IntoIter {
+            base: old_buckets.into_vec().into_iter(),
+            size: self.inner.len,
+        };
+
+        self.inner.len = 0;
+
+        for (key, value) in iter {
+            self.entry_no_grow(key).or_insert(value);
+        }
+    }
+
+    /// Removes all mappings whose keys have expired.
+    pub fn remove_expired(&mut self) {
+        self.retain(|_, _| true)
+    }
+
+    /// Reserves room for additional elements.
+    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.
+    pub fn shrink_to_fit(&mut self) {
+        self.remove_expired();
+        let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
+        self.resize(new_capacity);
+    }
+
+    /// Returns an over-approximation of the number of elements.
+    pub fn len(&self) -> usize {
+        self.inner.len
+    }
+
+    /// Is the map empty?
+    ///
+    /// Note that this may return false even if all keys in the map have
+    /// expired, if they haven't been collected yet.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// The proportion of buckets that are used.
+    ///
+    /// This is an over-approximation because of expired keys.
+    pub fn load_factor(&self) -> f32 {
+        (self.len() as f32 + 1.0) / self.capacity() as f32
+    }
+
+    fn maybe_adjust_size(&mut self) {
+        if self.load_factor() > COLLECT_LOAD_FACTOR {
+            self.remove_expired();
+
+            let load_factor = self.load_factor();
+            let capacity = self.capacity();
+            if load_factor > GROW_LOAD_FACTOR {
+                self.resize(max(1, capacity * 2));
+            } else if load_factor < SHRINK_LOAD_FACTOR && capacity > DEFAULT_INITIAL_CAPACITY {
+                self.resize(max(1, capacity / 2));
+            }
+        }
+    }
+
+    /// Gets the requested entry.
+    pub fn entry(&mut self, key: K) -> Entry<K, V> {
+        self.maybe_adjust_size();
+        self.entry_no_grow(key)
+    }
+
+    fn entry_no_grow(&mut self, key: K) -> Entry<K, V> {
+        let mut inner = {
+            let hash_code = self.hash(&key);
+            InnerEntry {
+                pos:        self.which_bucket(hash_code),
+                map:        &mut self.inner,
+                hash_code,
+                key,
+            }
+        };
+
+        for dist in 0 .. inner.capacity() {
+            match inner.bucket_status() {
+                BucketStatus::Unoccupied =>
+                    return Entry::Vacant(VacantEntry {inner}),
+                BucketStatus::MatchesKey(value) => {
+                    return Entry::Occupied(OccupiedEntry {inner, value})
+                }
+                BucketStatus::ProbeDistance(bucket_distance) => {
+                    if bucket_distance < dist {
+                        return Entry::Vacant(VacantEntry {inner})
+                    } else {
+                        inner.pos = inner.next_bucket(inner.pos);
+                    }
+                }
+            }
+        }
+
+        panic!("WeakValueHashTable::entry: out of space");
+    }
+
+    /// Removes all associations from the map.
+    pub fn clear(&mut self) {
+        self.drain();
+    }
+
+    fn find_bucket<Q>(&self, key: &Q) -> Option<(usize, V::Strong)>
+        where Q: ?Sized + Hash + Eq,
+              K: Borrow<Q>
+    {
+        if self.capacity() == 0 { return None; }
+
+        let hash_code = self.hash(key);
+        let mut pos = self.which_bucket(hash_code);
+
+        for dist in 0 .. self.capacity() {
+            if let Some((ref bucket_key, ref weak_value, bucket_hash_code)) = self.inner.buckets[pos] {
+                if bucket_hash_code == hash_code {
+                    if let Some(value) = weak_value.view() {
+                        if bucket_key.borrow() == key {
+                            return Some((pos, value));
+                        }
+                    }
+                }
+
+                let bucket_dist =
+                    self.probe_distance(pos, self.which_bucket(hash_code));
+                if bucket_dist < dist {
+                    return None;
+                }
+            } else {
+                return None;
+            }
+
+            pos = self.next_bucket(pos);
+        }
+
+        None
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    pub fn get<Q>(&self, key: &Q) -> Option<V::Strong>
+        where Q: ?Sized + Hash + Eq,
+              K: Borrow<Q>
+    {
+        self.find_bucket(key).map(|tup| tup.1)
+    }
+
+    /// Returns true if the map contains the specified key.
+    pub fn contains_key<Q>(&self, key: &Q) -> bool
+        where Q: ?Sized + Hash + Eq,
+              K: Borrow<Q>
+    {
+        self.find_bucket(key).is_some()
+    }
+
+    /// Unconditionally inserts the value, returning the old value if already present.
+    ///
+    /// Like `std::collections::HashMap`, this does not replace the key if occupied.
+    pub fn insert(&mut self, key: K, value: V::Strong) -> Option<V::Strong> {
+        match self.entry(key) {
+            Entry::Occupied(mut occupied) => {
+                Some(occupied.insert(value))
+            },
+            Entry::Vacant(vacant) => {
+                vacant.insert(value);
+                None
+            }
+        }
+    }
+
+    /// Removes the entry with the given key, if it exists, and returns the value.
+    pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong>
+        where Q: ?Sized + Hash + Eq,
+              K: Borrow<Q>
+    {
+        if let Some((pos, value)) = self.find_bucket(key) {
+            self.inner.remove_index(pos);
+            Some(value)
+        } else {
+            None
+        }
+    }
+
+    /// Removes all mappings not satisfying the given predicate.
+    ///
+    /// Also removes any expired mappings.
+    pub fn retain<F>(&mut self, mut f: F)
+        where F: FnMut(&K, V::Strong) -> bool
+    {
+        for i in 0 .. self.capacity() {
+            let remove = match self.inner.buckets[i] {
+                None => false,
+                Some(ref mut bucket) =>
+                    match bucket.1.view() {
+                        None => true,
+                        Some(value) => !f(&bucket.0, value),
+                    }
+            };
+
+            if remove {
+                self.inner.remove_index(i);
+            }
+        }
+    }
+
+    /// Is this map a submap of the other, using the given value comparison.
+    ///
+    /// 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: &WeakValueHashMap<K, V1, S1>,
+                                     mut value_equal: F) -> bool
+        where V1: WeakElement,
+              F: FnMut(V::Strong, V1::Strong) -> bool,
+              S1: BuildHasher
+    {
+        for (key, value1) in self {
+            if let Some(value2) = other.get(key) {
+                if !value_equal(value1, value2) {
+                    return false;
+                }
+            } else {
+                return false;
+            }
+        }
+
+        true
+    }
+
+    /// Is `self` a submap of `other`?
+    pub fn is_submap<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool
+        where V1: WeakElement,
+              V::Strong: PartialEq<V1::Strong>,
+              S1: BuildHasher
+    {
+        self.is_submap_with(other, |v, v1| v == v1)
+    }
+
+    /// Are the keys of `self` a subset of the keys of `other`?
+    pub fn domain_is_subset<V1, S1>(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool
+        where V1: WeakElement,
+              S1: BuildHasher
+    {
+        self.is_submap_with(other, |_, _| true)
+    }
+
+    fn hash<Q>(&self, key: &Q) -> HashCode
+        where Q: ?Sized + Hash,
+              K: Borrow<Q>
+    {
+        let mut hasher = self.hash_builder.build_hasher();
+        key.hash(&mut hasher);
+        HashCode(hasher.finish())
+    }
+}
+
+impl<K, V, V1, S, S1> PartialEq<WeakValueHashMap<K, V1, S1>> for WeakValueHashMap<K, V, S>
+    where K: Eq + Hash,
+          V: WeakElement,
+          V1: WeakElement,
+          V::Strong: PartialEq<V1::Strong>,
+          S: BuildHasher,
+          S1: BuildHasher
+{
+    fn eq(&self, other: &WeakValueHashMap<K, V1, S1>) -> bool {
+        self.is_submap(other) && other.domain_is_subset(self)
+    }
+}
+
+impl<K: Eq + Hash, V: WeakElement, S: BuildHasher> Eq for WeakValueHashMap<K, V, S>
+    where V::Strong: Eq
+{ }
+
+impl<K: Eq + Hash, V: WeakElement, S: BuildHasher + Default> Default for WeakValueHashMap<K, V, S> {
+    fn default() -> Self {
+        WeakValueHashMap::with_hasher(Default::default())
+    }
+}
+
+impl<K, V, S> ::std::iter::FromIterator<(K, V::Strong)> for WeakValueHashMap<K, V, S>
+    where K: Eq + Hash,
+          V: WeakElement,
+          S: BuildHasher + Default
+{
+    fn from_iter<T: IntoIterator<Item=(K, V::Strong)>>(iter: T) -> Self {
+        let mut result = WeakValueHashMap::with_hasher(Default::default());
+        result.extend(iter);
+        result
+    }
+}
+
+impl<K, V, S> Extend<(K, V::Strong)> for WeakValueHashMap<K, V, S>
+    where K: Eq + Hash,
+          V: WeakElement,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(K, V::Strong)>>(&mut self, iter: T) {
+        for (key, value) in iter {
+            self.insert(key, value);
+        }
+    }
+}
+
+impl<'a, K, V, S> Extend<(&'a K, &'a V::Strong)> for WeakValueHashMap<K, V, S>
+    where K: 'a + Eq + Hash + Clone,
+          V: 'a + WeakElement,
+          V::Strong: Clone,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(&'a K, &'a V::Strong)>>(&mut self, iter: T) {
+        for (key, value) in iter {
+            self.insert(key.clone(), value.clone());
+        }
+    }
+}
+
+enum BucketStatus<V: WeakElement> {
+    Unoccupied,
+    MatchesKey(V::Strong),
+    ProbeDistance(usize),
+}
+
+impl<'a, K: Eq + Hash, V: WeakElement> InnerEntry<'a, K, V> {
+    // Gets the status of the current bucket.
+    fn bucket_status(&self) -> BucketStatus<V> {
+        match &self.map.buckets[self.pos] {
+            Some(bucket) => {
+                if bucket.2 == self.hash_code {
+                    if let Some(value) = bucket.1.view() {
+                        if self.key == bucket.0 {
+                            return BucketStatus::MatchesKey(value);
+                        }
+                    }
+                }
+
+                let dist = self.probe_distance(self.pos,
+                                               self.which_bucket(bucket.2));
+                BucketStatus::ProbeDistance(dist)
+            },
+            None => BucketStatus::Unoccupied,
+        }
+    }
+}
+
+impl<'a, K, V: WeakElement> Entry<'a, K, V> {
+    /// Ensures a value is in the entry by inserting a default value
+    /// if empty.
+    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.
+    pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong {
+        match self {
+            Entry::Occupied(occupied) => occupied.get_strong(),
+            Entry::Vacant(vacant) => vacant.insert(default()),
+        }
+    }
+
+    /// Returns a reference to this entry's key.
+    pub fn key(&self) -> &K {
+        match *self {
+            Entry::Occupied(ref occupied) => occupied.key(),
+            Entry::Vacant(ref vacant) => vacant.key(),
+        }
+    }
+}
+
+impl<'a, K, V: WeakElement> OccupiedEntry<'a, K, V> {
+    /// Gets a reference to the key held by the entry.
+    pub fn key(&self) -> &K {
+        &self.inner.key
+    }
+
+    /// Takes ownership of the key and value from the map.
+    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();
+        self.inner.map.remove_index(self.inner.pos);
+        (key, value)
+    }
+
+    /// Gets a reference to the value in the entry.
+    pub fn get(&self) -> &V::Strong {
+        &self.value
+    }
+
+    /// Gets a copy of the strong value reference stored in the entry.
+    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.
+    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.
+    pub fn remove(self) -> V::Strong {
+        self.remove_entry().1
+    }
+}
+
+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`.
+    pub fn key(&self) -> &K {
+        &self.inner.key
+    }
+
+    /// Returns ownership of the key.
+    pub fn into_key(self) -> K {
+        self.inner.key
+    }
+
+    /// Inserts the value into the map, returning the same value.
+    pub fn insert(self, value: V::Strong) -> V::Strong {
+        let InnerEntry { map, key, hash_code, pos } = self.inner;
+
+        let old_bucket = mem::replace(
+            &mut map.buckets[pos],
+            Some((key, V::new(&value), hash_code)));
+
+        if let Some(full_bucket) = old_bucket {
+            let next_bucket = map.next_bucket(pos);
+            map.steal(next_bucket, full_bucket);
+        }
+
+        map.len += 1;
+
+        value
+    }
+}
+
+impl<K, V: WeakElement> WeakValueInnerMap<K, V> {
+    // Steals buckets starting at `pos`, replacing them with `bucket`.
+    fn steal(&mut self, mut pos: usize, mut bucket: FullBucket<K, V>) {
+        let mut my_dist = self.probe_distance(pos, self.which_bucket(bucket.2));
+
+        while let Some(hash_code) = self.buckets[pos].as_ref().and_then(
+            |bucket| if bucket.1.is_expired() {None} else {Some(bucket.2)}) {
+
+            let victim_dist = self.probe_distance(pos, self.which_bucket(hash_code));
+
+            if my_dist > victim_dist {
+                mem::swap(self.buckets[pos].as_mut().unwrap(), &mut bucket);
+                my_dist = victim_dist;
+            }
+
+            pos = self.next_bucket(pos);
+            my_dist += 1;
+        }
+
+        self.buckets[pos] = Some(bucket);
+    }
+
+    /// Removes the element at `dst`, shifting if necessary to preserve invariants.
+    fn remove_index(&mut self, mut dst: usize) {
+        let mut src = self.next_bucket(dst);
+
+        // We are going to remove the buckets in the range [dst, src)
+
+        loop {
+            let hash_code_option = self.buckets[src].as_ref().map(|tup| tup.2);
+
+            if let Some(hash_code) = hash_code_option {
+                let goal_pos = self.which_bucket(hash_code);
+                let dist = self.probe_distance(src, goal_pos);
+                if dist == 0 { break; }
+
+                if !self.buckets[src].as_ref().unwrap().1.is_expired() {
+                    if in_interval(dst, goal_pos, src) {
+                        self.erase_range(dst, goal_pos);
+                        self.buckets[goal_pos] = self.buckets[src].take();
+                        dst = self.next_bucket(goal_pos);
+                    } else {
+                        self.buckets[dst] = self.buckets[src].take();
+                        dst = self.next_bucket(dst);
+                    }
+                }
+            } else {
+                break;
+            }
+
+            src = self.next_bucket(src);
+        }
+
+        self.erase_range(dst, src);
+    }
+
+    /// Erases the (presumably expired, but not empty) elements in [start, limit).
+    fn erase_range(&mut self, mut start: usize, limit: usize)
+    {
+        while start != limit {
+            self.buckets[start] = None;
+            self.len -= 1;
+            start = self.next_bucket(start);
+        }
+    }
+}
+
+// Is value in [start, limit) modulo capacity?
+fn in_interval(start: usize, value: usize, limit: usize) -> bool
+{
+    if start <= limit {
+        start <= value && value < limit
+    } else {
+        start <= value || value < limit
+    }
+}
+
+// Helper trait for computing with indices modulo capacity.
+trait ModuloCapacity {
+    fn capacity(&self) -> usize;
+
+    fn probe_distance(&self, actual: usize, ideal: usize) -> usize {
+        if actual >= ideal {
+            actual - ideal
+        } else {
+            actual + self.capacity() - ideal
+        }
+    }
+
+    fn next_bucket(&self, pos: usize) -> usize {
+        assert_ne!( self.capacity(), 0 );
+        (pos + 1) % self.capacity()
+    }
+
+    fn which_bucket(&self, hash_code: HashCode) -> usize {
+        assert_ne!( self.capacity(), 0 );
+        (hash_code.0 as usize) % self.capacity()
+    }
+}
+
+impl<K, V> ModuloCapacity for WeakValueInnerMap<K, V> {
+    fn capacity(&self) -> usize {
+        self.buckets.len()
+    }
+}
+
+impl<K, V, S> ModuloCapacity for WeakValueHashMap<K, V, S> {
+    fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+}
+
+impl<'a, K, V: WeakElement> ModuloCapacity for InnerEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.map.capacity()
+    }
+}
+
+impl<'a, K, V: WeakElement> ModuloCapacity for OccupiedEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+}
+
+impl<'a, K, V: WeakElement> ModuloCapacity for VacantEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+}
+
+impl<K, V> Debug for WeakValueInnerMap<K, V>
+    where K: Debug,
+          V: WeakElement,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "{{ ")?;
+        for (i, bucket) in self.buckets.iter().enumerate() {
+            if let Some((k, v, _)) = bucket {
+                write!(f, "[{}] {:?} => {:?}, ", i, *k, v.view())?;
+            }
+        }
+        write!(f, "}}")
+    }
+}
+
+impl<K: Debug, V: WeakElement, S> Debug for WeakValueHashMap<K, V, S>
+    where V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K: Debug, V: WeakElement> Debug for Entry<'a, K, V>
+    where V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        match *self {
+            Entry::Occupied(ref e)  => e.fmt(f),
+            Entry::Vacant(ref e)    => e.fmt(f),
+        }
+    }
+}
+
+impl<'a, K: Debug, V: WeakElement> Debug for OccupiedEntry<'a, K, V>
+    where V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K: Debug, V: WeakElement> Debug for VacantEntry<'a, K, V>
+    where V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K: Debug, V: WeakElement> Debug for InnerEntry<'a, K, V>
+    where V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "InnerEntry {{ pos = {}, buckets = {:?} }}", self.pos, self.map)
+    }
+}
+
+impl<K, V: WeakElement, S> IntoIterator for WeakValueHashMap<K, V, S> {
+    type Item = (K, V::Strong);
+    type IntoIter = IntoIter<K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            size: self.inner.len,
+            base: self.inner.buckets.into_vec().into_iter(),
+        }
+    }
+}
+
+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>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        Iter {
+            base: self.inner.buckets.iter(),
+            size: self.inner.len,
+        }
+    }
+}
+
+impl<K, V: WeakElement, S> WeakValueHashMap<K, V, S> {
+    /// Gets an iterator over the keys and values.
+    pub fn iter(&self) -> Iter<K, V> {
+        self.into_iter()
+    }
+
+    /// Gets an iterator over the keys.
+    pub fn keys(&self) -> Keys<K, V> {
+        Keys(self.iter())
+    }
+
+    /// Gets an iterator over the values.
+    pub fn values(&self) -> Values<K, V> {
+        Values(self.iter())
+    }
+
+    /// Gets a draining iterator, which removes all the values but retains the storage.
+    pub fn drain(&mut self) -> Drain<K, V> {
+        let old_len = self.inner.len;
+        self.inner.len = 0;
+        Drain {
+            base: self.inner.buckets.iter_mut(),
+            size: old_len,
+        }
+    }
+}
+
+
diff --git a/src/weak_weak_hash_map.rs b/src/weak_weak_hash_map.rs
new file mode 100644
index 0000000..0ed89f6
--- /dev/null
+++ b/src/weak_weak_hash_map.rs
@@ -0,0 +1,902 @@
+//! 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::*;
+use super::util::*;
+
+pub use super::WeakWeakHashMap;
+
+/// Represents an entry in the table which may be occupied or vacant.
+pub enum Entry<'a, K: 'a + WeakKey, V: 'a + WeakElement> {
+    Occupied(OccupiedEntry<'a, K, V>),
+    Vacant(VacantEntry<'a, K, V>),
+}
+
+/// An occupied entry, which can be removed or viewed.
+pub struct OccupiedEntry<'a, K: 'a + WeakKey, V: 'a + WeakElement> {
+    inner: InnerEntry<'a, K, V>,
+    value: V::Strong,
+}
+
+/// A vacant entry, which can be inserted in or viewed.
+pub struct VacantEntry<'a, K: 'a + WeakKey, V: 'a + WeakElement> {
+    inner: InnerEntry<'a, K, V>,
+}
+
+struct InnerEntry<'a, K: 'a + WeakKey, V: 'a> {
+    map:        &'a mut WeakWeakInnerMap<K, V>,
+    pos:        usize,
+    key:        K::Strong,
+    hash_code:  HashCode,
+}
+
+/// An iterator over the keys and values of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Iter<'a, K: 'a, V: 'a> {
+    base: ::std::slice::Iter<'a, Bucket<K, V>>,
+    size: usize,
+}
+
+impl<'a, K: WeakElement, V: WeakElement> Iterator for Iter<'a, K, V> {
+    type Item = (K::Strong, V::Strong);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            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()) {
+                    return Some((key, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+/// An iterator over the keys of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Keys<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
+
+impl<'a, K: WeakElement, V: WeakElement> Iterator for Keys<'a, K, V> {
+    type Item = K::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(k, _)| k)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+/// An iterator over the values of the weak hash map.
+#[derive(Clone, Debug)]
+pub struct Values<'a, K: 'a, V: 'a>(Iter<'a, K, V>);
+
+impl<'a, K: WeakElement, V: WeakElement> Iterator for Values<'a, K, V> {
+    type Item = V::Strong;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next().map(|(_, v)| v)
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.0.size_hint()
+    }
+}
+
+#[derive(Debug)]
+/// An iterator that consumes the values of a weak hash map, leaving it empty.
+pub struct Drain<'a, K: 'a, V: 'a> {
+    base: ::std::slice::IterMut<'a, Bucket<K, V>>,
+    size: usize,
+}
+
+impl<'a, K: WeakElement, V: WeakElement> Iterator for Drain<'a, K, V> {
+    type Item = (K::Strong, V::Strong);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((weak_key, weak_value, _)) = bucket.take() {
+                self.size -= 1;
+                if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
+                    return Some((key, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+impl<'a, K, V> Drop for Drain<'a, K, V> {
+    fn drop(&mut self) {
+        while let Some(option) = self.base.next() {
+            *option = None;
+        }
+    }
+}
+
+/// An iterator that consumes the values of a weak hash map, leaving it empty.
+pub struct IntoIter<K, V> {
+    base: ::std::vec::IntoIter<Bucket<K, V>>,
+    size: usize,
+}
+
+impl<K: WeakElement, V: WeakElement> Iterator for IntoIter<K, V> {
+    type Item = (K::Strong, V::Strong);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(bucket) = self.base.next() {
+            if let Some((weak_key, weak_value, _)) = bucket {
+                self.size -= 1;
+                if let (Some(key), Some(value)) = (weak_key.view(), weak_value.view()) {
+                    return Some((key, value));
+                }
+            }
+        }
+
+        None
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (0, Some(self.size))
+    }
+}
+
+impl<K: WeakKey, V: WeakElement> WeakWeakHashMap<K, V, RandomState>
+{
+    /// Creates an empty `WeakWeakHashMap`.
+    pub fn new() -> Self {
+        Self::with_capacity(DEFAULT_INITIAL_CAPACITY)
+    }
+
+    /// Creates an empty `WeakWeakHashMap` with the given capacity.
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self::with_capacity_and_hasher(capacity, Default::default())
+    }
+}
+
+impl<K: WeakKey, V: WeakElement, S: BuildHasher> WeakWeakHashMap<K, V, S> {
+    /// Creates an empty `WeakWeakHashMap` with the given capacity and hasher.
+    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.
+    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
+        WeakWeakHashMap {
+            hash_builder,
+            inner: WeakWeakInnerMap {
+                buckets: new_boxed_option_slice(capacity),
+                len: 0,
+            }
+        }
+    }
+
+    /// Returns a reference to the map's `BuildHasher`.
+    pub fn hasher(&self) -> &S {
+        &self.hash_builder
+    }
+
+    /// Returns the number of elements the map can hold without reallocating.
+    pub fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+
+    /// This has some preconditions.
+    fn resize(&mut self, capacity: usize) {
+        let old_buckets = mem::replace(&mut self.inner.buckets,
+                                       new_boxed_option_slice(capacity));
+
+        let iter = IntoIter {
+            base: old_buckets.into_vec().into_iter(),
+            size: self.inner.len,
+        };
+
+        self.inner.len = 0;
+
+        for (key, value) in iter {
+            self.entry_no_grow(key).or_insert(value);
+        }
+    }
+
+    /// Removes all mappings whose keys have expired.
+    pub fn remove_expired(&mut self) {
+        self.retain(|_, _| true)
+    }
+
+    /// Reserves room for additional elements.
+    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.
+    pub fn shrink_to_fit(&mut self) {
+        self.remove_expired();
+        let new_capacity = (self.len() as f32 / COLLECT_LOAD_FACTOR).ceil() as usize;
+        self.resize(new_capacity);
+    }
+
+    /// Returns an over-approximation of the number of elements.
+    pub fn len(&self) -> usize {
+        self.inner.len
+    }
+
+    /// Is the map empty?
+    ///
+    /// Note that this may return false even if all keys in the map have
+    /// expired, if they haven't been collected yet.
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// The proportion of buckets that are used.
+    ///
+    /// This is an over-approximation because of expired keys.
+    pub fn load_factor(&self) -> f32 {
+        (self.len() as f32 + 1.0) / self.capacity() as f32
+    }
+
+    fn maybe_adjust_size(&mut self) {
+        if self.load_factor() > COLLECT_LOAD_FACTOR {
+            self.remove_expired();
+
+            let load_factor = self.load_factor();
+            let capacity = self.capacity();
+            if load_factor > GROW_LOAD_FACTOR {
+                self.resize(max(1, capacity * 2));
+            } else if load_factor < SHRINK_LOAD_FACTOR && capacity > DEFAULT_INITIAL_CAPACITY {
+                self.resize(max(1, capacity / 2));
+            }
+        }
+    }
+
+    /// Gets the requested entry.
+    pub fn entry(&mut self, key: K::Strong) -> Entry<K, V> {
+        self.maybe_adjust_size();
+        self.entry_no_grow(key)
+    }
+
+    fn entry_no_grow(&mut self, key: K::Strong) -> Entry<K, V> {
+        let mut inner = {
+            let hash_code = K::with_key(&key, |k| self.hash(k));
+            InnerEntry {
+                pos:        self.which_bucket(hash_code),
+                map:        &mut self.inner,
+                hash_code,
+                key,
+            }
+        };
+
+        for dist in 0 .. inner.capacity() {
+            match inner.bucket_status() {
+                BucketStatus::Unoccupied =>
+                    return Entry::Vacant(VacantEntry {inner}),
+                BucketStatus::MatchesKey(value) =>
+                    return Entry::Occupied(OccupiedEntry {value, inner}),
+                BucketStatus::ProbeDistance(bucket_distance) => {
+                    if bucket_distance < dist {
+                        return Entry::Vacant(VacantEntry {inner})
+                    } else {
+                        inner.pos = inner.next_bucket(inner.pos);
+                    }
+                }
+            }
+        }
+
+        panic!("WeakKeyHashTable::entry: out of space");
+    }
+
+    /// Removes all associations from the map.
+    pub fn clear(&mut self) {
+        self.drain();
+    }
+
+    fn find_bucket<Q>(&self, key: &Q) -> Option<(usize, K::Strong, V::Strong)>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        if self.capacity() == 0 { return None; }
+
+        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::with_key(&b_key, |k| k.borrow() == key) {
+                            return Some((pos, b_key, b_value));
+                        }
+                    }
+                }
+
+                let bucket_dist =
+                    self.probe_distance(pos, self.which_bucket(hash_code));
+                if bucket_dist < dist {
+                    return None;
+                }
+            } else {
+                return None;
+            }
+
+            pos = self.next_bucket(pos);
+        }
+
+        None
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    pub fn get<Q>(&self, key: &Q) -> Option<V::Strong>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).map(|tup| tup.2)
+    }
+
+    /// Returns the strong reference to the key, if present.
+    pub fn get_key<Q>(&self, key: &Q) -> Option<K::Strong>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).map(|tup| tup.1)
+    }
+
+    /// Returns strong references to both the key and the value, if present.
+    pub fn get_both<Q>(&self, key: &Q) -> Option<(K::Strong, V::Strong)>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).map(|tup| (tup.1, tup.2))
+    }
+
+    /// Returns true if the map contains the specified key.
+    pub fn contains_key<Q>(&self, key: &Q) -> bool
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        self.find_bucket(key).is_some()
+    }
+
+    /// Unconditionally inserts the value, returning the old value if already present.
+    ///
+    /// Unlike `std::collections::HashMap`, this replaces the key even if occupied.
+    pub fn insert(&mut self, key: K::Strong, value: V::Strong) -> Option<V::Strong> {
+        match self.entry(key) {
+            Entry::Occupied(mut occupied) => {
+                Some(occupied.insert(value))
+            },
+            Entry::Vacant(vacant) => {
+                vacant.insert(value);
+                None
+            }
+        }
+    }
+
+    /// Removes the entry with the given key, if it exists, and returns the value.
+    pub fn remove<Q>(&mut self, key: &Q) -> Option<V::Strong>
+        where Q: ?Sized + Hash + Eq,
+              K::Key: Borrow<Q>
+    {
+        if let Some((pos, _, value)) = self.find_bucket(key) {
+            self.inner.remove_index(pos);
+            Some(value)
+        } else {
+            None
+        }
+    }
+
+    /// Removes all mappings not satisfying the given predicate.
+    ///
+    /// Also removes any expired mappings.
+    pub fn retain<F>(&mut self, mut f: F)
+        where F: FnMut(K::Strong, V::Strong) -> bool
+    {
+        for i in 0 .. self.capacity() {
+            let remove = match self.inner.buckets[i] {
+                None => false,
+                Some(ref bucket) =>
+                    match (bucket.0.view(), bucket.1.view()) {
+                        (Some(key), Some(value)) => !f(key, value),
+                        _ => true,
+                    }
+            };
+
+            if remove {
+                self.inner.remove_index(i);
+            }
+        }
+    }
+
+    /// Is this map a submap of the other, using the given value comparison.
+    ///
+    /// 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: &WeakWeakHashMap<K, V1, S1>,
+                                     mut value_equal: F) -> bool
+        where V1: WeakElement,
+              F: FnMut(V::Strong, V1::Strong) -> bool,
+              S1: BuildHasher
+    {
+        for (key, value1) in self {
+            if let Some(value2) = K::with_key(&key, |k| other.get(k)) {
+                if !value_equal(value1, value2) {
+                    return false;
+                }
+            } else {
+                return false;
+            }
+        }
+
+        true
+    }
+
+    /// Is `self` a submap of `other`?
+    pub fn is_submap<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
+        where V1: WeakElement,
+              V::Strong: PartialEq<V1::Strong>,
+              S1: BuildHasher
+    {
+        self.is_submap_with(other, |v, v1| v == v1)
+    }
+
+    /// Are the keys of `self` a subset of the keys of `other`?
+    pub fn domain_is_subset<V1, S1>(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool
+        where V1: WeakElement,
+              S1: BuildHasher
+    {
+        self.is_submap_with(other, |_, _| true)
+    }
+
+    fn hash<Q>(&self, key: &Q) -> HashCode
+        where Q: ?Sized + Hash,
+              K::Key: Borrow<Q>
+    {
+        let mut hasher = self.hash_builder.build_hasher();
+        key.hash(&mut hasher);
+        HashCode(hasher.finish())
+    }
+}
+
+impl<K, V, V1, S, S1> PartialEq<WeakWeakHashMap<K, V1, S1>> for WeakWeakHashMap<K, V, S>
+    where K: WeakKey,
+          V: WeakElement,
+          V1: WeakElement,
+          V::Strong: PartialEq<V1::Strong>,
+          S: BuildHasher,
+          S1: BuildHasher
+{
+    fn eq(&self, other: &WeakWeakHashMap<K, V1, S1>) -> bool {
+        self.is_submap(other) && other.domain_is_subset(self)
+    }
+}
+
+impl<K: WeakKey, V: WeakElement, S: BuildHasher> Eq for WeakWeakHashMap<K, V, S>
+    where V::Strong: Eq
+{ }
+
+impl<K: WeakKey, V: WeakElement, S: BuildHasher + Default> Default for WeakWeakHashMap<K, V, S> {
+    fn default() -> Self {
+        WeakWeakHashMap::with_hasher(Default::default())
+    }
+}
+
+impl<K, V, S> ::std::iter::FromIterator<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
+    where K: WeakKey,
+          V: WeakElement,
+          S: BuildHasher + Default
+{
+    fn from_iter<T: IntoIterator<Item=(K::Strong, V::Strong)>>(iter: T) -> Self {
+        let mut result = WeakWeakHashMap::with_hasher(Default::default());
+        result.extend(iter);
+        result
+    }
+}
+
+impl<K, V, S> Extend<(K::Strong, V::Strong)> for WeakWeakHashMap<K, V, S>
+    where K: WeakKey,
+          V: WeakElement,
+          S: BuildHasher
+{
+    fn extend<T: IntoIterator<Item=(K::Strong, V::Strong)>>(&mut self, iter: T) {
+        for (key, value) in iter {
+            self.insert(key, value);
+        }
+    }
+}
+
+enum BucketStatus<V: WeakElement> {
+    Unoccupied,
+    MatchesKey(V::Strong),
+    ProbeDistance(usize),
+}
+
+impl<'a, K: WeakKey, V: WeakElement> InnerEntry<'a, K, V> {
+    // Gets the status of the current bucket.
+    fn bucket_status(&self) -> BucketStatus<V> {
+        match &self.map.buckets[self.pos] {
+            Some(bucket) => {
+                if bucket.2 == self.hash_code {
+                    if let (Some(key), Some(value)) = (bucket.0.view(), bucket.1.view()) {
+                        if K::with_key(&self.key, |k1| K::with_key(&key, |k2| k1 == k2)) {
+                            return BucketStatus::MatchesKey(value);
+                        }
+                    }
+                }
+
+                let dist = self.probe_distance(self.pos,
+                                               self.which_bucket(bucket.2));
+                BucketStatus::ProbeDistance(dist)
+            },
+            None => BucketStatus::Unoccupied,
+        }
+    }
+}
+
+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.
+    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, and returns a mutable reference to
+    /// the value in the entry.
+    pub fn or_insert_with<F: FnOnce() -> V::Strong>(self, default: F) -> V::Strong {
+        match self {
+            Entry::Occupied(occupied) => occupied.get_strong(),
+            Entry::Vacant(vacant) => vacant.insert(default()),
+        }
+    }
+
+    /// Returns a reference to this entry's key.
+    pub fn key(&self) -> &K::Strong {
+        match *self {
+            Entry::Occupied(ref occupied) => occupied.key(),
+            Entry::Vacant(ref vacant) => vacant.key(),
+        }
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> OccupiedEntry<'a, K, V> {
+    /// Gets a reference to the key held by the entry.
+    pub fn key(&self) -> &K::Strong {
+        &self.inner.key
+    }
+
+    /// Takes ownership of the key and value from the map.
+    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();
+        self.inner.map.remove_index(self.inner.pos);
+        (self.inner.key, value)
+    }
+
+    /// Gets a reference to the value in the entry.
+    pub fn get(&self) -> &V::Strong {
+        &self.value
+    }
+
+    /// Gets a clone of the reference to the value in the entry.
+    pub fn get_strong(&self) -> V::Strong {
+        V::clone(&self.value)
+    }
+
+    /// Replaces the value in the entry with the given value.
+    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.
+    pub fn remove(self) -> V::Strong {
+        self.remove_entry().1
+    }
+}
+
+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`.
+    pub fn key(&self) -> &K::Strong {
+        &self.inner.key
+    }
+
+    /// Returns ownership of the key.
+    pub fn into_key(self) -> K::Strong {
+        self.inner.key
+    }
+
+    /// Inserts the key and value into the map, returning the same value.
+    pub fn insert(self, value: V::Strong) -> V::Strong {
+        let old_bucket = mem::replace(
+            &mut self.inner.map.buckets[self.inner.pos],
+            Some((K::new(&self.inner.key), V::new(&value), self.inner.hash_code)));
+
+        if let Some(full_bucket) = old_bucket {
+            let next_bucket = self.next_bucket(self.inner.pos);
+            self.inner.map.steal(next_bucket, full_bucket);
+        }
+
+        self.inner.map.len += 1;
+
+        value
+    }
+}
+
+impl<K: WeakKey, V: WeakElement> WeakWeakInnerMap<K, V> {
+    // Steals buckets starting at `pos`, replacing them with `bucket`.
+    fn steal(&mut self, mut pos: usize, mut bucket: FullBucket<K, V>) {
+        let mut my_dist = self.probe_distance(pos, self.which_bucket(bucket.2));
+
+        while let Some(hash_code) = self.buckets[pos].as_ref().and_then(
+            |bucket| if bucket.0.is_expired() || bucket.1.is_expired() {
+                None
+            } else {
+                Some(bucket.2)
+            }) {
+
+            let victim_dist = self.probe_distance(pos, self.which_bucket(hash_code));
+
+            if my_dist > victim_dist {
+                mem::swap(self.buckets[pos].as_mut().unwrap(), &mut bucket);
+                my_dist = victim_dist;
+            }
+
+            pos = self.next_bucket(pos);
+            my_dist += 1;
+        }
+
+        self.buckets[pos] = Some(bucket);
+    }
+
+    /// Removes the element at `dst`, shifting if necessary to preserve invariants.
+    fn remove_index(&mut self, mut dst: usize) {
+        let mut src = self.next_bucket(dst);
+
+        // We are going to remove the buckets in the range [dst, src)
+
+        loop {
+            let hash_code_option = self.buckets[src].as_ref().map(|tup| tup.2);
+
+            if let Some(hash_code) = hash_code_option {
+                let goal_pos = self.which_bucket(hash_code);
+                let dist = self.probe_distance(src, goal_pos);
+                if dist == 0 { break; }
+
+                let expired = {
+                    let bucket = self.buckets[src].as_ref().unwrap();
+                    bucket.0.is_expired() || bucket.1.is_expired()
+                };
+
+                if !expired {
+                    if in_interval(dst, goal_pos, src) {
+                        self.erase_range(dst, goal_pos);
+                        self.buckets[goal_pos] = self.buckets[src].take();
+                        dst = self.next_bucket(goal_pos);
+                    } else {
+                        self.buckets[dst] = self.buckets[src].take();
+                        dst = self.next_bucket(dst);
+                    }
+                }
+            } else {
+                break;
+            }
+
+            src = self.next_bucket(src);
+        }
+
+        self.erase_range(dst, src);
+    }
+
+    /// Erases the (presumably expired, but not empty) elements in [start, limit).
+    fn erase_range(&mut self, mut start: usize, limit: usize)
+    {
+        while start != limit {
+            self.buckets[start] = None;
+            self.len -= 1;
+            start = self.next_bucket(start);
+        }
+    }
+}
+
+// Is value in [start, limit) modulo capacity?
+fn in_interval(start: usize, value: usize, limit: usize) -> bool
+{
+    if start <= limit {
+        start <= value && value < limit
+    } else {
+        start <= value || value < limit
+    }
+}
+
+// Helper trait for computing with indices modulo capacity.
+trait ModuloCapacity {
+    fn capacity(&self) -> usize;
+
+    fn probe_distance(&self, actual: usize, ideal: usize) -> usize {
+        if actual >= ideal {
+            actual - ideal
+        } else {
+            actual + self.capacity() - ideal
+        }
+    }
+
+    fn next_bucket(&self, pos: usize) -> usize {
+        assert_ne!( self.capacity(), 0 );
+        (pos + 1) % self.capacity()
+    }
+
+    fn which_bucket(&self, hash_code: HashCode) -> usize {
+        assert_ne!( self.capacity(), 0 );
+        (hash_code.0 as usize) % self.capacity()
+    }
+}
+
+impl<K, V> ModuloCapacity for WeakWeakInnerMap<K, V> {
+    fn capacity(&self) -> usize {
+        self.buckets.len()
+    }
+}
+
+impl<K, V, S> ModuloCapacity for WeakWeakHashMap<K, V, S> {
+    fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> ModuloCapacity for InnerEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.map.capacity()
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> ModuloCapacity for OccupiedEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> ModuloCapacity for VacantEntry<'a, K, V> {
+    fn capacity(&self) -> usize {
+        self.inner.capacity()
+    }
+}
+
+impl<K, V> Debug for WeakWeakInnerMap<K, V>
+    where K: WeakElement,
+          K::Strong: Debug,
+          V: WeakElement,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "{{ ")?;
+        for (i, bucket) in self.buckets.iter().enumerate() {
+            if let Some((k, v, _)) = bucket {
+                write!(f, "[{}] {:?} => {:?}, ", i, k.view(), v.view())?;
+            }
+        }
+        write!(f, "}}")
+    }
+}
+
+impl<K: WeakElement, V: WeakElement, S> Debug for WeakWeakHashMap<K, V, S>
+    where K::Strong: Debug,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> Debug for Entry<'a, K, V>
+    where K::Strong: Debug,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        match *self {
+            Entry::Occupied(ref e)  => e.fmt(f),
+            Entry::Vacant(ref e)    => e.fmt(f),
+        }
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> Debug for OccupiedEntry<'a, K, V>
+    where K::Strong: Debug,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> Debug for VacantEntry<'a, K, V>
+    where K::Strong: Debug,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        self.inner.fmt(f)
+    }
+}
+
+impl<'a, K: WeakKey, V: WeakElement> Debug for InnerEntry<'a, K, V>
+    where K::Strong: Debug,
+          V::Strong: Debug
+{
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        write!(f, "InnerEntry {{ pos = {}, buckets = {:?} }}", self.pos, self.map)
+    }
+}
+
+impl<K: WeakElement, V: WeakElement, S> IntoIterator for WeakWeakHashMap<K, V, S> {
+    type Item = (K::Strong, V::Strong);
+    type IntoIter = IntoIter<K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            size: self.inner.len,
+            base: self.inner.buckets.into_vec().into_iter(),
+        }
+    }
+}
+
+impl<'a, K: WeakElement, V: WeakElement, S> IntoIterator for &'a WeakWeakHashMap<K, V, S> {
+    type Item = (K::Strong, V::Strong);
+    type IntoIter = Iter<'a, K, V>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        Iter {
+            base: self.inner.buckets.iter(),
+            size: self.inner.len,
+        }
+    }
+}
+
+impl<K: WeakElement, V: WeakElement, S> WeakWeakHashMap<K, V, S> {
+    /// Gets an iterator over the keys and values.
+    pub fn iter(&self) -> Iter<K, V> {
+        self.into_iter()
+    }
+
+    /// Gets an iterator over the keys.
+    pub fn keys(&self) -> Keys<K, V> {
+        Keys(self.iter())
+    }
+
+    /// Gets an iterator over the values.
+    pub fn values(&self) -> Values<K, V> {
+        Values(self.iter())
+    }
+
+    /// Gets a draining iterator, which removes all the values but retains the storage.
+    pub fn drain(&mut self) -> Drain<K, V> {
+        let old_len = self.inner.len;
+        self.inner.len = 0;
+        Drain {
+            base: self.inner.buckets.iter_mut(),
+            size: old_len,
+        }
+    }
+}
+
diff --git a/tests/symbols.rs b/tests/symbols.rs
new file mode 100644
index 0000000..4f01b0d
--- /dev/null
+++ b/tests/symbols.rs
@@ -0,0 +1,54 @@
+extern crate weak_table;
+
+use weak_table::WeakHashSet;
+use std::ops::Deref;
+use std::rc::{Rc, Weak};
+
+#[derive(Clone, Debug)]
+pub struct Symbol(Rc<str>);
+
+impl PartialEq for Symbol {
+    fn eq(&self, other: &Symbol) -> bool {
+        Rc::ptr_eq(&self.0, &other.0)
+    }
+}
+
+impl Eq for Symbol {}
+
+impl Deref for Symbol {
+    type Target = str;
+    fn deref(&self) -> &str {
+        &self.0
+    }
+}
+
+#[derive(Debug, Default)]
+pub struct SymbolTable(WeakHashSet<Weak<str>>);
+
+impl SymbolTable {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    pub fn intern(&mut self, name: &str) -> Symbol {
+        if let Some(rc) = self.0.get(name) {
+            Symbol(rc)
+        } else {
+            let rc = Rc::<str>::from(name);
+            self.0.insert(Rc::clone(&rc));
+            Symbol(rc)
+        }
+    }
+}
+
+#[test]
+fn interning() {
+    let mut tab = SymbolTable::new();
+
+    let a0 = tab.intern("a");
+    let a1 = tab.intern("a");
+    let b  = tab.intern("b");
+
+    assert_eq!(a0, a1);
+    assert_ne!(a0, b);
+}
diff --git a/tests/weak_key_hash_map.rs b/tests/weak_key_hash_map.rs
new file mode 100644
index 0000000..fe18890
--- /dev/null
+++ b/tests/weak_key_hash_map.rs
@@ -0,0 +1,163 @@
+use std::collections::HashMap;
+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;
+
+use self::Cmd::*;
+
+fn test_script<K, V>(script: &Script<K, V>) -> bool
+    where K: Clone + Debug + Eq + Hash,
+          V: Clone + Debug + Eq
+{
+    let mut tester = Tester::with_capacity(4);
+    tester.execute_script(script);
+    tester.check()
+}
+
+quickcheck! {
+    fn prop_u8_u8(script: Script<u8, u8>) -> bool {
+        test_script(&script)
+    }
+
+    fn prop_string_usize(script: Script<String, usize>) -> bool {
+        test_script(&script)
+    }
+}
+
+#[derive(Clone, Debug)]
+pub enum Cmd<K, V>
+{
+    Insert(K, V),
+    Reinsert(usize, V),
+    RemoveInserted(usize),
+    RemoveOther(K),
+    ForgetInserted(usize),
+}
+
+#[derive(Clone, Debug)]
+pub struct Script<K, V>(Vec<Cmd<K, V>>);
+
+#[derive(Clone, Debug)]
+pub struct Tester<K: Hash + Eq, V> {
+    weak:   WeakKeyHashMap<Weak<K>, V>,
+    strong: HashMap<Rc<K>, V>,
+    log:    Vec<K>,
+}
+
+impl<K, V> Tester<K, V>
+    where K: Hash + Eq + Clone + Debug,
+          V: Eq + Clone + Debug
+{
+    pub fn new() -> Self {
+        Tester::with_capacity(8)
+    }
+
+    pub fn with_capacity(capacity: usize) -> Self {
+        Tester {
+            weak:   WeakKeyHashMap::with_capacity(capacity),
+            strong: HashMap::new(),
+            log:    Vec::new(),
+        }
+    }
+
+    pub fn check(&self) -> bool {
+        let copy = self.weak.iter().map(|(k, v)| (k, v.clone())).collect();
+        if self.strong == copy {
+//            eprintln!("Tester::check: succeeded: {:?}", self.weak);
+            true
+        } else {
+            eprintln!("Tester::check: failed: {:?} ≠ {:?}", self.strong, copy);
+            false
+        }
+    }
+
+    pub fn execute_script(&mut self, script: &Script<K, V>) {
+//        eprintln!("\n*** Starting script ***");
+        for cmd in &script.0 {
+            self.execute_command(cmd);
+        }
+    }
+
+    pub fn execute_command(&mut self, cmd: &Cmd<K, V>) {
+//        eprintln!("Executing command: {:?}", cmd);
+        match *cmd {
+            Insert(ref k, ref v)    => self.insert(k, v, true),
+            Reinsert(index, ref v)  => self.reinsert(index, v),
+            RemoveInserted(index)   => self.remove_inserted(index),
+            RemoveOther(ref k)      => self.remove_other(k),
+            ForgetInserted(index)   => self.forget_inserted(index),
+        }
+//        eprintln!("Table state: {:?}", self.weak);
+    }
+
+    pub fn insert(&mut self, key: &K, value: &V, log: bool) {
+        let key_ptr = Rc::new(key.clone());
+        self.weak.insert(key_ptr.clone(), value.clone());
+        self.strong.remove(key);
+        self.strong.insert(key_ptr, value.clone());
+        if log { self.log.push(key.clone()); }
+    }
+
+    pub fn reinsert(&mut self, index: usize, value: &V) {
+        if let Some(key) = self.nth_key_mod_len(index) {
+            self.insert(&key, value, false);
+        }
+    }
+
+    pub fn remove_inserted(&mut self, index: usize) {
+        if let Some(key) = self.nth_key_mod_len(index) {
+            self.strong.remove(&key);
+            self.weak.remove(&key);
+        }
+    }
+
+    pub fn remove_other(&mut self, key: &K) {
+        self.strong.remove(key);
+        self.weak.remove(key);
+    }
+
+    pub fn forget_inserted(&mut self, index: usize) {
+        if let Some(key) = self.nth_key_mod_len(index) {
+            self.strong.remove(&key);
+        }
+    }
+
+    fn nth_key_mod_len(&self, n: usize) -> Option<K>
+    {
+        if self.log.is_empty() {
+            None
+        } else {
+            Some(self.log[n % self.log.len()].clone())
+        }
+    }
+}
+
+impl<K: Arbitrary, V: Arbitrary> Arbitrary for Cmd<K, V> {
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+        let choice = g.gen_range(0, 100);
+
+        match choice {
+            00..=39 => Insert(K::arbitrary(g), V::arbitrary(g)),
+            40..=49 => Reinsert(usize::arbitrary(g), V::arbitrary(g)),
+            50..=69 => RemoveInserted(usize::arbitrary(g)),
+            70..=79 => RemoveOther(K::arbitrary(g)),
+            80..=99 => ForgetInserted(usize::arbitrary(g)),
+            _       => unreachable!(),
+        }
+    }
+}
+
+impl<K: Arbitrary, V: Arbitrary> Arbitrary for Script<K, V> {
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+        Script(Vec::<Cmd<K, V>>::arbitrary(g))
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item=Self>> {
+        Box::new(self.0.shrink().map(|v| Script(v)))
+    }
+}