Struct std::collections::hash_map::raw_table::RawTable
[−]
[src]
pub struct RawTable<K, V> {
capacity: usize,
size: usize,
hashes: Unique<u64>,
marker: PhantomData<(K, V)>,
}The raw hashtable, providing safe-ish access to the unzipped and highly optimized arrays of hashes, keys, and values.
This design uses less memory and is a lot faster than the naive
Vec<Option<u64, K, V>>, because we don't pay for the overhead of an
option on every element, and we get a generally more cache-aware design.
Essential invariants of this structure:
if t.hashes[i] == EMPTY_BUCKET, then
Bucket::at_index(&t, i).rawpoints to 'undefined' contents. Don't read from it. This invariant is enforced outside this module with theEmptyBucket,FullBucket, andSafeHashtypes.An
EmptyBucketis only constructed at an index with a hash of EMPTY_BUCKET.A
FullBucketis only constructed at an index with a non-EMPTY_BUCKET hash.A
SafeHashis only constructed for non-EMPTY_BUCKEThash. We get around hashes of zero by changing them to 0x8000_0000_0000_0000, which will likely map to the same bucket, while not being confused with "empty".All three "arrays represented by pointers" are the same length:
capacity. This is set at creation and never changes. The arrays are unzipped to save space (we don't have to pay for the padding between odd sized elements, such as in a map from u64 to u8), and be more cache aware (scanning through 8 hashes brings in at most 2 cache lines, since they're all right beside each other).
You can kind of think of this module/data structure as a safe wrapper
around just the "table" part of the hashtable. It enforces some
invariants at the type level and employs some performance trickery,
but in general is just a tricked out Vec<Option<u64, K, V>>.
Fields
capacity | |
size | |
hashes | |
marker |
Methods
impl<K, V> RawTable<K, V>
unsafe fn new_uninitialized(capacity: usize) -> RawTable<K, V>
Does not initialize the buckets. The caller should ensure they, at the very least, set every hash to EMPTY_BUCKET.
fn first_bucket_raw(&self) -> RawBucket<K, V>
fn new(capacity: usize) -> RawTable<K, V>
Creates a new raw table from a given capacity. All buckets are initially empty.
fn capacity(&self) -> usize
The hashtable's capacity, similar to a vector's.
fn size(&self) -> usize
The number of elements ever put in the hashtable, minus the number
of elements ever taken.
fn raw_buckets(&self) -> RawBuckets<K, V>
fn iter(&self) -> Iter<K, V>
fn iter_mut(&mut self) -> IterMut<K, V>
fn into_iter(self) -> IntoIter<K, V>
fn drain(&mut self) -> Drain<K, V>
unsafe fn rev_move_buckets(&mut self) -> RevMoveBuckets<K, V>
Returns an iterator that copies out each entry. Used while the table is being dropped.