An unordered map and set type implemented as hash tables

The tables use a keyed hash with new random keys generated for each container, so the ordering of a set of keys in a hash table is randomized.

Type SetAlgebraIter

type SetAlgebraIter<'self, T> = FilterMap<'static,
(&'self HashSet<T>, &'self T), &'self T,
Zip<Repeat<&'self HashSet<T>>, HashSetIterator<'self, T>>>

Set operations iterator

Struct HashMap

pub struct HashMap<K, V> {
    priv k0: u64,
    priv k1: u64,
    priv resize_at: uint,
    priv size: uint,
    priv buckets: ~[Option<Bucket<K, V>>],
}

A hash map implementation which uses linear probing along with the SipHash hash function for internal state. This means that the order of all hash maps is randomized by keying each hash map randomly on creation.

It is required that the keys implement the Eq and Hash traits, although this can frequently be achieved by just implementing the Eq and IterBytes traits as Hash is automatically implemented for types that implement IterBytes.

Struct HashMapIterator

pub struct HashMapIterator<'self, K, V> {
    priv iter: vec::VecIterator<'self, Option<Bucket<K, V>>>,
}

HashMap iterator

Struct HashMapMoveIterator

pub struct HashMapMoveIterator<K, V> {
    priv iter: vec::MoveRevIterator<Option<Bucket<K, V>>>,
}

HashMap move iterator

Struct HashMapMutIterator

pub struct HashMapMutIterator<'self, K, V> {
    priv iter: vec::VecMutIterator<'self, Option<Bucket<K, V>>>,
}

HashMap mutable values iterator

Struct HashSet

pub struct HashSet<T> {
    priv map: HashMap<T, ()>,
}

An implementation of a hash set using the underlying representation of a HashMap where the value is (). As with the HashMap type, a HashSet requires that the elements implement the Eq and Hash traits.

Struct HashSetIterator

pub struct HashSetIterator<'self, K> {
    priv iter: vec::VecIterator<'self, Option<Bucket<K, ()>>>,
}

HashSet iterator

Struct HashSetMoveIterator

pub struct HashSetMoveIterator<K> {
    priv iter: vec::MoveRevIterator<Option<Bucket<K, ()>>>,
}

HashSet move iterator

Implementation of Container for HashMap<K, V> where <K: Hash + Eq, V>

Method len

fn len(&self) -> uint

Return the number of elements in the map

Implementation of Mutable for HashMap<K, V> where <K: Hash + Eq, V>

Method clear

fn clear(&mut self)

Clear the map, removing all key-value pairs.

Implementation of Map<K, V> for HashMap<K, V> where <K: Hash + Eq, V>

Method find

fn find<'a>(&'a self, k: &K) -> Option<&'a V>

Return a reference to the value corresponding to the key

Implementation of MutableMap<K, V> for HashMap<K, V> where <K: Hash + Eq, V>

Method find_mut

fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V>

Return a mutable reference to the value corresponding to the key

Method swap

fn swap(&mut self, k: K, v: V) -> Option<V>

Insert a key-value pair from the map. If the key already had a value present in the map, that value is returned. Otherwise None is returned.

Method pop

fn pop(&mut self, k: &K) -> Option<V>

Removes a key from the map, returning the value at the key if the key was previously in the map.

Implementation for HashMap<K, V> where <K: Hash + Eq, V>

Method new

fn new() -> HashMap<K, V>

Create an empty HashMap

Method with_capacity

fn with_capacity(capacity: uint) -> HashMap<K, V>

Create an empty HashMap with space for at least capacity elements in the hash table.

Method with_capacity_and_keys

fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashMap<K, V>

Create an empty HashMap with space for at least capacity elements, using k0 and k1 as the keys.

Warning: k0 and k1 are normally randomly generated, and are designed to allow HashMaps to be resistant to attacks that cause many collisions and very poor performance. Setting them manually using this function can expose a DoS attack vector.

Method reserve_at_least

fn reserve_at_least(&mut self, n: uint)

Reserve space for at least n elements in the hash table.

Method mangle

fn mangle<'a,
          A>(&'a mut self, k: K, a: A, not_found: &fn(&K, A) -> V,
             found: &fn(&K, &mut V, A)) -> &'a mut V

Modify and return the value corresponding to the key in the map, or insert and return a new value if it doesn't exist.

Method find_or_insert

fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a mut V

Return the value corresponding to the key in the map, or insert and return the value if it doesn't exist.

Method find_or_insert_with

fn find_or_insert_with<'a>(&'a mut self, k: K, f: &fn(&K) -> V) -> &'a mut V

Return the value corresponding to the key in the map, or create, insert, and return a new value if it doesn't exist.

Method insert_or_update_with

fn insert_or_update_with<'a>(&'a mut self, k: K, v: V, f: &fn(&K, &mut V)) ->
 &'a mut V

Insert a key-value pair into the map if the key is not already present. Otherwise, modify the existing value for the key. Returns the new or modified value for the key.

Method get

fn get<'a>(&'a self, k: &K) -> &'a V

Retrieves a value for the given key, failing if the key is not present.

Method get_mut

fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V

Retrieves a (mutable) value for the given key, failing if the key is not present.

Method contains_key_equiv

fn contains_key_equiv<Q: Hash + Equiv<K>>(&self, key: &Q) -> bool

Return true if the map contains a value for the specified key, using equivalence

Method find_equiv

fn find_equiv<'a, Q: Hash + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V>

Return the value corresponding to the key in the map, using equivalence

Method each_key

fn each_key(&self, blk: &fn(k: &K) -> bool) -> bool

Visit all keys

Method each_value

fn each_value<'a>(&'a self, blk: &fn(v: &'a V) -> bool) -> bool

Visit all values

Method iter

fn iter<'a>(&'a self) -> HashMapIterator<'a, K, V>

An iterator visiting all key-value pairs in arbitrary order. Iterator element type is (&'a K, &'a V).

Method mut_iter

fn mut_iter<'a>(&'a mut self) -> HashMapMutIterator<'a, K, V>

An iterator visiting all key-value pairs in arbitrary order, with mutable references to the values. Iterator element type is (&'a K, &'a mut V).

Method move_iter

fn move_iter(self) -> HashMapMoveIterator<K, V>

Creates a consuming iterator, that is, one that moves each key-value pair out of the map in arbitrary order. The map cannot be used after calling this.

Implementation for HashMap<K, V> where <K: Hash + Eq, V: Clone>

Method find_copy

fn find_copy(&self, k: &K) -> Option<V>

Like find, but returns a copy of the value.

Method get_copy

fn get_copy(&self, k: &K) -> V

Like get, but returns a copy of the value.

Implementation of Eq for HashMap<K, V> where <K: Hash + Eq, V: Eq>

Method eq

fn eq(&self, other: &HashMap<K, V>) -> bool

Method ne

fn ne(&self, other: &HashMap<K, V>) -> bool

Implementation of Clone for HashMap<K, V> where <K: Hash + Eq + Clone, V: Clone>

Method clone

fn clone(&self) -> HashMap<K, V>

Implementation of ::std::clone::Clone for HashMapIterator<'self, K, V> where <'self, K: ::std::clone::Clone, V: ::std::clone::Clone>

Automatically derived.

Method clone

fn clone(&self) -> HashMapIterator<'self, K, V>

Implementation of ::std::clone::Clone for HashSetIterator<'self, K> where <'self, K: ::std::clone::Clone>

Automatically derived.

Method clone

fn clone(&self) -> HashSetIterator<'self, K>

Implementation of Iterator<(&'self K, &'self V)> for HashMapIterator<'self, K, V> where <'self, K, V>

Method next

fn next(&mut self) -> Option<(&'self K, &'self V)>

Implementation of Iterator<(&'self K, &'self mut V)> for HashMapMutIterator<'self, K, V> where <'self, K, V>

Method next

fn next(&mut self) -> Option<(&'self K, &'self mut V)>

Implementation of Iterator<(K, V)> for HashMapMoveIterator<K, V> where <K, V>

Method next

fn next(&mut self) -> Option<(K, V)>

Implementation of Iterator<&'self K> for HashSetIterator<'self, K> where <'self, K>

Method next

fn next(&mut self) -> Option<&'self K>

Implementation of Iterator<K> for HashSetMoveIterator<K> where <K>

Method next

fn next(&mut self) -> Option<K>

Implementation of FromIterator<(K, V)> for HashMap<K, V> where <K: Eq + Hash, V>

Method from_iterator

fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> HashMap<K, V>

Implementation of Extendable<(K, V)> for HashMap<K, V> where <K: Eq + Hash, V>

Method extend

fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T)

Implementation of Eq for HashSet<T> where <T: Hash + Eq>

Method eq

fn eq(&self, other: &HashSet<T>) -> bool

Method ne

fn ne(&self, other: &HashSet<T>) -> bool

Implementation of Container for HashSet<T> where <T: Hash + Eq>

Method len

fn len(&self) -> uint

Return the number of elements in the set

Implementation of Mutable for HashSet<T> where <T: Hash + Eq>

Method clear

fn clear(&mut self)

Clear the set, removing all values.

Implementation of Set<T> for HashSet<T> where <T: Hash + Eq>

Method contains

fn contains(&self, value: &T) -> bool

Return true if the set contains a value

Method is_disjoint

fn is_disjoint(&self, other: &HashSet<T>) -> bool

Return true if the set has no elements in common with other. This is equivalent to checking for an empty intersection.

Method is_subset

fn is_subset(&self, other: &HashSet<T>) -> bool

Return true if the set is a subset of another

Method is_superset

fn is_superset(&self, other: &HashSet<T>) -> bool

Return true if the set is a superset of another

Implementation of MutableSet<T> for HashSet<T> where <T: Hash + Eq>

Method insert

fn insert(&mut self, value: T) -> bool

Add a value to the set. Return true if the value was not already present in the set.

Method remove

fn remove(&mut self, value: &T) -> bool

Remove a value from the set. Return true if the value was present in the set.

Implementation for HashSet<T> where <T: Hash + Eq>

Method new

fn new() -> HashSet<T>

Create an empty HashSet

Method with_capacity

fn with_capacity(capacity: uint) -> HashSet<T>

Create an empty HashSet with space for at least n elements in the hash table.

Method reserve_at_least

fn reserve_at_least(&mut self, n: uint)

Reserve space for at least n elements in the hash table.

Method contains_equiv

fn contains_equiv<Q: Hash + Equiv<T>>(&self, value: &Q) -> bool

Returns true if the hash set contains a value equivalent to the given query value.

Method iter

fn iter<'a>(&'a self) -> HashSetIterator<'a, T>

An iterator visiting all elements in arbitrary order. Iterator element type is &'a T.

Method move_iter

fn move_iter(self) -> HashSetMoveIterator<T>

Creates a consuming iterator, that is, one that moves each value out of the set in arbitrary order. The set cannot be used after calling this.

Method difference_iter

fn difference_iter<'a>(&'a self, other: &'a HashSet<T>) ->
 SetAlgebraIter<'a, T>

Visit the values representing the difference

Method symmetric_difference_iter

fn symmetric_difference_iter<'a>(&'a self, other: &'a HashSet<T>) ->
 Chain<SetAlgebraIter<'a, T>, SetAlgebraIter<'a, T>>

Visit the values representing the symmetric difference

Method intersection_iter

fn intersection_iter<'a>(&'a self, other: &'a HashSet<T>) ->
 SetAlgebraIter<'a, T>

Visit the values representing the intersection

Method union_iter

fn union_iter<'a>(&'a self, other: &'a HashSet<T>) ->
 Chain<HashSetIterator<'a, T>, SetAlgebraIter<'a, T>>

Visit the values representing the union

Implementation of Clone for HashSet<T> where <T: Hash + Eq + Clone>

Method clone

fn clone(&self) -> HashSet<T>

Implementation of FromIterator<K> for HashSet<K> where <K: Eq + Hash>

Method from_iterator

fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K>

Implementation of Extendable<K> for HashSet<K> where <K: Eq + Hash>

Method extend

fn extend<T: Iterator<K>>(&mut self, iter: &mut T)