Struct std::collections::hashmap::HashMap[src]
pub struct HashMap<K, V, H = SipHasher> {
// 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 overridden 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
fn main() { use std::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 Huckleberry Finn", "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); } }use std::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 Huckleberry Finn", "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: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H>
fn pop_equiv<Q: Hash<S> + Equiv<K>>(&mut self, k: &Q) -> Option<V>
Like pop, but can operate on any type that is equivalent to a key.
impl<K: Hash + Eq, V> HashMap<K, V, SipHasher>
fn new() -> HashMap<K, V, SipHasher>
Create an empty HashMap.
fn with_capacity(capacity: uint) -> HashMap<K, V, SipHasher>
Creates an empty hash map with the given initial capacity.
impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H>
fn with_hasher(hasher: H) -> HashMap<K, V, H>
Creates an empty hashmap which will use the given hasher to hash keys.
The creates map has the default initial capacity.
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 find_with_or_insert_with<'a, A>(&'a mut self, k: K, a: A, found: |&K, &mut V, A|, not_found: |&K, A| -> V) -> &'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.
This method allows for all insertion behaviours of a hashmap;
see methods like insert, find_or_insert and
insert_or_update_with for less general and more friendly
variations of this.
Example
fn main() { use std::collections::HashMap; // map some strings to vectors of strings let mut map = HashMap::new(); map.insert("a key", vec!["value"]); map.insert("z key", vec!["value"]); let new = vec!["a key", "b key", "z key"]; for k in new.move_iter() { map.find_with_or_insert_with( k, "new value", // if the key does exist either prepend or append this // new value based on the first letter of the key. |key, already, new| { if key.as_slice().starts_with("z") { already.unshift(new); } else { already.push(new); } }, // if the key doesn't exist in the map yet, add it in // the obvious way. |_k, v| vec![v]); } assert_eq!(map.len(), 3); assert_eq!(map.get(&"a key"), &vec!["value", "new value"]); assert_eq!(map.get(&"b key"), &vec!["new value"]); assert_eq!(map.get(&"z key"), &vec!["new value", "value"]); }use std::collections::HashMap; // map some strings to vectors of strings let mut map = HashMap::new(); map.insert("a key", vec!["value"]); map.insert("z key", vec!["value"]); let new = vec!["a key", "b key", "z key"]; for k in new.move_iter() { map.find_with_or_insert_with( k, "new value", // if the key does exist either prepend or append this // new value based on the first letter of the key. |key, already, new| { if key.as_slice().starts_with("z") { already.unshift(new); } else { already.push(new); } }, // if the key doesn't exist in the map yet, add it in // the obvious way. |_k, v| vec![v]); } assert_eq!(map.len(), 3); assert_eq!(map.get(&"a key"), &vec!["value", "new value"]); assert_eq!(map.get(&"b key"), &vec!["new value"]); assert_eq!(map.get(&"z key"), &vec!["new value", "value"]);
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: Eq + 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: Eq + Hash<S>, V, S, H: Hasher<S>> Collection for HashMap<K, V, H>
impl<K: Eq + 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. Keeps the allocated memory for reuse.