Struct hash_ord::hash_map::HashMap [−][src]
pub struct HashMap<K, V, S = RandomState> { /* fields omitted */ }
A hash map which uses AVL to resolve collision.
Usually, hashing algorithm seems to play an important role in HashMap. However, any generated hash-value needs to be mapped into a limited collection, and that will brings in collision. Since collision is unavoidable, in this lib, we focus on solving problem in the worst case, such as Collision-Attack.
As a kind of Self-Balancing BST, AVL is not worse than RBTree, and has a few advantages like simpler structure and smaller height. So we put an AVL under every Hash-Index to resolve collision. When facing Collision Attack, the runtime complexity of STL HashMap is O(n*n), but ours is just O(n log n).
To improve performance, raw pointer is used frequently. Because Rust uses a similar memory model
to C/C++, two classic macros offset_of
and container_of
are used to dereference member
variables into main struct. Fastbin
is implemented to reduce the cost of memory allocation.
Examples
use hash_ord::hash_map::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 { match book_reviews.get(book) { Some(review) => println!("{}: {}", book, review), None => println!("{} is unreviewed.", book) } } // iterate over everything. for (book, review) in &book_reviews { println!("{}: \"{}\"", book, review); }
HashMap
also implements an Entry API
, which allows
for more complex methods of getting, setting, updating and removing keys and
their values:
use hash_ord::hash_map::HashMap; // type inference lets us omit an explicit type signature (which // would be `HashMap<&str, u8>` in this example). let mut player_stats = HashMap::new(); fn random_stat_buff() -> u8 { // could actually return some random value here - let's just return // some fixed value for now 42 } // insert a key only if it doesn't already exist player_stats.entry("health").or_insert(100); // insert a key using a function that provides a new value only if it // doesn't already exist player_stats.entry("defence").or_insert_with(random_stat_buff); // update a key, guarding against the key possibly not being set let stat = player_stats.entry("attack").or_insert(100); *stat += random_stat_buff();
The easiest way to use HashMap
with a custom type as key is to derive Ord
and Hash
.
use hash_ord::hash_map::HashMap; use std::cmp::Ordering; #[derive(Hash, Eq, Debug)] struct Viking { name: String, country: String, } impl Ord for Viking { fn cmp(&self, other: &Self) -> Ordering { let tmp = self.name.cmp(&other.name); return if tmp != Ordering::Equal { tmp } else { self.country.cmp(&other.country) }; } } impl PartialOrd for Viking { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } impl PartialEq for Viking { fn eq(&self, other: &Self) -> bool { self.name == other.name && self.country == other.country } } impl Viking { /// / Create a new Viking. fn new(name: &str, country: &str) -> Viking { Viking { name: name.to_string(), country: country.to_string() } } } // Use a HashMap to store the vikings' health points. let mut vikings = HashMap::new(); vikings.insert(Viking::new("Einar", "Norway"), 25); vikings.insert(Viking::new("Olaf", "Denmark"), 24); vikings.insert(Viking::new("Harald", "Iceland"), 12); // Use derived implementation to print the status of the vikings. for (viking, health) in &vikings { println!("{:?} has {} hp", viking, health); }
A HashMap
with fixed list of elements can be initialized from an array:
use hash_ord::hash_map::HashMap; let timber_resources: HashMap<&str, i32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)] .iter().cloned().collect();
Methods
impl<K, V, S> HashMap<K, V, S>
[src]
impl<K, V, S> HashMap<K, V, S>
pub fn clear(&mut self)
[src]
pub fn clear(&mut self)
Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse.
Examples
use hash_ord::hash_map::HashMap; let mut a = HashMap::new(); a.insert(1, "a"); a.clear(); assert!(a.is_empty());
pub fn capacity(&self) -> usize
[src]
pub fn capacity(&self) -> usize
Returns the number of elements the map can hold without reallocating.
This number is a lower bound; the HashMap<K, V>
might be able to hold
more, but is guaranteed to be able to hold at least this many.
Examples
use std::collections::HashMap; let map: HashMap<isize, isize> = HashMap::with_capacity(100); assert!(map.capacity() >= 100);
pub fn get_max_node_of_single_index(&self) -> i32
[src]
pub fn get_max_node_of_single_index(&self) -> i32
Returns the maximum node count under a simgle HashIndex
pub fn len(&self) -> usize
[src]
pub fn len(&self) -> usize
Returns the number of elements in the map.
Examples
use hash_ord::hash_map::HashMap; let mut a = HashMap::new(); assert_eq!(a.len(), 0); a.insert(1, "a"); assert_eq!(a.len(), 1);
pub fn is_empty(&self) -> bool
[src]
pub fn is_empty(&self) -> bool
Returns true if the map contains no element.
Examples
use hash_ord::hash_map::HashMap; let mut a = HashMap::new(); assert!(a.is_empty()); a.insert(1, "a"); assert!(!a.is_empty());
ⓘImportant traits for Keys<'a, K, V, S>pub fn keys(&self) -> Keys<K, V, S>
[src]
pub fn keys(&self) -> Keys<K, V, S>
An iterator visiting all keys in arbitrary order.
The iterator element type is &'a K
.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert("a", 1); map.insert("b", 2); map.insert("c", 3); for key in map.keys() { println!("{}", key); }
ⓘImportant traits for Values<'a, K, V, S>pub fn values(&self) -> Values<K, V, S>
[src]
pub fn values(&self) -> Values<K, V, S>
An iterator visiting all values in arbitrary order.
The iterator element type is &'a V
.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert("a", 1); map.insert("b", 2); map.insert("c", 3); for val in map.values() { println!("{}", val); }
ⓘImportant traits for ValuesMut<'a, K, V, S>pub fn values_mut(&mut self) -> ValuesMut<K, V, S>
[src]
pub fn values_mut(&mut self) -> ValuesMut<K, V, S>
An iterator visiting all values mutably in arbitrary order.
The iterator element type is &'a mut V
.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert("a", 1); map.insert("b", 2); map.insert("c", 3); for val in map.values_mut() { *val = *val + 10; } for val in map.values() { println!("{}", val); }
ⓘImportant traits for Iter<'a, K, V, S>pub fn iter(&self) -> Iter<K, V, S>
[src]
pub fn iter(&self) -> Iter<K, V, S>
An iterator visiting all key-value pairs in arbitrary order.
The iterator element type is (&'a K, &'a V)
.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert("a", 1); map.insert("b", 2); map.insert("c", 3); for (key, val) in map.iter() { println!("key: {} val: {}", key, val); }
ⓘImportant traits for IterMut<'a, K, V, S>pub fn iter_mut(&mut self) -> IterMut<K, V, S>
[src]
pub fn iter_mut(&mut self) -> IterMut<K, V, S>
An iterator visiting all key-value pairs in arbitrary order,
with mutable references to the values.
The iterator element type is (&'a K, &'a mut V)
.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert("a", 1); map.insert("b", 2); map.insert("c", 3); // Update all values for (_, val) in map.iter_mut() { *val *= 2; } for (key, val) in &map { println!("key: {} val: {}", key, val); }
ⓘImportant traits for Drain<'a, K, V, S>pub fn drain(&mut self) -> Drain<K, V, S>
[src]
pub fn drain(&mut self) -> Drain<K, V, S>
Clears the map, returning all key-value pairs as an iterator. Keeps the allocated memory for reuse.
Examples
use hash_ord::hash_map::HashMap; let mut a = HashMap::new(); a.insert(1, "a"); a.insert(2, "b"); for (k, v) in a.drain().take(1) { assert!(k == 1 || k == 2); assert!(v == "a" || v == "b"); } assert!(a.is_empty());
impl<K, V, S> HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
[src]
impl<K, V, S> HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
pub fn entry(&mut self, key: K) -> Entry<K, V, S>
[src]
pub fn entry(&mut self, key: K) -> Entry<K, V, S>
Gets the given key's corresponding entry in the map for in-place manipulation.
Examples
use hash_ord::hash_map::HashMap; let mut letters = HashMap::new(); for ch in "a short treatise on fungi".chars() { let counter = letters.entry(ch).or_insert(0); *counter += 1; } assert_eq!(letters[&'s'], 2); assert_eq!(letters[&'t'], 3); assert_eq!(letters[&'u'], 1); assert_eq!(letters.get(&'y'), None);
pub fn with_hasher(hash_builder: S) -> Self
[src]
pub fn with_hasher(hash_builder: S) -> Self
Creates an empty HashMap
which will use the given hash builder to hash
keys.
The created map has the default initial capacity.
Warning: hash_builder
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.
Examples
use hash_ord::hash_map::HashMap; use std::collections::hash_map::RandomState; let s = RandomState::new(); let mut map = HashMap::with_hasher(s); map.insert(1, 2);
pub fn get<Q: ?Sized>(&self, q: &Q) -> Option<&V> where
K: Borrow<Q>,
Q: Hash + Ord,
[src]
pub fn get<Q: ?Sized>(&self, q: &Q) -> Option<&V> where
K: Borrow<Q>,
Q: Hash + Ord,
Returns a reference to the value corresponding to the key.
The key may be any borrowed form of the map's key type, but
Hash
and Ord
on the borrowed form must match those for
the key type.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert(1, "a"); assert_eq!(map.get(&1), Some(&"a")); assert_eq!(map.get(&2), None);
pub fn get_mut<Q: ?Sized>(&mut self, q: &Q) -> Option<&mut V> where
K: Borrow<Q>,
Q: Hash + Ord,
[src]
pub fn get_mut<Q: ?Sized>(&mut self, q: &Q) -> Option<&mut V> where
K: Borrow<Q>,
Q: Hash + Ord,
Returns a mutable reference to the value corresponding to the key.
The key may be any borrowed form of the map's key type, but
Hash
and Ord
on the borrowed form must match those for
the key type.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert(1, "a"); if let Some(x) = map.get_mut(&1) { *x = "b"; } assert_eq!(map[&1], "b");
pub fn reserve(&mut self, additional: usize)
[src]
pub fn reserve(&mut self, additional: usize)
Reserves capacity for at least additional
more elements to be inserted
in the HashMap
. The collection may reserve more space to avoid
frequent reallocations.
Examples
use hash_ord::hash_map::HashMap; let mut map: HashMap<&str, isize> = HashMap::new(); map.reserve(10);
pub fn try_reserve(&mut self, additional: usize)
[src]
pub fn try_reserve(&mut self, additional: usize)
pub fn contains_key<Q: ?Sized>(&self, q: &Q) -> bool where
K: Borrow<Q>,
Q: Hash + Ord,
[src]
pub fn contains_key<Q: ?Sized>(&self, q: &Q) -> bool where
K: Borrow<Q>,
Q: Hash + Ord,
Returns true if the map contains a value for the specified key.
The key may be any borrowed form of the map's key type, but
Hash
and Ord
on the borrowed form must match those for
the key type.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert(1, "a"); assert_eq!(map.contains_key(&1), true); assert_eq!(map.contains_key(&2), false);
pub fn insert(&mut self, key: K, value: V) -> Option<(K, V)>
[src]
pub fn insert(&mut self, key: K, value: V) -> Option<(K, V)>
Inserts a key-value pair into the map.
If the map did not have this key present, None
is returned.
If the map did have this key present, update map with new (key, value) and return the old one.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); assert_eq!(map.insert(37, "a"), None); assert_eq!(map.is_empty(), false); map.insert(37, "b"); assert_eq!(map.insert(37, "c"), Some((37, "b"))); assert_eq!(map[&37], "c");
pub fn remove<Q: ?Sized>(&mut self, q: &Q) -> Option<(K, V)> where
K: Borrow<Q>,
Q: Hash + Ord,
[src]
pub fn remove<Q: ?Sized>(&mut self, q: &Q) -> Option<(K, V)> where
K: Borrow<Q>,
Q: Hash + Ord,
Removes a key from the map, returning the stored key and value if the key was previously in the map.
The key may be any borrowed form of the map's key type, but
Hash
and Ord
on the borrowed form must match those for
the key type.
Examples
use hash_ord::hash_map::HashMap; let mut map = HashMap::new(); map.insert(1, "a"); assert_eq!(map.remove(&1), Some((1, "a"))); assert_eq!(map.remove(&1), None);
pub fn with_capacity_and_hasher(
capacity: usize,
hash_builder: S
) -> HashMap<K, V, S>
[src]
pub fn with_capacity_and_hasher(
capacity: usize,
hash_builder: S
) -> HashMap<K, V, S>
Creates an empty HashMap
with the specified capacity, using hash_builder
to hash the keys.
The hash map will be able to hold at least capacity
elements without
reallocating. If capacity
is 0, the hash map will not allocate.
Warning: hash_builder
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.
Examples
use hash_ord::hash_map::HashMap; use std::collections::hash_map::RandomState; let s = RandomState::new(); let mut map = HashMap::with_capacity_and_hasher(10, s); map.insert(1, 2);
pub fn shrink_to_fit(&mut self)
[src]
pub fn shrink_to_fit(&mut self)
Shrinks the capacity of the map as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.
Examples
use hash_ord::hash_map::HashMap; let mut map: HashMap<isize, isize> = HashMap::with_capacity(100); map.insert(1, 2); map.insert(3, 4); assert!(map.capacity() >= 100); map.shrink_to_fit(); assert!(map.capacity() >= 2);
impl<K, V> HashMap<K, V, RandomState> where
K: Hash + Ord,
[src]
impl<K, V> HashMap<K, V, RandomState> where
K: Hash + Ord,
pub fn new() -> HashMap<K, V, RandomState>
[src]
pub fn new() -> HashMap<K, V, RandomState>
Creates an empty HashMap
.
The hash map is initially created with a capacity of 0, so it will not allocate until it is first inserted into.
Examples
use hash_ord::hash_map::HashMap; let mut map: HashMap<&str, isize> = HashMap::new();
pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState>
[src]
pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState>
Trait Implementations
impl<K, V, S> Default for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher + Default,
[src]
impl<K, V, S> Default for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher + Default,
fn default() -> HashMap<K, V, S>
[src]
fn default() -> HashMap<K, V, S>
Creates an empty HashMap<K, V, S>
, with the Default
value for the hasher.
impl<K, V, S> Drop for HashMap<K, V, S>
[src]
impl<K, V, S> Drop for HashMap<K, V, S>
impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S> where
Q: Hash + Ord,
K: Hash + Ord + Borrow<Q>,
S: BuildHasher,
[src]
impl<'a, K, Q: ?Sized, V, S> Index<&'a Q> for HashMap<K, V, S> where
Q: Hash + Ord,
K: Hash + Ord + Borrow<Q>,
S: BuildHasher,
type Output = V
The returned type after indexing.
fn index(&self, q: &Q) -> &Self::Output
[src]
fn index(&self, q: &Q) -> &Self::Output
Returns a reference to the value corresponding to the supplied key.
Panics
Panics if the key is not present in the HashMap
.
impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
[src]
impl<K, V, S> Extend<(K, V)> for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
[src]
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
Extends a collection with the contents of an iterator. Read more
impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S> where
K: Ord + Hash + Copy,
V: Copy,
S: BuildHasher,
[src]
impl<'a, K, V, S> Extend<(&'a K, &'a V)> for HashMap<K, V, S> where
K: Ord + Hash + Copy,
V: Copy,
S: BuildHasher,
fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T)
[src]
fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T)
Extends a collection with the contents of an iterator. Read more
impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
[src]
impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
type Item = (&'a K, &'a V)
The type of the elements being iterated over.
type IntoIter = Iter<'a, K, V, S>
Which kind of iterator are we turning this into?
ⓘImportant traits for Iter<'a, K, V, S>fn into_iter(self) -> Iter<'a, K, V, S>
[src]
fn into_iter(self) -> Iter<'a, K, V, S>
Creates an iterator from a value. Read more
impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
[src]
impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
type Item = (&'a K, &'a mut V)
The type of the elements being iterated over.
type IntoIter = IterMut<'a, K, V, S>
Which kind of iterator are we turning this into?
ⓘImportant traits for IterMut<'a, K, V, S>fn into_iter(self) -> IterMut<'a, K, V, S>
[src]
fn into_iter(self) -> IterMut<'a, K, V, S>
Creates an iterator from a value. Read more
impl<K, V, S> IntoIterator for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
[src]
impl<K, V, S> IntoIterator for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher,
type Item = (K, V)
The type of the elements being iterated over.
type IntoIter = IntoIter<K, V, S>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Self::IntoIter
[src]
fn into_iter(self) -> Self::IntoIter
Creates an iterator from a value. Read more
impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher + Default,
[src]
impl<K, V, S> FromIterator<(K, V)> for HashMap<K, V, S> where
K: Ord + Hash,
S: BuildHasher + Default,
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S>
[src]
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> HashMap<K, V, S>
Creates a value from an iterator. Read more
impl<K, V, S> Clone for HashMap<K, V, S> where
K: Ord + Hash + Clone,
V: Clone,
S: BuildHasher + Clone,
[src]
impl<K, V, S> Clone for HashMap<K, V, S> where
K: Ord + Hash + Clone,
V: Clone,
S: BuildHasher + Clone,
fn clone(&self) -> Self
[src]
fn clone(&self) -> Self
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<K, V, S> PartialEq for HashMap<K, V, S> where
K: Ord + Hash,
V: PartialEq,
S: BuildHasher,
[src]
impl<K, V, S> PartialEq for HashMap<K, V, S> where
K: Ord + Hash,
V: PartialEq,
S: BuildHasher,
fn eq(&self, other: &HashMap<K, V, S>) -> bool
[src]
fn eq(&self, other: &HashMap<K, V, S>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
fn ne(&self, other: &Rhs) -> bool
This method tests for !=
.
impl<K, V, S> Eq for HashMap<K, V, S> where
K: Ord + Hash,
V: Eq,
S: BuildHasher,
[src]
impl<K, V, S> Eq for HashMap<K, V, S> where
K: Ord + Hash,
V: Eq,
S: BuildHasher,
Auto Trait Implementations
impl<K, V, S = BuildHasherDefault<FnvHasher>> !Send for HashMap<K, V, S>
impl<K, V, S = BuildHasherDefault<FnvHasher>> !Send for HashMap<K, V, S>
impl<K, V, S = BuildHasherDefault<FnvHasher>> !Sync for HashMap<K, V, S>
impl<K, V, S = BuildHasherDefault<FnvHasher>> !Sync for HashMap<K, V, S>