Maps & Dictionaries

Introduction

Maps and dictionaries are fundamental data structures that store key-value pairs, allowing for efficient retrieval, insertion, and deletion of data based on unique keys. They form the backbone of many algorithms and applications, from database indexing to caching systems and symbol tables in compilers.

In Swift, the built-in Dictionary type provides a robust implementation of this concept, but understanding the underlying mechanisms and alternative implementations is crucial for writing efficient code and making informed architectural decisions.

Core Concepts

What is a Map?

A map (also known as an associative array or dictionary) is an abstract data type that maintains a collection of key-value pairs, where:

Each key is unique within the collection
Keys are mapped to their associated values
Operations include insertion, deletion, and lookup by key

Key Properties

Uniqueness: Each key appears at most once in the map
Association: Each key is associated with exactly one value
Mutability: Values can be updated, and key-value pairs can be added or removed
Efficiency: Well-designed maps provide fast lookup, insertion, and deletion

Implementation Strategies

1. Hash Tables (Hash Maps)

Hash tables use a hash function to map keys to array indices, providing average O(1) operations.

struct HashTable<Key: Hashable, Value> {
	private struct Entry {
		let key: Key
		var value: Value
		var isDeleted: Bool = false
		
		init(key: Key, value: Value) {
			self.key = key
			self.value = value
		}
	}
	
	private var buckets: [Entry?]
	private var count: Int = 0
	private let loadFactorThreshold: Double = 0.75
	
	init(capacity: Int = 16) {
		self.buckets = Array(repeating: nil, count: capacity)
	}
	
	var isEmpty: Bool {
		return count == 0
	}
	
	var size: Int {
		return count
	}
	
	// MARK: - Hash Function
	
	private func hash(_ key: Key) -> Int {
		return abs(key.hashValue) % buckets.count
	}
	
	// MARK: - Core Operations
	
	mutating func setValue(_ value: Value, forKey key: Key) {
		if shouldResize() {
			resize()
		}
		
		let index = findSlot(for: key)
		
		if let existingEntry = buckets[index], !existingEntry.isDeleted {
			// Update existing entry
			buckets[index]?.value = value
		} else {
			// Insert new entry
			buckets[index] = Entry(key: key, value: value)
			count += 1
		}
	}
	
	func getValue(forKey key: Key) -> Value? {
		let index = findSlot(for: key)
		
		if let entry = buckets[index], !entry.isDeleted, entry.key == key {
			return entry.value
		}
		
		return nil
	}
	
	mutating func removeValue(forKey key: Key) -> Value? {
		let index = findSlot(for: key)
		
		if let entry = buckets[index], !entry.isDeleted, entry.key == key {
			buckets[index]?.isDeleted = true
			count -= 1
			return entry.value
		}
		
		return nil
	}
	
	// MARK: - Helper Methods
	
	private func findSlot(for key: Key) -> Int {
		var index = hash(key)
		
		// Linear probing for collision resolution
		while let entry = buckets[index] {
			if entry.key == key {
				return index
			}
			index = (index + 1) % buckets.count
		}
		
		return index
	}
	
	private func shouldResize() -> Bool {
		return Double(count) / Double(buckets.count) >= loadFactorThreshold
	}
	
	private mutating func resize() {
		let oldBuckets = buckets
		buckets = Array(repeating: nil, count: buckets.count * 2)
		count = 0
		
		// Rehash all entries
		for entry in oldBuckets {
			if let entry = entry, !entry.isDeleted {
				setValue(entry.value, forKey: entry.key)
			}
		}
	}
}

// MARK: - Subscript Support

extension HashTable {
	subscript(key: Key) -> Value? {
		get {
			return getValue(forKey: key)
		}
		set {
			if let value = newValue {
				setValue(value, forKey: key)
			} else {
				removeValue(forKey: key)
			}
		}
	}
}

2. Separate Chaining Hash Table

An alternative approach using linked lists to handle collisions:

struct ChainedHashTable<Key: Hashable, Value> {
	private class Node {
		let key: Key
		var value: Value
		var next: Node?
		
		init(key: Key, value: Value, next: Node? = nil) {
			self.key = key
			self.value = value
			self.next = next
		}
	}
	
	private var buckets: [Node?]
	private var count: Int = 0
	
	init(capacity: Int = 16) {
		self.buckets = Array(repeating: nil, count: capacity)
	}
	
	var isEmpty: Bool {
		return count == 0
	}
	
	var size: Int {
		return count
	}
	
	private func hash(_ key: Key) -> Int {
		return abs(key.hashValue) % buckets.count
	}
	
	mutating func setValue(_ value: Value, forKey key: Key) {
		let index = hash(key)
		
		if buckets[index] == nil {
			buckets[index] = Node(key: key, value: value)
			count += 1
			return
		}
		
		var current = buckets[index]
		while let node = current {
			if node.key == key {
				node.value = value
				return
			}
			if node.next == nil {
				node.next = Node(key: key, value: value)
				count += 1
				return
			}
			current = node.next
		}
	}
	
	func getValue(forKey key: Key) -> Value? {
		let index = hash(key)
		var current = buckets[index]
		
		while let node = current {
			if node.key == key {
				return node.value
			}
			current = node.next
		}
		
		return nil
	}
	
	mutating func removeValue(forKey key: Key) -> Value? {
		let index = hash(key)
		
		guard let head = buckets[index] else { return nil }
		
		if head.key == key {
			buckets[index] = head.next
			count -= 1
			return head.value
		}
		
		var current = head
		while let next = current.next {
			if next.key == key {
				current.next = next.next
				count -= 1
				return next.value
			}
			current = next
		}
		
		return nil
	}
}

3. Binary Search Tree Map

A map implementation using a binary search tree for ordered key storage:

class BSTMap<Key: Comparable, Value> {
	private class Node {
		let key: Key
		var value: Value
		var left: Node?
		var right: Node?
		
		init(key: Key, value: Value) {
			self.key = key
			self.value = value
		}
	}
	
	private var root: Node?
	private var count: Int = 0
	
	var isEmpty: Bool {
		return root == nil
	}
	
	var size: Int {
		return count
	}
	
	func setValue(_ value: Value, forKey key: Key) {
		root = setValue(value, forKey: key, in: root)
	}
	
	private func setValue(_ value: Value, forKey key: Key, in node: Node?) -> Node {
		guard let node = node else {
			count += 1
			return Node(key: key, value: value)
		}
		
		if key < node.key {
			node.left = setValue(value, forKey: key, in: node.left)
		} else if key > node.key {
			node.right = setValue(value, forKey: key, in: node.right)
		} else {
			node.value = value
		}
		
		return node
	}
	
	func getValue(forKey key: Key) -> Value? {
		return getValue(forKey: key, in: root)
	}
	
	private func getValue(forKey key: Key, in node: Node?) -> Value? {
		guard let node = node else { return nil }
		
		if key < node.key {
			return getValue(forKey: key, in: node.left)
		} else if key > node.key {
			return getValue(forKey: key, in: node.right)
		} else {
			return node.value
		}
	}
	
	func removeValue(forKey key: Key) -> Value? {
		var removedValue: Value?
		root = removeValue(forKey: key, in: root, removedValue: &removedValue)
		return removedValue
	}
	
	private func removeValue(forKey key: Key, in node: Node?, removedValue: inout Value?) -> Node? {
		guard let node = node else { return nil }
		
		if key < node.key {
			node.left = removeValue(forKey: key, in: node.left, removedValue: &removedValue)
		} else if key > node.key {
			node.right = removeValue(forKey: key, in: node.right, removedValue: &removedValue)
		} else {
			removedValue = node.value
			count -= 1
			
			if node.left == nil {
				return node.right
			} else if node.right == nil {
				return node.left
			} else {
				let successor = findMin(in: node.right!)
				node.key = successor.key
				node.value = successor.value
				node.right = removeValue(forKey: successor.key, in: node.right, removedValue: &removedValue)
			}
		}
		
		return node
	}
	
	private func findMin(in node: Node) -> Node {
		var current = node
		while let left = current.left {
			current = left
		}
		return current
	}
	
	// MARK: - Ordered Operations
	
	func keys() -> [Key] {
		var result: [Key] = []
		inorderTraversal(root) { result.append($0.key) }
		return result
	}
	
	func values() -> [Value] {
		var result: [Value] = []
		inorderTraversal(root) { result.append($0.value) }
		return result
	}
	
	private func inorderTraversal(_ node: Node?, visit: (Node) -> Void) {
		guard let node = node else { return }
		inorderTraversal(node.left, visit: visit)
		visit(node)
		inorderTraversal(node.right, visit: visit)
	}
}

4. Trie (Prefix Tree) for String Keys

A specialized map implementation for string keys that supports prefix operations:

class TrieMap<Value> {
	private class Node {
		var value: Value?
		var children: [Character: Node] = [:]
		var isEndOfWord: Bool = false
	}
	
	private let root = Node()
	private var count = 0
	
	var isEmpty: Bool {
		return count == 0
	}
	
	var size: Int {
		return count
	}
	
	func setValue(_ value: Value, forKey key: String) {
		var current = root
		
		for char in key {
			if current.children[char] == nil {
				current.children[char] = Node()
			}
			current = current.children[char]!
		}
		
		if !current.isEndOfWord {
			count += 1
		}
		
		current.value = value
		current.isEndOfWord = true
	}
	
	func getValue(forKey key: String) -> Value? {
		var current = root
		
		for char in key {
			guard let node = current.children[char] else {
				return nil
			}
			current = node
		}
		
		return current.isEndOfWord ? current.value : nil
	}
	
	func removeValue(forKey key: String) -> Value? {
		return removeValue(forKey: key, from: root, index: key.startIndex)
	}
	
	private func removeValue(forKey key: String, from node: Node, index: String.Index) -> Value? {
		if index == key.endIndex {
			guard node.isEndOfWord else { return nil }
			
			let removedValue = node.value
			node.isEndOfWord = false
			node.value = nil
			count -= 1
			return removedValue
		}
		
		let char = key[index]
		guard let childNode = node.children[char] else { return nil }
		
		let removedValue = removeValue(forKey: key, from: childNode, index: key.index(after: index))
		
		// Clean up empty nodes
		if !childNode.isEndOfWord && childNode.children.isEmpty {
			node.children[char] = nil
		}
		
		return removedValue
	}
	
	// MARK: - Prefix Operations
	
	func keysWithPrefix(_ prefix: String) -> [String] {
		var current = root
		
		for char in prefix {
			guard let node = current.children[char] else {
				return []
			}
			current = node
		}
		
		var results: [String] = []
		collectKeys(from: current, prefix: prefix, results: &results)
		return results
	}
	
	private func collectKeys(from node: Node, prefix: String, results: inout [String]) {
		if node.isEndOfWord {
			results.append(prefix)
		}
		
		for (char, childNode) in node.children {
			collectKeys(from: childNode, prefix: prefix + String(char), results: &results)
		}
	}
	
	func hasPrefix(_ prefix: String) -> Bool {
		var current = root
		
		for char in prefix {
			guard let node = current.children[char] else {
				return false
			}
			current = node
		}
		
		return true
	}
}

Swift’s Built-in Dictionary

Swift’s Dictionary type is a highly optimized hash table implementation. Let’s explore advanced usage patterns:

Advanced Dictionary Operations

extension Dictionary {
	// Merge dictionaries with custom conflict resolution
	mutating func merge<S: Sequence>(_ other: S, uniquingKeysWith combine: (Value, Value) throws -> Value) rethrows 
	where S.Element == (Key, Value) {
		for (key, value) in other {
			self[key] = try combine(self[key] ?? value, value)
		}
	}
	
	// Group elements by key
	static func grouping<S: Sequence>(_ values: S, by keyForValue: (S.Element) throws -> Key) rethrows -> [Key: [S.Element]]
	where Value == [S.Element] {
		return try Dictionary<Key, [S.Element]>(grouping: values, by: keyForValue)
	}
	
	// Transform values while preserving keys
	func mapValues<T>(_ transform: (Value) throws -> T) rethrows -> [Key: T] {
		var result: [Key: T] = [:]
		for (key, value) in self {
			result[key] = try transform(value)
		}
		return result
	}
	
	// Compact map values, removing nil results
	func compactMapValues<T>(_ transform: (Value) throws -> T?) rethrows -> [Key: T] {
		var result: [Key: T] = [:]
		for (key, value) in self {
			if let transformedValue = try transform(value) {
				result[key] = transformedValue
			}
		}
		return result
	}
}

Custom Dictionary Implementation with Swift Features

struct CustomDictionary<Key: Hashable, Value> {
	private var storage: [Key: Value] = [:]
	
	var isEmpty: Bool {
		return storage.isEmpty
	}
	
	var count: Int {
		return storage.count
	}
	
	var keys: Dictionary<Key, Value>.Keys {
		return storage.keys
	}
	
	var values: Dictionary<Key, Value>.Values {
		return storage.values
	}
	
	subscript(key: Key) -> Value? {
		get {
			return storage[key]
		}
		set {
			storage[key] = newValue
		}
	}
	
	// Default value subscript
	subscript(key: Key, default defaultValue: @autoclosure () -> Value) -> Value {
		get {
			return storage[key] ?? defaultValue()
		}
		set {
			storage[key] = newValue
		}
	}
	
	mutating func updateValue(_ value: Value, forKey key: Key) -> Value? {
		return storage.updateValue(value, forKey: key)
	}
	
	mutating func removeValue(forKey key: Key) -> Value? {
		return storage.removeValue(forKey: key)
	}
	
	mutating func merge<S: Sequence>(_ other: S, uniquingKeysWith combine: (Value, Value) throws -> Value) rethrows 
	where S.Element == (Key, Value) {
		try storage.merge(other, uniquingKeysWith: combine)
	}
}

// MARK: - Collection Conformance

extension CustomDictionary: Collection {
	typealias Element = (key: Key, value: Value)
	typealias Index = Dictionary<Key, Value>.Index
	
	var startIndex: Index {
		return storage.startIndex
	}
	
	var endIndex: Index {
		return storage.endIndex
	}
	
	subscript(index: Index) -> Element {
		let (key, value) = storage[index]
		return (key: key, value: value)
	}
	
	func index(after i: Index) -> Index {
		return storage.index(after: i)
	}
}

// MARK: - ExpressibleByDictionaryLiteral

extension CustomDictionary: ExpressibleByDictionaryLiteral {
	init(dictionaryLiteral elements: (Key, Value)...) {
		self.storage = Dictionary(uniqueKeysWithValues: elements)
	}
}

Time Complexity Analysis

Hash Table Operations

Operation	Average Case	Worst Case	Best Case
Insert	O(1)	O(n)	O(1)
Search	O(1)	O(n)	O(1)
Delete	O(1)	O(n)	O(1)

Binary Search Tree Map Operations

Operation	Average Case	Worst Case	Best Case
Insert	O(log n)	O(n)	O(log n)
Search	O(log n)	O(n)	O(log n)
Delete	O(log n)	O(n)	O(log n)

Trie Operations

Operation	Time Complexity	Space Complexity
Insert	O(m)	O(m)
Search	O(m)	O(1)
Delete	O(m)	O(1)
Prefix	O(p + k)	O(k)

Where m = key length, p = prefix length, k = number of keys with prefix

Real-World Applications

1. LRU Cache Implementation

class LRUCache<Key: Hashable, Value> {
	private class Node {
		let key: Key
		var value: Value
		var prev: Node?
		var next: Node?
		
		init(key: Key, value: Value) {
			self.key = key
			self.value = value
		}
	}
	
	private let capacity: Int
	private var cache: [Key: Node] = [:]
	private let head = Node(key: "" as! Key, value: "" as! Value) // Dummy head
	private let tail = Node(key: "" as! Key, value: "" as! Value) // Dummy tail
	
	init(capacity: Int) {
		self.capacity = capacity
		head.next = tail
		tail.prev = head
	}
	
	func get(_ key: Key) -> Value? {
		guard let node = cache[key] else { return nil }
		
		// Move to front
		moveToFront(node)
		return node.value
	}
	
	func set(_ key: Key, _ value: Value) {
		if let existingNode = cache[key] {
			existingNode.value = value
			moveToFront(existingNode)
		} else {
			let newNode = Node(key: key, value: value)
			cache[key] = newNode
			addToFront(newNode)
			
			if cache.count > capacity {
				removeLeastUsed()
			}
		}
	}
	
	private func moveToFront(_ node: Node) {
		removeFromList(node)
		addToFront(node)
	}
	
	private func addToFront(_ node: Node) {
		node.next = head.next
		node.prev = head
		head.next?.prev = node
		head.next = node
	}
	
	private func removeFromList(_ node: Node) {
		node.prev?.next = node.next
		node.next?.prev = node.prev
	}
	
	private func removeLeastUsed() {
		if let lastNode = tail.prev, lastNode !== head {
			cache[lastNode.key] = nil
			removeFromList(lastNode)
		}
	}
}

2. Word Frequency Counter

class WordFrequencyCounter {
	private var frequencies: [String: Int] = [:]
	
	func addText(_ text: String) {
		let words = text.lowercased()
			.components(separatedBy: .whitespacesAndNewlines)
			.compactMap { word in
				let cleaned = word.trimmingCharacters(in: .punctuationCharacters)
				return cleaned.isEmpty ? nil : cleaned
			}
		
		for word in words {
			frequencies[word, default: 0] += 1
		}
	}
	
	func frequency(of word: String) -> Int {
		return frequencies[word.lowercased()] ?? 0
	}
	
	func mostFrequent(count: Int) -> [(word: String, frequency: Int)] {
		return frequencies
			.sorted { $0.value > $1.value }
			.prefix(count)
			.map { (word: $0.key, frequency: $0.value) }
	}
	
	func wordsWithFrequency(_ frequency: Int) -> [String] {
		return frequencies
			.compactMap { $0.value == frequency ? $0.key : nil }
			.sorted()
	}
}

3. Configuration Manager

class ConfigurationManager {
	private var configurations: [String: Any] = [:]
	private let queue = DispatchQueue(label: "config.queue", attributes: .concurrent)
	
	func setValue<T>(_ value: T, forKey key: String) {
		queue.async(flags: .barrier) {
			self.configurations[key] = value
		}
	}
	
	func getValue<T>(forKey key: String, type: T.Type) -> T? {
		return queue.sync {
			return configurations[key] as? T
		}
	}
	
	func getValue<T>(forKey key: String, default defaultValue: T) -> T {
		return queue.sync {
			return configurations[key] as? T ?? defaultValue
		}
	}
	
	func removeValue(forKey key: String) {
		queue.async(flags: .barrier) {
			self.configurations[key] = nil
		}
	}
	
	func allKeys() -> [String] {
		return queue.sync {
			return Array(configurations.keys)
		}
	}
	
	func clear() {
		queue.async(flags: .barrier) {
			self.configurations.removeAll()
		}
	}
}

4. Database Index Simulation

struct DatabaseIndex<Key: Hashable, RecordID: Hashable> {
	private var index: [Key: Set<RecordID>] = [:]
	
	mutating func addRecord(id: RecordID, forKey key: Key) {
		index[key, default: Set<RecordID>()].insert(id)
	}
	
	mutating func removeRecord(id: RecordID, forKey key: Key) {
		index[key]?.remove(id)
		if index[key]?.isEmpty == true {
			index[key] = nil
		}
	}
	
	func findRecords(forKey key: Key) -> Set<RecordID> {
		return index[key] ?? Set<RecordID>()
	}
	
	func findRecords(forKeys keys: [Key]) -> Set<RecordID> {
		return keys.reduce(into: Set<RecordID>()) { result, key in
			result.formUnion(findRecords(forKey: key))
		}
	}
	
	func findRecords(matchingAll keys: [Key]) -> Set<RecordID> {
		guard let firstKey = keys.first else { return Set<RecordID>() }
		
		return keys.dropFirst().reduce(findRecords(forKey: firstKey)) { result, key in
			result.intersection(findRecords(forKey: key))
		}
	}
}

Performance Optimization Techniques

1. Memory-Efficient String Interning

class StringInterner {
	private var internedStrings: [String: String] = [:]
	
	func intern(_ string: String) -> String {
		if let existingString = internedStrings[string] {
			return existingString
		} else {
			internedStrings[string] = string
			return string
		}
	}
	
	func clear() {
		internedStrings.removeAll()
	}
	
	var count: Int {
		return internedStrings.count
	}
}

2. Batch Operations for Better Performance

extension Dictionary {
	mutating func setBatch<S: Sequence>(_ keyValuePairs: S) where S.Element == (Key, Value) {
		reserveCapacity(count + keyValuePairs.underestimatedCount)
		
		for (key, value) in keyValuePairs {
			self[key] = value
		}
	}
	
	func getBatch<S: Sequence>(_ keys: S) -> [Key: Value] where S.Element == Key {
		var result: [Key: Value] = [:]
		result.reserveCapacity(keys.underestimatedCount)
		
		for key in keys {
			if let value = self[key] {
				result[key] = value
			}
		}
		
		return result
	}
}

Best Practices and Design Patterns

1. Type-Safe Configuration Keys

protocol ConfigurationKey {
	associatedtype Value
	static var defaultValue: Value { get }
}

struct ServerURLKey: ConfigurationKey {
	typealias Value = URL
	static let defaultValue = URL(string: "https://api.example.com")!
}

struct MaxRetryCountKey: ConfigurationKey {
	typealias Value = Int
	static let defaultValue = 3
}

class TypeSafeConfiguration {
	private var storage: [String: Any] = [:]
	
	func setValue<Key: ConfigurationKey>(_ value: Key.Value, for key: Key.Type) {
		storage[String(describing: key)] = value
	}
	
	func getValue<Key: ConfigurationKey>(for key: Key.Type) -> Key.Value {
		return storage[String(describing: key)] as? Key.Value ?? Key.defaultValue
	}
}

2. Lazy Loading Dictionary

class LazyDictionary<Key: Hashable, Value> {
	private var storage: [Key: Value] = [:]
	private let valueProvider: (Key) -> Value?
	
	init(valueProvider: @escaping (Key) -> Value?) {
		self.valueProvider = valueProvider
	}
	
	subscript(key: Key) -> Value? {
		if let existingValue = storage[key] {
			return existingValue
		}
		
		if let computedValue = valueProvider(key) {
			storage[key] = computedValue
			return computedValue
		}
		
		return nil
	}
	
	func preload(keys: [Key]) {
		for key in keys {
			_ = self[key] // Trigger lazy loading
		}
	}
}

3. Multi-Level Cache

class MultiLevelCache<Key: Hashable, Value> {
	private var l1Cache: [Key: Value] = [:]
	private var l2Cache: [Key: Value] = [:]
	private let l1Capacity: Int
	private let l2Capacity: Int
	private let valueProvider: (Key) -> Value?
	
	init(l1Capacity: Int, l2Capacity: Int, valueProvider: @escaping (Key) -> Value?) {
		self.l1Capacity = l1Capacity
		self.l2Capacity = l2Capacity
		self.valueProvider = valueProvider
	}
	
	func getValue(for key: Key) -> Value? {
		// Check L1 cache first
		if let value = l1Cache[key] {
			return value
		}
		
		// Check L2 cache
		if let value = l2Cache[key] {
			promoteToL1(key: key, value: value)
			return value
		}
		
		// Load from source
		if let value = valueProvider(key) {
			setValue(value, for: key)
			return value
		}
		
		return nil
	}
	
	private func setValue(_ value: Value, for key: Key) {
		if l1Cache.count >= l1Capacity {
			evictFromL1()
		}
		
		l1Cache[key] = value
	}
	
	private func promoteToL1(key: Key, value: Value) {
		l2Cache[key] = nil
		setValue(value, for: key)
	}
	
	private func evictFromL1() {
		if let (key, value) = l1Cache.randomElement() {
			l1Cache[key] = nil
			
			if l2Cache.count >= l2Capacity {
				l2Cache.removeValue(forKey: l2Cache.randomElement()!.key)
			}
			
			l2Cache[key] = value
		}
	}
}

Testing and Debugging

Unit Testing Dictionary Implementations

import XCTest

class HashTableTests: XCTestCase {
	var hashTable: HashTable<String, Int>!
	
	override func setUp() {
		super.setUp()
		hashTable = HashTable<String, Int>()
	}
	
	func testInsertAndRetrieve() {
		hashTable["key1"] = 100
		hashTable["key2"] = 200
		
		XCTAssertEqual(hashTable["key1"], 100)
		XCTAssertEqual(hashTable["key2"], 200)
		XCTAssertEqual(hashTable.size, 2)
	}
	
	func testUpdateExistingKey() {
		hashTable["key1"] = 100
		hashTable["key1"] = 150
		
		XCTAssertEqual(hashTable["key1"], 150)
		XCTAssertEqual(hashTable.size, 1)
	}
	
	func testRemoveKey() {
		hashTable["key1"] = 100
		let removedValue = hashTable.removeValue(forKey: "key1")
		
		XCTAssertEqual(removedValue, 100)
		XCTAssertNil(hashTable["key1"])
		XCTAssertEqual(hashTable.size, 0)
	}
	
	func testCollisionHandling() {
		// Insert many items to force collisions
		for i in 0..<100 {
			hashTable["key\(i)"] = i
		}
		
		// Verify all items are retrievable
		for i in 0..<100 {
			XCTAssertEqual(hashTable["key\(i)"], i)
		}
		
		XCTAssertEqual(hashTable.size, 100)
	}
	
	func testResizing() {
		let initialCapacity = 16
		let itemsToInsert = 50 // This should trigger resize
		
		for i in 0..<itemsToInsert {
			hashTable["key\(i)"] = i
		}
		
		// All items should still be accessible after resize
		for i in 0..<itemsToInsert {
			XCTAssertEqual(hashTable["key\(i)"], i)
		}
	}
	
	func testPerformance() {
		measure {
			for i in 0..<10000 {
				hashTable["key\(i)"] = i
			}
		}
	}
}

class BSTMapTests: XCTestCase {
	var bstMap: BSTMap<String, Int>!
	
	override func setUp() {
		super.setUp()
		bstMap = BSTMap<String, Int>()
	}
	
	func testOrderedTraversal() {
		let keys = ["dog", "cat", "elephant", "ant", "bear"]
		for (index, key) in keys.enumerated() {
			bstMap.setValue(index, forKey: key)
		}
		
		let sortedKeys = bstMap.keys()
		XCTAssertEqual(sortedKeys, ["ant", "bear", "cat", "dog", "elephant"])
	}
	
	func testBalanceIssues() {
		// Insert in sorted order (worst case for basic BST)
		for i in 1...10 {
			bstMap.setValue(i, forKey: "key\(String(format: "%02d", i))")
		}
		
		// Should still work, but performance will be degraded
		for i in 1...10 {
			XCTAssertEqual(bstMap.getValue(forKey: "key\(String(format: "%02d", i))"), i)
		}
	}
}

class TrieMapTests: XCTestCase {
	var trie: TrieMap<Int>!
	
	override func setUp() {
		super.setUp()
		trie = TrieMap<Int>()
	}
	
	func testPrefixOperations() {
		trie.setValue(1, forKey: "cat")
		trie.setValue(2, forKey: "car")
		trie.setValue(3, forKey: "card")
		trie.setValue(4, forKey: "care")
		trie.setValue(5, forKey: "dog")
		
		let carPrefixKeys = trie.keysWithPrefix("car")
		XCTAssertEqual(Set(carPrefixKeys), Set(["car", "card", "care"]))
		
		XCTAssertTrue(trie.hasPrefix("ca"))
		XCTAssertFalse(trie.hasPrefix("bat"))
	}
	
	func testEmptyStringHandling() {
		trie.setValue(42, forKey: "")
		XCTAssertEqual(trie.getValue(forKey: ""), 42)
		
		let emptyPrefixKeys = trie.keysWithPrefix("")
		XCTAssertTrue(emptyPrefixKeys.contains(""))
	}
}

Performance Profiling Tools

class PerformanceProfiler {
	static func measureTime<T>(operation: () throws -> T) rethrows -> (result: T, time: TimeInterval) {
		let startTime = CFAbsoluteTimeGetCurrent()
		let result = try operation()
		let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
		return (result, timeElapsed)
	}
	
	static func benchmarkDictionaryOperations<Key: Hashable, Value>(
		dictionary: inout [Key: Value],
		keys: [Key],
		values: [Value]
	) -> [String: TimeInterval] {
		precondition(keys.count == values.count)
		
		var results: [String: TimeInterval] = [:]
		
		// Benchmark insertions
		let (_, insertTime) = measureTime {
			for (key, value) in zip(keys, values) {
				dictionary[key] = value
			}
		}
		results["insert"] = insertTime
		
		// Benchmark lookups
		let (_, lookupTime) = measureTime {
			for key in keys {
				_ = dictionary[key]
			}
		}
		results["lookup"] = lookupTime
		
		// Benchmark updates
		let (_, updateTime) = measureTime {
			for (key, value) in zip(keys, values) {
				dictionary[key] = value
			}
		}
		results["update"] = updateTime
		
		// Benchmark deletions
		let (_, deleteTime) = measureTime {
			for key in keys {
				dictionary[key] = nil
			}
		}
		results["delete"] = deleteTime
		
		return results
	}
}

Memory Usage Analysis

class MemoryProfiler {
	static func measureMemoryUsage<T>(operation: () -> T) -> (result: T, memoryUsed: Int) {
		let before = mach_task_basic_info()
		let result = operation()
		let after = mach_task_basic_info()
		
		let memoryUsed = Int(after.resident_size - before.resident_size)
		return (result, memoryUsed)
	}
	
	private static func mach_task_basic_info() -> mach_task_basic_info {
		var info = mach_task_basic_info()
		var count = mach_msg_type_number_t(MemoryLayout<mach_task_basic_info>.size) / 4
		
		let result = withUnsafeMutablePointer(to: &info) {
			$0.withMemoryRebound(to: integer_t.self, capacity: 1) {
				task_info(mach_task_self_, task_flavor_t(MACH_TASK_BASIC_INFO), $0, &count)
			}
		}
		
		guard result == KERN_SUCCESS else {
			fatalError("Failed to get memory info")
		}
		
		return info
	}
}

Common Pitfalls and Solutions

1. Hash Function Quality

// Poor hash function - causes many collisions
struct PoorHashable: Hashable {
	let value: String
	
	func hash(into hasher: inout Hasher) {
		hasher.combine(value.count) // Only uses string length!
	}
}

// Better hash function - distributes values well
struct BetterHashable: Hashable {
	let value: String
	
	func hash(into hasher: inout Hasher) {
		hasher.combine(value) // Uses entire string content
	}
}

// Custom hash function for specific needs
struct CustomHashable: Hashable {
	let id: Int
	let category: String
	
	func hash(into hasher: inout Hasher) {
		hasher.combine(id)
		hasher.combine(category)
	}
	
	static func == (lhs: CustomHashable, rhs: CustomHashable) -> Bool {
		return lhs.id == rhs.id && lhs.category == rhs.category
	}
}

2. Memory Leaks in Reference-Based Maps

// Potential memory leak - strong reference cycles
class Node {
	let id: String
	var connections: [String: Node] = [:]
	
	init(id: String) {
		self.id = id
	}
}

// Solution: Use weak references where appropriate
class SafeNode {
	let id: String
	private var _connections: [String: WeakRef<SafeNode>] = [:]
	
	init(id: String) {
		self.id = id
	}
	
	func addConnection(_ node: SafeNode) {
		_connections[node.id] = WeakRef(node)
	}
	
	func getConnection(_ id: String) -> SafeNode? {
		return _connections[id]?.value
	}
	
	func removeDeadConnections() {
		_connections = _connections.compactMapValues { ref in
			ref.value != nil ? ref : nil
		}
	}
}

class WeakRef<T: AnyObject> {
	weak var value: T?
	
	init(_ value: T) {
		self.value = value
	}
}

3. Thread Safety Considerations

class ThreadSafeDictionary<Key: Hashable, Value> {
	private var dictionary: [Key: Value] = [:]
	private let queue = DispatchQueue(label: "dictionary.queue", attributes: .concurrent)
	
	subscript(key: Key) -> Value? {
		get {
			return queue.sync {
				return dictionary[key]
			}
		}
		set {
			queue.async(flags: .barrier) {
				self.dictionary[key] = newValue
			}
		}
	}
	
	func getValue(forKey key: Key) -> Value? {
		return queue.sync {
			return dictionary[key]
		}
	}
	
	func setValue(_ value: Value, forKey key: Key) {
		queue.async(flags: .barrier) {
			self.dictionary[key] = value
		}
	}
	
	func removeValue(forKey key: Key) -> Value? {
		return queue.sync(flags: .barrier) {
			return self.dictionary.removeValue(forKey: key)
		}
	}
	
	var count: Int {
		return queue.sync {
			return dictionary.count
		}
	}
}

Advanced Topics

1. Consistent Hashing for Distributed Systems

class ConsistentHash<Node: Hashable> {
	private var ring: [UInt32: Node] = [:]
	private let virtualNodes: Int
	
	init(virtualNodes: Int = 100) {
		self.virtualNodes = virtualNodes
	}
	
	func addNode(_ node: Node) {
		for i in 0..<virtualNodes {
			let hash = computeHash("\(node):\(i)")
			ring[hash] = node
		}
	}
	
	func removeNode(_ node: Node) {
		for i in 0..<virtualNodes {
			let hash = computeHash("\(node):\(i)")
			ring[hash] = nil
		}
	}
	
	func getNode(forKey key: String) -> Node? {
		guard !ring.isEmpty else { return nil }
		
		let hash = computeHash(key)
		let sortedHashes = ring.keys.sorted()
		
		// Find the first node clockwise from the hash
		for nodeHash in sortedHashes {
			if nodeHash >= hash {
				return ring[nodeHash]
			}
		}
		
		// Wrap around to the first node
		return ring[sortedHashes.first!]
	}
	
	private func computeHash(_ input: String) -> UInt32 {
		return UInt32(input.hashValue) & 0xFFFFFFFF
	}
}

2. Bloom Filters for Membership Testing

struct BloomFilter {
	private var bitArray: [Bool]
	private let hashFunctions: [(String) -> Int]
	
	init(size: Int, hashFunctionCount: Int) {
		self.bitArray = Array(repeating: false, count: size)
		self.hashFunctions = (0..<hashFunctionCount).map { seed in
			return { string in
				var hasher = Hasher()
				hasher.combine(string)
				hasher.combine(seed)
				return abs(hasher.finalize()) % size
			}
		}
	}
	
	mutating func insert(_ item: String) {
		for hashFunction in hashFunctions {
			let index = hashFunction(item)
			bitArray[index] = true
		}
	}
	
	func mightContain(_ item: String) -> Bool {
		for hashFunction in hashFunctions {
			let index = hashFunction(item)
			if !bitArray[index] {
				return false
			}
		}
		return true
	}
	
	func definitelyDoesNotContain(_ item: String) -> Bool {
		return !mightContain(item)
	}
}

3. Cuckoo Hashing Implementation

struct CuckooHash<Key: Hashable, Value> {
	private var table1: [Entry?]
	private var table2: [Entry?]
	private let maxIterations = 8
	
	private struct Entry {
		let key: Key
		let value: Value
	}
	
	init(capacity: Int = 16) {
		self.table1 = Array(repeating: nil, count: capacity)
		self.table2 = Array(repeating: nil, count: capacity)
	}
	
	private func hash1(_ key: Key) -> Int {
		return abs(key.hashValue) % table1.count
	}
	
	private func hash2(_ key: Key) -> Int {
		return abs(key.hashValue.multipliedReportingOverflow(by: 31).partialValue) % table2.count
	}
	
	mutating func setValue(_ value: Value, forKey key: Key) {
		let newEntry = Entry(key: key, value: value)
		
		if insert(newEntry) {
			return
		}
		
		// Rehash if insertion failed
		rehash()
		_ = insert(newEntry)
	}
	
	private mutating func insert(_ entry: Entry) -> Bool {
		var currentEntry = entry
		
		for _ in 0..<maxIterations {
			let index1 = hash1(currentEntry.key)
			if table1[index1] == nil {
				table1[index1] = currentEntry
				return true
			}
			
			// Kick out existing entry and place it in table2
			let evicted = table1[index1]!
			table1[index1] = currentEntry
			
			let index2 = hash2(evicted.key)
			if table2[index2] == nil {
				table2[index2] = evicted
				return true
			}
			
			// Kick out from table2 and continue cycle
			currentEntry = table2[index2]!
			table2[index2] = evicted
		}
		
		return false // Cycle detected, need to rehash
	}
	
	private mutating func rehash() {
		let oldTable1 = table1
		let oldTable2 = table2
		
		table1 = Array(repeating: nil, count: table1.count * 2)
		table2 = Array(repeating: nil, count: table2.count * 2)
		
		for entry in oldTable1.compactMap({ $0 }) {
			_ = insert(entry)
		}
		
		for entry in oldTable2.compactMap({ $0 }) {
			_ = insert(entry)
		}
	}
	
	func getValue(forKey key: Key) -> Value? {
		let index1 = hash1(key)
		if let entry = table1[index1], entry.key == key {
			return entry.value
		}
		
		let index2 = hash2(key)
		if let entry = table2[index2], entry.key == key {
			return entry.value
		}
		
		return nil
	}
}

Exercises

Exercise 1: LFU Cache

Implement a Least Frequently Used (LFU) cache that evicts the least frequently accessed items when capacity is exceeded.

Exercise 2: Multi-Map Implementation

Create a data structure that allows multiple values for a single key, supporting operations like add(key, value), remove(key, value), and getAll(key).

Exercise 3: Ordered Dictionary

Implement a dictionary that maintains insertion order while providing O(1) access times.

Exercise 4: Radix Tree (Patricia Trie)

Build a compressed trie that minimizes space usage for string keys with common prefixes.

Exercise 5: Robin Hood Hashing

Implement a hash table using Robin Hood hashing for better worst-case performance.

Summary

Maps and dictionaries are versatile data structures that form the foundation of many algorithms and applications. Understanding their various implementations helps you choose the right tool for specific requirements:

Key Takeaways:

Hash tables provide average O(1) operations but can degrade to O(n) in worst cases
Binary search trees offer O(log n) operations with ordered traversal capabilities
Tries excel at prefix-based operations and string key scenarios
Swift’s Dictionary is highly optimized and suitable for most use cases
Thread safety requires careful consideration in concurrent environments
Memory efficiency and cache locality significantly impact real-world performance

When to Choose Each Implementation:

Use hash tables for general-purpose key-value storage with fast access
Choose BST maps when you need ordered keys or range queries
Select tries for prefix matching and string-heavy applications
Consider specialized implementations for specific performance requirements

Understanding these fundamentals enables you to build efficient, scalable applications and make informed decisions about data structure selection in your Swift projects.