HashMap的核心思想是使用哈希函数将键映射到存储桶(bucket)的索引上。存储桶是一个数组,每个桶可以存储一个或多个键值对。通过哈希函数,键被转换成一个整数索引,然后将对应的值存储在该索引对应的桶中。
当需要插入、查找或删除一个键值对时,HashMap会使用哈希函数计算键对应的索引,然后在对应的桶中执行操作。哈希函数的设计目标是将键均匀地映射到不同的索引上,这样可以使得操作的时间复杂度接近常数级别。
在HashMap中,键是唯一的,而值可以重复。当存在两个或多个键被哈希到同一个索引上时,称为哈希碰撞(hash collision)。HashMap的优点包括快速的查找、插入和删除操作,适用于大量数据的存储和查询。然而,它的缺点是相对于其他数据结构,会占用更多的内存空间,并且在哈希碰撞较多时,性能可能会下降。
在许多编程语言和框架中,包括Java、C++、Python等,都提供了HashMap类或类似的数据结构,以方便开发者使用和操作键值对。
哈希碰撞(hash collision)指的是不同的键通过哈希函数计算后得到相同的哈希值,从而被映射到了哈希表(如HashMap)中的同一个桶(bucket)。哈希函数的设计目标是将键均匀地映射到不同的索引上,但由于哈希函数的输出空间通常远小于键的输入空间,碰撞是不可避免的。
在选择解决哈希碰撞的方法时,需要根据具体的应用场景和需求进行权衡。例如,链地址法适用于存储大量键值对且碰撞较多的情况,而开放寻址法适用于空间敏感、存储较少键值对且碰撞相对较少的情况。
另外,为了减少哈希碰撞的发生,设计良好的哈希函数至关重要。好的哈希函数能够将键均匀地映射到哈希表的不同桶中,从而减少碰撞的概率。
struct KeyValuePair<Key: Hashable, Value> { let key: Key var value: Value } // 堆代码 duidaima.com struct HashMap<Key: Hashable, Value> { private var buckets: [[KeyValuePair<Key, Value>]] // 存储键值对的桶数组 private let initialCapacity: Int // 哈希表的初始容量 private var count: Int // 哈希表中键值对的数量 init(capacity: Int = 16) { buckets = Array(repeating: [], count: capacity) // 初始化桶数组 initialCapacity = capacity // 保存初始容量 count = 0 // 初始化键值对数量为 0 } private func getIndex(forKey key: Key) -> Int { let hashCode = abs(key.hashValue) // 获取键的哈希值 return hashCode % buckets.count // 计算哈希值对应的桶的索引 } mutating func setValue(_ value: Value, forKey key: Key) { let index = getIndex(forKey: key) // 获取键对应的桶的索引 for i in 0..<buckets[index].count { if buckets[index][i].key == key { buckets[index][i].value = value // 如果键已存在,则更新对应的值 return } } buckets[index].append(KeyValuePair(key: key, value: value)) // 键不存在,则将新的键值对添加到桶中 count += 1 // 更新键值对数量 if Double(count) / Double(buckets.count) > 0.75 { // 如果装载因子超过 0.75,则进行扩容 resize() } } private mutating func resize() { let newCapacity = buckets.count * 2 // 扩大为当前容量的两倍 var newBuckets = Array(repeating: [KeyValuePair<Key, Value>](), count: newCapacity) // 创建新的桶数组 for bucket in buckets { for pair in bucket { let newIndex = getIndex(forKey: pair.key) // 计算键在新桶数组中的索引 newBuckets[newIndex].append(pair) // 将键值对添加到新的桶中 } } buckets = newBuckets // 更新桶数组为新的桶数组 } func getValue(forKey key: Key) -> Value? { let index = getIndex(forKey: key) // 获取键对应的桶的索引 for pair in buckets[index] { if pair.key == key { return pair.value // 遍历桶中的键值对,找到对应的值并返回 } } return nil // 没有找到对应的值,则返回 nil } mutating func removeValue(forKey key: Key) { let index = getIndex(forKey: key) // 获取键对应的桶的索引 for i in 0..<buckets[index].count { if buckets[index][i].key == key { buckets[index].remove(at: i) // 遍历桶中的键值对,找到对应的键值对并移除 count -= 1 // 更新键值对数量 return } } } struct Iterator: IteratorProtocol { private let buckets: [[KeyValuePair<Key, Value>]] // 桶数组 private var currentIndex: (bucket: Int, element: Int) // 当前索引 init(buckets: [[KeyValuePair<Key, Value>]]) { self.buckets = buckets currentIndex = (0, 0) } mutating func next() -> KeyValuePair<Key, Value>? { while currentIndex.bucket < buckets.count { let bucket = buckets[currentIndex.bucket] while currentIndex.element < bucket.count { let pair = bucket[currentIndex.element] currentIndex.element += 1 return pair // 返回下一个键值对 } currentIndex.bucket += 1 currentIndex.element = 0 } return nil // 遍历完成,返回 nil } } func makeIterator() -> Iterator { return Iterator(buckets: buckets) // 创建迭代器 } func forEach(_ body: (KeyValuePair<Key, Value>) throws -> Void) rethrows { for bucket in buckets { for pair in bucket { try body(pair) // 对每个键值对执行操作 } } } func printHashMap() { for (index, bucket) in buckets.enumerated() { print("Bucket \(index):") for pair in bucket { print("\(pair.key): \(pair.value)") // 打印哈希表的内容 } } } }
这个 HashMap 实现使用了一个二维数组 buckets 来存储键值对。每个桶是一个数组,用于存储具有相同哈希值的键值对。在 setValue(_:forKey:) 方法中,我们首先使用哈希函数计算键的哈希值,然后根据哈希值找到对应的桶。在该桶中,我们遍历键值对,检查是否已经存在具有相同键的键值对。如果是,则更新现有键值对的值;如果不是,则将新的键值对添加到桶中。
在 getValue(forKey:) 方法中,我们根据键使用哈希函数计算哈希值,并找到对应的桶。然后,我们遍历该桶中的键值对,查找具有相同键的键值对。如果找到,则返回对应的值;否则,返回 nil。在 removeValue(forKey:) 方法中,我们根据键使用哈希函数计算哈希值,并找到对应的桶。然后,我们遍历该桶中的键值对,查找具有相同键的键值对。
如果找到,则从桶中移除该键值对。在 resize() 方法中,我们根据当前桶的数量扩展哈希表的容量。我们创建一个新的数组 newBuckets,其长度是当前桶数量的两倍。然后,我们将现有的键值对重新分配到新的桶中。最后,我们更新 buckets 为新的桶数组。printHashMap() 方法用于打印哈希表的内容,以便检查和调试。