Struct collections::hashmap::HashMap
pub struct HashMap<K, V, H> {
// some fields omitted
}A hash map implementation which uses linear probing with Robin Hood bucket stealing.
The hashes are all keyed by the task-local random number generator on creation by default, this means the ordering of the keys is randomized, but makes the tables more resistant to denial-of-service attacks (Hash DoS). This behaviour can be overriden with one of the constructors.
It is required that the keys implement the Eq and Hash traits, although
this can frequently be achieved by using #[deriving(Eq, Hash)].
Relevant papers/articles:
- Pedro Celis. "Robin Hood Hashing"
- Emmanuel Goossaert. "Robin Hood hashing"
- Emmanuel Goossaert. "Robin Hood hashing: backward shift deletion"
Example
use collections::HashMap; // type inference lets us omit an explicit type signature (which // would be `HashMap<&str, &str>` in this example). let mut book_reviews = HashMap::new(); // review some books. book_reviews.insert("Adventures of Hucklebury Fin", "My favorite book."); book_reviews.insert("Grimms' Fairy Tales", "Masterpiece."); book_reviews.insert("Pride and Prejudice", "Very enjoyable."); book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot."); // check for a specific one. if !book_reviews.contains_key(& &"Les Misérables") { println!("We've got {} reviews, but Les Misérables ain't one.", book_reviews.len()); } // oops, this review has a lot of spelling mistakes, let's delete it. book_reviews.remove(& &"The Adventures of Sherlock Holmes"); // look up the values associated with some keys. let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; for book in to_find.iter() { match book_reviews.find(book) { Some(review) => println!("{}: {}", *book, *review), None => println!("{} is unreviewed.", *book) } } // iterate over everything. for (book, review) in book_reviews.iter() { println!("{}: \"{}\"", *book, *review); }
Methods
impl<K: Hash + TotalEq, V> HashMap<K, V, SipHasher>
fn new() -> HashMap<K, V, SipHasher>
Create an empty HashMap.
fn with_capacity(capacity: uint) -> HashMap<K, V, SipHasher>
impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H>
fn with_hasher(hasher: H) -> HashMap<K, V, H>
fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashMap<K, V, H>
Create an empty HashMap with space for at least capacity
elements, using hasher to hash the keys.
Warning: hasher is normally randomly generated, and
is designed to allow HashMaps to be resistant to attacks that
cause many collisions and very poor performance. Setting it
manually using this function can expose a DoS attack vector.
fn reserve(&mut self, new_minimum_capacity: uint)
The hashtable will never try to shrink below this size. You can use this function to reduce reallocations if your hashtable frequently grows and shrinks by large amounts.
This function has no effect on the operational semantics of the hashtable, only on performance.
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.
fn find_or_insert_with<'a>(&'a mut self, k: K, f: |&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.
fn insert_or_update_with<'a>(&'a mut self, k: K, v: V, f: |&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.
fn get<'a>(&'a self, k: &K) -> &'a V
Retrieves a value for the given key, failing if the key is not present.
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.
fn contains_key_equiv<Q: Hash<S> + Equiv<K>>(&self, key: &Q) -> bool
Return true if the map contains a value for the specified key, using equivalence.
fn find_equiv<'a, Q: Hash<S> + Equiv<K>>(&'a self, k: &Q) -> Option<&'a V>
Return the value corresponding to the key in the map, using equivalence.
fn keys<'a>(&'a self) -> Keys<'a, K, V>
An iterator visiting all keys in arbitrary order. Iterator element type is &'a K.
fn values<'a>(&'a self) -> Values<'a, K, V>
An iterator visiting all values in arbitrary order. Iterator element type is &'a V.
fn iter<'a>(&'a self) -> Entries<'a, K, V>
An iterator visiting all key-value pairs in arbitrary order. Iterator element type is (&'a K, &'a V).
fn mut_iter<'a>(&'a mut self) -> MutEntries<'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).
fn move_iter(self) -> MoveEntries<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.
impl<K: TotalEq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H>
fn find_copy(&self, k: &K) -> Option<V>
Like find, but returns a copy of the value.
fn get_copy(&self, k: &K) -> V
Like get, but returns a copy of the value.
Trait Implementations
impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Container for HashMap<K, V, H>
fn len(&self) -> uint
Return the number of elements in the map
impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H>
fn clear(&mut self)
Clear the map, removing all key-value pairs.