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.

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 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

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

Method is_empty

fn is_empty(&self) -> bool

Return true if the map contains no elements

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 contains_key

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

Return true if the map contains a value for the specified key

Method find

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

Return a reference to the value corresponding to the key

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 insert

fn insert(&mut self, k: K, v: V) -> bool

Insert a key-value pair into the map. An existing value for a key is replaced by the new value. Return true if the key did not already exist in the map.

Method remove

fn remove(&mut self, k: &K) -> bool

Remove a key-value pair from the map. Return true if the key was present in the map, otherwise false.

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 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 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 consume

fn consume(&mut self, f: &fn(K, V))

Calls a function on each element of a hash map, destroying the hash map in the process.

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 mutate_values

fn mutate_values(&mut self, blk: &fn(&K, &mut V) -> bool) -> bool

Iterate over the map and mutate the contained 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).

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

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 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<&'self K> for HashSetIterator<'self, K> where <'self, K>

Method next

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

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

Method is_empty

fn is_empty(&self) -> bool

Return true if the set contains no elements

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 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.

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

Method difference

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

Visit the values representing the difference

Method symmetric_difference

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

Visit the values representing the symmetric difference

Method intersection

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

Visit the values representing the intersection

Method union

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

Visit the values representing the union

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 consume

fn consume(&mut self, f: &fn(T))

Consumes all of the elements in the set, emptying it out

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.

Function linear_map_with_capacity

fn linear_map_with_capacity<K: Eq + Hash, V>(initial_capacity: uint) ->
 HashMap<K, V>

Creates a new hash map with the specified capacity.