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.
SetAlgebraIter
- Set operations iteratorHashMap
- A hash map implementation which uses linear probing along with the SipHash hash function for internal stateHashMapIterator
- HashMap iteratorHashMapMoveIterator
- HashMap move iteratorHashMapMutIterator
- HashMap mutable values iteratorHashSet
- An implementation of a hash set using the underlying representation of a HashMap where the value is ()HashSetIterator
- HashSet iteratorHashSetMoveIterator
- HashSet move 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>
of MutableMap<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: Clone>
of Eq for HashMap<K, V> where <K: Hash + Eq, V: Eq>
of Clone for HashMap<K, V> where <K: Hash + Eq + Clone, V: Clone>
of ::std::clone::Clone for HashMapIterator<'self, K, V> where <'self, K: ::std::clone::Clone, V: ::std::clone::Clone>
- Automatically derived.of ::std::clone::Clone for HashSetIterator<'self, K> where <'self, K: ::std::clone::Clone>
- Automatically derived.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<(K, V)> for HashMapMoveIterator<K, V> where <K, V>
of Iterator<&'self K> for HashSetIterator<'self, K> where <'self, K>
of Iterator<K> for HashSetMoveIterator<K> where <K>
of FromIterator<(K, V)> for HashMap<K, V> where <K: Eq + Hash, V>
of Extendable<(K, V)> for HashMap<K, V> where <K: Eq + Hash, V>
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>
of MutableSet<T> for HashSet<T> where <T: Hash + Eq>
for HashSet<T> where <T: Hash + Eq>
of Clone for HashSet<T> where <T: Hash + Eq + Clone>
of FromIterator<K> for HashSet<K> where <K: Eq + Hash>
of Extendable<K> for HashSet<K> where <K: Eq + Hash>
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
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
HashMapMoveIterator
pub struct HashMapMoveIterator<K, V> {
priv iter: vec::MoveRevIterator<Option<Bucket<K, V>>>,
}
HashMap move 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
HashSetMoveIterator
pub struct HashSetMoveIterator<K> {
priv iter: vec::MoveRevIterator<Option<Bucket<K, ()>>>,
}
HashSet move iterator
Container
for HashMap<K, V>
where <K: Hash + Eq, V>
len
fn len(&self) -> uint
Return the number of elements in the map
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>
find
fn find<'a>(&'a self, k: &K) -> Option<&'a V>
Return a reference to the value corresponding to the key
MutableMap<K, V>
for HashMap<K, V>
where <K: Hash + Eq, V>
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
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 capacity
elements in the hash table.
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.
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.
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
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).
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.
HashMap<K, V>
where <K: Hash + Eq, V: Clone>
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
Clone
for HashMap<K, V>
where <K: Hash + Eq + Clone, V: Clone>
clone
fn clone(&self) -> HashMap<K, V>
::std::clone::Clone
for HashMapIterator<'self, K, V>
where <'self, K: ::std::clone::Clone, V: ::std::clone::Clone>
Automatically derived.
clone
fn clone(&self) -> HashMapIterator<'self, K, V>
::std::clone::Clone
for HashSetIterator<'self, K>
where <'self, K: ::std::clone::Clone>
Automatically derived.
clone
fn clone(&self) -> HashSetIterator<'self, K>
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<(K, V)>
for HashMapMoveIterator<K, V>
where <K, V>
next
fn next(&mut self) -> Option<(K, V)>
Iterator<&'self K>
for HashSetIterator<'self, K>
where <'self, K>
next
fn next(&mut self) -> Option<&'self K>
Iterator<K>
for HashSetMoveIterator<K>
where <K>
next
fn next(&mut self) -> Option<K>
FromIterator<(K, V)>
for HashMap<K, V>
where <K: Eq + Hash, V>
from_iterator
fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> HashMap<K, V>
Extendable<(K, V)>
for HashMap<K, V>
where <K: Eq + Hash, V>
extend
fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T)
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
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
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
MutableSet<T>
for HashSet<T>
where <T: Hash + Eq>
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.
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.
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.
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.
difference_iter
fn difference_iter<'a>(&'a self, other: &'a HashSet<T>) ->
SetAlgebraIter<'a, T>
Visit the values representing the difference
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
intersection_iter
fn intersection_iter<'a>(&'a self, other: &'a HashSet<T>) ->
SetAlgebraIter<'a, T>
Visit the values representing the intersection
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
Clone
for HashSet<T>
where <T: Hash + Eq + Clone>
clone
fn clone(&self) -> HashSet<T>
FromIterator<K>
for HashSet<K>
where <K: Eq + Hash>
from_iterator
fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K>
Extendable<K>
for HashSet<K>
where <K: Eq + Hash>
extend
fn extend<T: Iterator<K>>(&mut self, iter: &mut T)