use borrow::Borrow;
use cmp::max;
use fmt::{self, Debug};
+#[allow(deprecated)]
use hash::{Hash, Hasher, BuildHasher, SipHasher13};
use iter::{FromIterator, FusedIterator};
use mem::{self, replace};
use super::table::{self, Bucket, EmptyBucket, FullBucket, FullBucketMut, RawTable, SafeHash};
use super::table::BucketState::{Empty, Full};
-const INITIAL_LOG2_CAP: usize = 5;
-const INITIAL_CAPACITY: usize = 1 << INITIAL_LOG2_CAP; // 2^5
+const MIN_NONZERO_RAW_CAPACITY: usize = 32; // must be a power of two
-/// The default behavior of HashMap implements a load factor of 90.9%.
-/// This behavior is characterized by the following condition:
-///
-/// - if size > 0.909 * capacity: grow the map
+/// The default behavior of HashMap implements a maximum load factor of 90.9%.
#[derive(Clone)]
struct DefaultResizePolicy;
DefaultResizePolicy
}
+ /// A hash map's "capacity" is the number of elements it can hold without
+ /// being resized. Its "raw capacity" is the number of slots required to
+ /// provide that capacity, accounting for maximum loading. The raw capacity
+ /// is always zero or a power of two.
#[inline]
- fn min_capacity(&self, usable_size: usize) -> usize {
- // Here, we are rephrasing the logic by specifying the lower limit
- // on capacity:
- //
- // - if `cap < size * 1.1`: grow the map
- usable_size * 11 / 10
+ fn raw_capacity(&self, len: usize) -> usize {
+ if len == 0 {
+ 0
+ } else {
+ // 1. Account for loading: `raw_capacity >= len * 1.1`.
+ // 2. Ensure it is a power of two.
+ // 3. Ensure it is at least the minimum size.
+ let mut raw_cap = len * 11 / 10;
+ assert!(raw_cap >= len, "raw_cap overflow");
+ raw_cap = raw_cap.checked_next_power_of_two().expect("raw_capacity overflow");
+ raw_cap = max(MIN_NONZERO_RAW_CAPACITY, raw_cap);
+ raw_cap
+ }
}
- /// An inverse of `min_capacity`, approximately.
+ /// The capacity of the given raw capacity.
#[inline]
- fn usable_capacity(&self, cap: usize) -> usize {
- // As the number of entries approaches usable capacity,
- // min_capacity(size) must be smaller than the internal capacity,
- // so that the map is not resized:
- // `min_capacity(usable_capacity(x)) <= x`.
- // The left-hand side can only be smaller due to flooring by integer
- // division.
- //
+ fn capacity(&self, raw_cap: usize) -> usize {
// This doesn't have to be checked for overflow since allocation size
// in bytes will overflow earlier than multiplication by 10.
//
// As per https://github.com/rust-lang/rust/pull/30991 this is updated
- // to be: (cap * den + den - 1) / num
- (cap * 10 + 10 - 1) / 11
- }
-}
-
-#[test]
-fn test_resize_policy() {
- let rp = DefaultResizePolicy;
- for n in 0..1000 {
- assert!(rp.min_capacity(rp.usable_capacity(n)) <= n);
- assert!(rp.usable_capacity(rp.min_capacity(n)) <= n);
+ // to be: (raw_cap * den + den - 1) / num
+ (raw_cap * 10 + 10 - 1) / 11
}
}
//
// FIXME(Gankro, pczarn): review the proof and put it all in a separate README.md
-/// A hash map implementation which uses linear probing with Robin
-/// Hood bucket stealing.
+/// A hash map implementation which uses linear probing with Robin Hood bucket
+/// stealing.
///
-/// By default, HashMap uses a somewhat slow hashing algorithm which can provide resistance
-/// to DoS attacks. Rust makes a best attempt at acquiring random numbers without IO
-/// blocking from your system. Because of this HashMap is not guaranteed to provide
-/// DoS resistance since the numbers generated might not be truly random. If you do
-/// require this behavior you can create your own hashing function using
-/// [BuildHasherDefault](../hash/struct.BuildHasherDefault.html).
+/// By default, `HashMap` uses a hashing algorithm selected to provide
+/// resistance against HashDoS attacks. The algorithm is randomly seeded, and a
+/// reasonable best-effort is made to generate this seed from a high quality,
+/// secure source of randomness provided by the host without blocking the
+/// program. Because of this, the randomness of the seed is dependant on the
+/// quality of the system's random number generator at the time it is created.
+/// In particular, seeds generated when the system's entropy pool is abnormally
+/// low such as during system boot may be of a lower quality.
+///
+/// The default hashing algorithm is currently SipHash 1-3, though this is
+/// subject to change at any point in the future. While its performance is very
+/// competitive for medium sized keys, other hashing algorithms will outperform
+/// it for small keys such as integers as well as large keys such as long
+/// strings, though those algorithms will typically *not* protect against
+/// attacks such as HashDoS.
+///
+/// The hashing algorithm can be replaced on a per-`HashMap` basis using the
+/// `HashMap::default`, `HashMap::with_hasher`, and
+/// `HashMap::with_capacity_and_hasher` methods. Many alternative algorithms
+/// are available on crates.io, such as the `fnv` crate.
///
/// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
/// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
/// println!("{:?} has {} hp", viking, health);
/// }
/// ```
+///
+/// A HashMap with fixed list of elements can be initialized from an array:
+///
+/// ```
+/// use std::collections::HashMap;
+///
+/// fn main() {
+/// let timber_resources: HashMap<&str, i32> =
+/// [("Norway", 100),
+/// ("Denmark", 50),
+/// ("Iceland", 10)]
+/// .iter().cloned().collect();
+/// // use the values stored in map
+/// }
+/// ```
+
#[derive(Clone)]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct HashMap<K, V, S = RandomState> {
// The caller should ensure that invariants by Robin Hood Hashing hold.
fn insert_hashed_ordered(&mut self, hash: SafeHash, k: K, v: V) {
- let cap = self.table.capacity();
+ let raw_cap = self.raw_capacity();
let mut buckets = Bucket::new(&mut self.table, hash);
let ib = buckets.index();
- while buckets.index() != ib + cap {
+ while buckets.index() != ib + raw_cap {
// We don't need to compare hashes for value swap.
// Not even DIBs for Robin Hood.
buckets = match buckets.peek() {
Default::default()
}
- /// Creates an empty `HashMap` with the given initial capacity.
+ /// Creates an empty `HashMap` with the specified capacity.
+ ///
+ /// The hash map will be able to hold at least `capacity` elements without
+ /// reallocating. If `capacity` is 0, the hash map will not allocate.
///
/// # Examples
///
}
}
- /// Creates an empty `HashMap` with space for at least `capacity`
- /// elements, using `hasher` to hash the keys.
+ /// Creates an empty `HashMap` with the specified capacity, using `hasher`
+ /// 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: `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
#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> HashMap<K, V, S> {
let resize_policy = DefaultResizePolicy::new();
- let min_cap = max(INITIAL_CAPACITY, resize_policy.min_capacity(capacity));
- let internal_cap = min_cap.checked_next_power_of_two().expect("capacity overflow");
- assert!(internal_cap >= capacity, "capacity overflow");
+ let raw_cap = resize_policy.raw_capacity(capacity);
HashMap {
hash_builder: hash_builder,
resize_policy: resize_policy,
- table: RawTable::new(internal_cap),
+ table: RawTable::new(raw_cap),
}
}
#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub fn capacity(&self) -> usize {
- self.resize_policy.usable_capacity(self.table.capacity())
+ self.resize_policy.capacity(self.raw_capacity())
+ }
+
+ /// Returns the hash map's raw capacity.
+ #[inline]
+ fn raw_capacity(&self) -> usize {
+ self.table.capacity()
}
/// Reserves capacity for at least `additional` more elements to be inserted
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn reserve(&mut self, additional: usize) {
- let new_size = self.len().checked_add(additional).expect("capacity overflow");
- let min_cap = self.resize_policy.min_capacity(new_size);
-
- // An invalid value shouldn't make us run out of space. This includes
- // an overflow check.
- assert!(new_size <= min_cap);
-
- if self.table.capacity() < min_cap {
- let new_capacity = max(min_cap.next_power_of_two(), INITIAL_CAPACITY);
- self.resize(new_capacity);
+ let remaining = self.capacity() - self.len(); // this can't overflow
+ if remaining < additional {
+ let min_cap = self.len().checked_add(additional).expect("reserve overflow");
+ let raw_cap = self.resize_policy.raw_capacity(min_cap);
+ self.resize(raw_cap);
}
}
- /// Resizes the internal vectors to a new capacity. It's your responsibility to:
- /// 1) Make sure the new capacity is enough for all the elements, accounting
+ /// Resizes the internal vectors to a new capacity. It's your
+ /// responsibility to:
+ /// 1) Ensure `new_raw_cap` is enough for all the elements, accounting
/// for the load factor.
- /// 2) Ensure `new_capacity` is a power of two or zero.
- fn resize(&mut self, new_capacity: usize) {
- assert!(self.table.size() <= new_capacity);
- assert!(new_capacity.is_power_of_two() || new_capacity == 0);
+ /// 2) Ensure `new_raw_cap` is a power of two or zero.
+ fn resize(&mut self, new_raw_cap: usize) {
+ assert!(self.table.size() <= new_raw_cap);
+ assert!(new_raw_cap.is_power_of_two() || new_raw_cap == 0);
- let mut old_table = replace(&mut self.table, RawTable::new(new_capacity));
+ let mut old_table = replace(&mut self.table, RawTable::new(new_raw_cap));
let old_size = old_table.size();
if old_table.capacity() == 0 || old_table.size() == 0 {
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
pub fn shrink_to_fit(&mut self) {
- let min_capacity = self.resize_policy.min_capacity(self.len());
- let min_capacity = max(min_capacity.next_power_of_two(), INITIAL_CAPACITY);
-
- // An invalid value shouldn't make us run out of space.
- debug_assert!(self.len() <= min_capacity);
-
- if self.table.capacity() != min_capacity {
- let old_table = replace(&mut self.table, RawTable::new(min_capacity));
+ let new_raw_cap = self.resize_policy.raw_capacity(self.len());
+ if self.raw_capacity() != new_raw_cap {
+ let old_table = replace(&mut self.table, RawTable::new(new_raw_cap));
let old_size = old_table.size();
// Shrink the table. Naive algorithm for resizing:
#[unstable(feature = "fused", issue = "35602")]
impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
-#[stable(feature = "rust1", since = "1.0.0")]
+#[stable(feature = "drain", since = "1.6.0")]
impl<'a, K, V> Iterator for Drain<'a, K, V> {
type Item = (K, V);
self.inner.size_hint()
}
}
-#[stable(feature = "rust1", since = "1.0.0")]
+#[stable(feature = "drain", since = "1.6.0")]
impl<'a, K, V> ExactSizeIterator for Drain<'a, K, V> {
#[inline]
fn len(&self) -> usize {
impl BuildHasher for RandomState {
type Hasher = DefaultHasher;
#[inline]
+ #[allow(deprecated)]
fn build_hasher(&self) -> DefaultHasher {
DefaultHasher(SipHasher13::new_with_keys(self.k0, self.k1))
}
///
/// [`RandomState`]: struct.RandomState.html
/// [`Hasher`]: ../../hash/trait.Hasher.html
-#[unstable(feature = "hashmap_default_hasher", issue = "0")]
+#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
+#[allow(deprecated)]
+#[derive(Debug)]
pub struct DefaultHasher(SipHasher13);
-#[unstable(feature = "hashmap_default_hasher", issue = "0")]
+impl DefaultHasher {
+ /// Creates a new `DefaultHasher`.
+ ///
+ /// This hasher is not guaranteed to be the same as all other
+ /// `DefaultHasher` instances, but is the same as all other `DefaultHasher`
+ /// instances created through `new` or `default`.
+ #[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
+ #[allow(deprecated)]
+ pub fn new() -> DefaultHasher {
+ DefaultHasher(SipHasher13::new_with_keys(0, 0))
+ }
+}
+
+#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
+impl Default for DefaultHasher {
+ fn default() -> DefaultHasher {
+ DefaultHasher::new()
+ }
+}
+
+#[stable(feature = "hashmap_default_hasher", since = "1.13.0")]
impl Hasher for DefaultHasher {
#[inline]
fn write(&mut self, msg: &[u8]) {
}
}
-#[stable(feature = "rust1", since = "1.0.0")]
+#[stable(feature = "hashmap_build_hasher", since = "1.7.0")]
impl Default for RandomState {
/// Constructs a new `RandomState`.
#[inline]
use rand::{thread_rng, Rng};
#[test]
- fn test_create_capacities() {
+ fn test_zero_capacities() {
type HM = HashMap<i32, i32>;
let m = HM::new();
let m = HM::with_hasher(RandomState::new());
assert_eq!(m.capacity(), 0);
+
+ let m = HM::with_capacity(0);
+ assert_eq!(m.capacity(), 0);
+
+ let m = HM::with_capacity_and_hasher(0, RandomState::new());
+ assert_eq!(m.capacity(), 0);
+
+ let mut m = HM::new();
+ m.insert(1, 1);
+ m.insert(2, 2);
+ m.remove(&1);
+ m.remove(&2);
+ m.shrink_to_fit();
+ assert_eq!(m.capacity(), 0);
+
+ let mut m = HM::new();
+ m.reserve(0);
+ assert_eq!(m.capacity(), 0);
}
#[test]
assert!(m.is_empty());
let mut i = 0;
- let old_cap = m.table.capacity();
- while old_cap == m.table.capacity() {
+ let old_raw_cap = m.raw_capacity();
+ while old_raw_cap == m.raw_capacity() {
m.insert(i, i);
i += 1;
}
let mut m = HashMap::new();
assert_eq!(m.len(), 0);
- assert_eq!(m.table.capacity(), 0);
+ assert_eq!(m.raw_capacity(), 0);
assert!(m.is_empty());
m.insert(0, 0);
m.remove(&0);
assert!(m.is_empty());
- let initial_cap = m.table.capacity();
- m.reserve(initial_cap);
- let cap = m.table.capacity();
+ let initial_raw_cap = m.raw_capacity();
+ m.reserve(initial_raw_cap);
+ let raw_cap = m.raw_capacity();
- assert_eq!(cap, initial_cap * 2);
+ assert_eq!(raw_cap, initial_raw_cap * 2);
let mut i = 0;
- for _ in 0..cap * 3 / 4 {
+ for _ in 0..raw_cap * 3 / 4 {
m.insert(i, i);
i += 1;
}
// three quarters full
assert_eq!(m.len(), i);
- assert_eq!(m.table.capacity(), cap);
+ assert_eq!(m.raw_capacity(), raw_cap);
- for _ in 0..cap / 4 {
+ for _ in 0..raw_cap / 4 {
m.insert(i, i);
i += 1;
}
// half full
- let new_cap = m.table.capacity();
- assert_eq!(new_cap, cap * 2);
+ let new_raw_cap = m.raw_capacity();
+ assert_eq!(new_raw_cap, raw_cap * 2);
- for _ in 0..cap / 2 - 1 {
+ for _ in 0..raw_cap / 2 - 1 {
i -= 1;
m.remove(&i);
- assert_eq!(m.table.capacity(), new_cap);
+ assert_eq!(m.raw_capacity(), new_raw_cap);
}
// A little more than one quarter full.
m.shrink_to_fit();
- assert_eq!(m.table.capacity(), cap);
+ assert_eq!(m.raw_capacity(), raw_cap);
// again, a little more than half full
- for _ in 0..cap / 2 - 1 {
+ for _ in 0..raw_cap / 2 - 1 {
i -= 1;
m.remove(&i);
}
assert_eq!(m.len(), i);
assert!(!m.is_empty());
- assert_eq!(m.table.capacity(), initial_cap);
+ assert_eq!(m.raw_capacity(), initial_raw_cap);
}
#[test]
projects / rust.git / blobdiff