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.
HashMap
- A hash map implementation which uses linear probing along with the SipHash hash function for internal stateHashMapIterator
- HashMap iteratorHashMapMutIterator
- HashMap mutable values iteratorHashSet
- An implementation of a hash set using the underlying representation of a HashMap where the value is ()HashSetIterator
- HashSet iteratorof Container for HashMap<K, V> where <K: Hash + Eq, V>
of Mutable for HashMap<K, V> where <K: Hash + Eq, V>
of Map<K, V> for HashMap<K, V> where <K: Hash + Eq, V>
for HashMap<K, V> where <K: Hash + Eq, V>
for HashMap<K, V> where <K: Hash + Eq, V: Copy>
of Eq for HashMap<K, V> where <K: Hash + Eq, V: Eq>
of Iterator<(&'self K, &'self V)> for HashMapIterator<'self, K, V> where <'self, K, V>
of Iterator<(&'self K, &'self mut V)> for HashMapMutIterator<'self, K, V> where <'self, K, V>
of Iterator<&'self K> for HashSetIterator<'self, K> where <'self, K>
of Eq for HashSet<T> where <T: Hash + Eq>
of Container for HashSet<T> where <T: Hash + Eq>
of Mutable for HashSet<T> where <T: Hash + Eq>
of Set<T> for HashSet<T> where <T: Hash + Eq>
for HashSet<T> where <T: Hash + Eq>
linear_map_with_capacity
- Creates a new hash map with the specified capacity.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
.
HashMapIterator
pub struct HashMapIterator<'self, K, V> {
priv iter: vec::VecIterator<'self, Option<Bucket<K, V>>>,
}
HashMap iterator
HashMapMutIterator
pub struct HashMapMutIterator<'self, K, V> {
priv iter: vec::VecMutIterator<'self, Option<Bucket<K, V>>>,
}
HashMap mutable values iterator
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.
HashSetIterator
pub struct HashSetIterator<'self, K> {
priv iter: vec::VecIterator<'self, Option<Bucket<K, ()>>>,
}
HashSet iterator
Container
for HashMap<K, V>
where <K: Hash + Eq, V>
len
fn len(&self) -> uint
Return the number of elements in the map
is_empty
fn is_empty(&self) -> bool
Return true if the map contains no elements
Mutable
for HashMap<K, V>
where <K: Hash + Eq, V>
clear
fn clear(&mut self)
Clear the map, removing all key-value pairs.
Map<K, V>
for HashMap<K, V>
where <K: Hash + Eq, V>
contains_key
fn contains_key(&self, k: &K) -> bool
Return true if the map contains a value for the specified key
find
fn find<'a>(&'a self, k: &K) -> Option<&'a V>
Return a reference to the value corresponding to the key
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
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.
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.
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.
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.
HashMap<K, V>
where <K: Hash + Eq, V>
new
fn new() -> HashMap<K, V>
Create an empty HashMap
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.
reserve_at_least
fn reserve_at_least(&mut self, n: uint)
Reserve space for at least n
elements in the hash table.
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.
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.
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.
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.
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.
get
fn get<'a>(&'a self, k: &K) -> &'a V
Retrieves a value for the given key, failing if the key is not present.
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.
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
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
each_key
fn each_key(&self, blk: &fn(k: &K) -> bool) -> bool
Visit all keys
each_value
fn each_value<'a>(&'a self, blk: &fn(v: &'a V) -> bool) -> bool
Visit all values
mutate_values
fn mutate_values(&mut self, blk: &fn(&K, &mut V) -> bool) -> bool
Iterate over the map and mutate the contained values
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).
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).
HashMap<K, V>
where <K: Hash + Eq, V: Copy>
find_copy
fn find_copy(&self, k: &K) -> Option<V>
Like find
, but returns a copy of the value.
get_copy
fn get_copy(&self, k: &K) -> V
Like get
, but returns a copy of the value.
Eq
for HashMap<K, V>
where <K: Hash + Eq, V: Eq>
eq
fn eq(&self, other: &HashMap<K, V>) -> bool
ne
fn ne(&self, other: &HashMap<K, V>) -> bool
Iterator<(&'self K, &'self V)>
for HashMapIterator<'self, K, V>
where <'self, K, V>
next
fn next(&mut self) -> Option<(&'self K, &'self V)>
Iterator<(&'self K, &'self mut V)>
for HashMapMutIterator<'self, K, V>
where <'self, K, V>
next
fn next(&mut self) -> Option<(&'self K, &'self mut V)>
Iterator<&'self K>
for HashSetIterator<'self, K>
where <'self, K>
next
fn next(&mut self) -> Option<&'self K>
Eq
for HashSet<T>
where <T: Hash + Eq>
eq
fn eq(&self, other: &HashSet<T>) -> bool
ne
fn ne(&self, other: &HashSet<T>) -> bool
Container
for HashSet<T>
where <T: Hash + Eq>
len
fn len(&self) -> uint
Return the number of elements in the set
is_empty
fn is_empty(&self) -> bool
Return true if the set contains no elements
Mutable
for HashSet<T>
where <T: Hash + Eq>
clear
fn clear(&mut self)
Clear the set, removing all values.
Set<T>
for HashSet<T>
where <T: Hash + Eq>
contains
fn contains(&self, value: &T) -> bool
Return true if the set contains a value
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.
remove
fn remove(&mut self, value: &T) -> bool
Remove a value from the set. Return true if the value was present in the set.
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.
is_subset
fn is_subset(&self, other: &HashSet<T>) -> bool
Return true if the set is a subset of another
is_superset
fn is_superset(&self, other: &HashSet<T>) -> bool
Return true if the set is a superset of another
difference
fn difference(&self, other: &HashSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values representing the difference
symmetric_difference
fn symmetric_difference(&self, other: &HashSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values representing the symmetric difference
intersection
fn intersection(&self, other: &HashSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values representing the intersection
union
fn union(&self, other: &HashSet<T>, f: &fn(&T) -> bool) -> bool
Visit the values representing the union
HashSet<T>
where <T: Hash + Eq>
new
fn new() -> HashSet<T>
Create an empty HashSet
with_capacity
fn with_capacity(capacity: uint) -> HashSet<T>
Create an empty HashSet with space for at least n
elements in the hash table.
reserve_at_least
fn reserve_at_least(&mut self, n: uint)
Reserve space for at least n
elements in the hash table.
consume
fn consume(&mut self, f: &fn(T))
Consumes all of the elements in the set, emptying it out
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.
iter
fn iter<'a>(&'a self) -> HashSetIterator<'a, T>
An iterator visiting all elements in arbitrary order. Iterator element type is &'a T.
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.