weak-table

This release improves performance and correctness by replacing the backend with [hashbrown]. It also adds numerous APIs, and extensive tests.

There are breaking changes in this release, but they should not affect most users. Notably, the alloc feature has been removed, the ahash feature has been deprecated, and the minimum supported rust version for this crate has been increased to 1.65. See below for more details.

Added

• High-coverage unit tests for the hash table backend.

• High-coverage unit tests for all maps and sets.

• Property tests for all of the exposed map and set types.

• Benchmarks based on criterion.

• Added APIs to map types to match with stdlib HashMap:

  • extract_if
  • get_disjoint_mut, get_both_disjoint_mut
  • into_keys
  • into_values
  • remove_entry
  • shrink_to
  • try_reserve
  • From<[(K, V); N]>
  • Entry::and_modify
  • Entry::insert_entry
  • Entry::or_insert_with_key
  • VacantEntry::insert_entry.

• Added APIs to set types to match with stdlib HashSet:

  • difference
  • extract_if
  • intersection
  • is_disjoint
  • is_superset
  • shrink_to
  • symmetric_difference
  • take
  • try_reserve
  • union
  • BitAnd
  • BitOr
  • BitXor
  • From<[T;N]>
  • Sub

• It is now possible to build as no_std without ahash support. If you do, there will be no default BuildHasher, and the new() and with_capacity() methods will be absent.

Removed

• The non-functional alloc feature has been removed.

Deprecated

• The ahash feature is now deprecated for security reasons. Instead, use the constructors that allow you to specify a BuildHasher manually.

Changed (visible)

• All hash-tables now use a new backend based on [hashbrown] for improved speed and correctness. (Benchmarks report a speedup around 30-50%.)
• The Minimum Supported Rust Version is now 1.65. (This is necessary to use hashbrown version 0.16.)
• The default capacity for new tables is now zero.
• Changed load_factor() to return a value closer to the table's actual load factor.
• Methods that do not require the element type to be WeakKey or WeakElement no longer constrain their parameters in this way.
• Constructors are now #[must_use].
• ExtractIf iterators are now #[must_use].

Changed (internal)

• Numerous Clippy warnings are now enabled.
• The Rust Edition is now 2021.
• We no longer rely on floating-point except in methods that return a floating-point result.
• The Debug output is slightly different.
• The source is now formatted according to the Rust style guide, using cargo fmt.
• Allocation sizes are now slightly different.
• The output of Debug is now slightly different.
• Because of hashbrown internals, capacity calculations can behave differently.
• Tests have been moved to a tests submodule, so that they can share code.
• A great deal of common code has been extracted into macros, to avoid the risk of copy-and-paste errors.
• When ahash is enabled, we now use ahash version 0.8.12 or later.
• The rand dev-dependency has been removed.

Fixed

• The retain() and remove_expired() methods no longer skip elements that changed position due to other elements having been removed. ([github#22])
• Fix a bug in load_factor() calculation where it would return inf for a zero-capacity table.
• Changed the output of Debug for WeakHashSet and PtrWeakHashSet to display them as sets, not as maps to ().
• Eliminated some possible integer overflows when trying to reserve very high capacities.

Documentation

• Cleaned up documentation that referred to sets as maps, or claimed that they had separate keys and values.

Release version 0.4.0-pre3

Documentation

• listed asymptotic time complexities for each operation

Added

• no_std compatibility (h/t @tsao-chi)

(cargo-release) version 0.3.0

(cargo-release) version 0.2.4

Fixed

• Bad bucket selection on collision (h/t Andrew Browne <[email protected]>).

(cargo-release) version 0.2.3

Fixed

• Use Rc::ptr_eq to compare Rcs by address.

(cargo-release) version 0.2.2

Fixed

• Weak–weak submap operations were missing a line of code.

Added

• {PtrWeakHashSet,PtrWeakKeyHashMap}::is_empty() methods.

Fixed

• a test that was breaking on an older rustc

Documention

• improved

Renamed

• from WeakElement::expired to WeakElement::is_expired

Documention

• improved

Testing

• added a test

Documention

• minimum supported rustc

Added

• WeakKeyHashMap::{get_key, get_both, get_both_mut} methods
• WeakWeakHashMap::{get_key, get_both} methods
• WeakHashSet::get method

Changed

• Values stored behind Rcs can now be ?Sized.

Removed

• struct RcKey<K>

Documentation

• improved

Initial release.