HashQueue

public class HashQueue<K> where K : Hashable

A high-performance hash-based queue that maintains insertion order with O(1) access and removal operations.

Core Features

  • Hash-Based Operations: All operations are performed using hashable keys, providing intuitive access patterns
  • LRU (Least Recently Used) Management: Recently accessed keys are moved to the front of the queue
  • O(1) Performance: Constant time complexity for enqueue, dequeue, and removal operations
  • Capacity Management: Configurable capacity with automatic eviction of least recently used keys
  • Duplicate Key Handling: Re-inserting an existing key moves it to the front (LRU behavior)

Data Structure

The queue uses a combination of:

  • Doubly Linked List: Maintains insertion order and provides O(1) front/back operations
  • Hash Map: Provides O(1) key-to-node lookup for efficient access and removal

Performance Characteristics

  • Time Complexity: O(1) average case for all operations
  • Space Complexity: O(n) where n is the number of keys
  • Memory Efficiency: Automatic eviction when capacity is exceeded
  • Thread Safety: Not thread-safe; caller must ensure thread safety if needed

Example Usage

// Create a hash queue with capacity of 100
let queue = HashQueue<String>(capacity: 100)

// Enqueue keys (moves to front if already exists)
queue.enqueueFront(key: "task1")
queue.enqueueFront(key: "task2")
queue.enqueueFront(key: "task1") // Moves "task1" to front

// Dequeue from front (most recently used)
let mostRecent = queue.dequeueFront() // Returns "task1"

// Dequeue from back (least recently used)
let leastRecent = queue.dequeueBack() // Returns "task2"

// Remove specific key
queue.remove(key: "task3")

  • Initializes a new empty hash queue with specified capacity.

    Declaration

    Swift

    public init(capacity: Int)

    Parameters

    capacity

    Maximum number of keys allowed in the queue. Negative values are treated as zero.

  • Enqueues a key at the front (most recently used position).

    • Behavior:

      • If key already exists, it is moved to the front (LRU behavior)
      • When at capacity, applies evictedStrategy from the underlying DoublyLink:
      • .FIFO: evicts the least-recent key from the back and returns it
      • .LIFO: rejects insertion and returns the provided key (no state change)
      • If capacity == 0, returns key immediately and performs no mutation

    Declaration

    Swift

    @discardableResult
public func enqueueFront(key: K, evictedStrategy: DoublyLink<K>.EvictedStrategy) -> K?

    Parameters

    key

    The key to enqueue
    evictedStrategy

    Eviction policy when full (default: .FIFO)

    Return Value

    Evicted key (if any), or the input key when insertion is rejected; otherwise nil

  • Removes and returns the key at the front of the queue (most recently used).

    Declaration

    Swift

    public func dequeueFront() -> K?

    Return Value

    The most recently used key, or nil if the queue is empty.

  • Removes and returns multiple keys from the front of the queue (most recently used).

    Declaration

    Swift

    public func dequeueFront(count: UInt) -> [K]

    Parameters

    count

    The number of keys to dequeue. If count exceeds available keys, returns all available keys.

    Return Value

    Array of the most recently used keys, in order from most to least recent. Returns empty array if queue is empty or count is 0.

  • Removes and returns the key at the back of the queue (least recently used).

    Declaration

    Swift

    public func dequeueBack() -> K?

    Return Value

    The least recently used key, or nil if the queue is empty.

  • Removes and returns multiple keys from the back of the queue (least recently used).

    Declaration

    Swift

    public func dequeueBack(count: UInt) -> [K]

    Parameters

    count

    The number of keys to dequeue. If count exceeds available keys, returns all available keys.

    Return Value

    Array of the least recently used keys, in order from least to most recent. Returns empty array if queue is empty or count is 0.

  • Removes a specific key from the queue. If the key doesn’t exist, this operation has no effect.

    Declaration

    Swift

    public func remove(key: K)

    Parameters

    key

    The key to remove from the queue.

  • The maximum number of keys the queue can hold.

    Declaration

    Swift

    var capacity: Int { get }

  • The current number of keys in the queue.

    Declaration

    Swift

    var count: Int { get }

  • Indicates if the queue is at maximum capacity.

    Declaration

    Swift

    var isFull: Bool { get }

  • Indicates if the queue is empty.

    Declaration

    Swift

    var isEmpty: Bool { get }

  • Returns whether the queue currently contains key.

    Declaration

    Swift

    func contains(key: K) -> Bool

    Parameters

    key

    The key to test for membership

    Return Value

    True if present, false otherwise