fixed_size_hash_map.rs

Overview

This file implements a generic, fixed-capacity hash map data structure named FixedSizeHashMap. The primary purpose of this structure is to maintain a collection of key-value pairs with a strict size limit (capacity). When the map reaches its capacity and a new element is inserted, the map evicts the oldest entry in insertion order to make space for the new one. This eviction strategy ensures a bounded memory footprint and predictable resource usage, suitable for caching or limited storage scenarios.

The map uses an internal HashMap for fast key-based lookups and a Vec to track the insertion order for eviction purposes. The eviction is a simple cyclic buffer approach, which allows efficient replacement of entries without the overhead of complex data structures.

Struct: FixedSizeHashMap<K, V>

Description

A fixed-capacity hash map supporting insertions, lookups, and a simple eviction policy that removes the oldest entry when capacity is exceeded.

Generic Parameters

• K: Key type. Must implement Clone, Hash, and Eq.

• V: Value type.

Fields

• capacity: usize
  The maximum number of entries the map can hold.

• blocks: HashMap<K, V>
  The underlying storage for key-value pairs.

• eviction_order: Vec<K>
  Tracks the keys in insertion order to determine which entry to evict next.

• eviction_order_cursor: usize
  Points to the current position in eviction_order for the next eviction replacement.

Implementation Details

• The map never grows beyond the specified capacity.

• On insertion:

  • If the key already exists, insertion is ignored.

  • If there is still capacity, the key-value pair is added and the key is appended to eviction_order.

  • If capacity is full, the entry at eviction_order_cursor is evicted (removed from the map), replaced with the new key, and the new pair is inserted. The cursor then advances cyclically.

• Lookup is performed directly on the internal HashMap.

• The eviction strategy is a simple ring buffer over the eviction_order vector, which is efficient in time and space.

Methods

new(capacity: usize) -> Self

Constructs a new FixedSizeHashMap with the specified maximum capacity.

• Parameters:

  • capacity: Maximum number of elements the map can hold.

• Returns:
  A new instance of FixedSizeHashMap with empty storage and initialized eviction data.

• Example:

  let map: FixedSizeHashMap<i32, String> = FixedSizeHashMap::new(100);
  

contains_key(&self, id: &K) -> bool

Checks if the map contains a given key.

• Parameters:

  • id: Reference to the key to check.

• Returns:
  true if the key exists in the map, false otherwise.

• Example:

  if map.contains_key(&42) {
      println!("Key 42 exists");
  }
  

insert(&mut self, id: K, value: V)

Inserts a new key-value pair into the map. If the capacity is exceeded, evicts the oldest entry.

• Parameters:

  • id: The key to insert.

  • value: The value associated with the key.

• Behavior:

  • Ignores insertion if the key already exists.

  • Adds a new entry if capacity is not yet full.

  • Evicts and replaces the oldest entry if capacity is full.

• Example:

  map.insert(10, "value".to_string());
  

get<Q>(&self, k: &Q) -> Option<&V>

Generic key lookup supporting borrowed forms of K.

• Parameters:

  • k: Reference to a key or key-like type that can be borrowed from K.

• Returns:
  An Option containing a reference to the value if found, or None if not.

• Example:

  if let Some(val) = map.get(&10) {
      println!("Found value: {}", val);
  }
  

blocks(&self) -> &HashMap<K, V>

Returns a reference to the internal HashMap storing the key-value pairs.

• Returns:
  Reference to the internal blocks map.

• Example:

  let internal_map = map.blocks();
  

Trait Implementations

Debug

• Displays a brief summary showing the current number of stored entries and the capacity.

• Format: FixedSizeHashMap(current_size/capacity)

• Example:

  println!("{:?}", map);
  // Output: FixedSizeHashMap(5/100)
  

Important Implementation Notes

• The eviction strategy is a simple ring buffer implemented via eviction_order and eviction_order_cursor. This design avoids complex data structures and allows constant time eviction and insertion operations.

• The comment at the top suggests a future improvement for storage cleanup based on descendants of finalized blocks, but the current implementation prioritizes simplicity and speed under the assumption of a sufficient capacity.

• The insert method does not update the position of existing keys; it ignores duplicate inserts to maintain eviction order correctness.

Interaction with Other System Components

• This map is suitable for scenarios where controlled memory usage is critical, such as caching or block storage in blockchain or distributed ledger contexts.

• It is designed to be a drop-in bounded map replacement when a standard HashMap with unbounded size is not suitable.

• The note about "finalized blocks" suggests usage in a blockchain or DAG-based system for storing blocks or state snapshots, interacting with block finalization and cleanup logic elsewhere in the application.

Mermaid Diagram

classDiagram
class FixedSizeHashMap {
-capacity: usize
-blocks: HashMap<K, V>
-eviction_order: Vec<K>
-eviction_order_cursor: usize
+new(capacity)
+contains_key(id)
+insert(id, value)
+get(k)
+blocks()
+fmt()
}