什么是HashMap？
HashMap是一种常见的数据结构，用于存储键值对（key-value pairs）。它提供了高效的插入、删除和查找操作，并且允许根据键快速访问对应的值。
HashMap的核心思想是使用哈希函数将键映射到存储桶（bucket）的索引上。存储桶是一个数组，每个桶可以存储一个或多个键值对。通过哈希函数，键被转换成一个整数索引，然后将对应的值存储在该索引对应的桶中。
当需要插入、查找或删除一个键值对时，HashMap会使用哈希函数计算键对应的索引，然后在对应的桶中执行操作。哈希函数的设计目标是将键均匀地映射到不同的索引上，这样可以使得操作的时间复杂度接近常数级别。
在HashMap中，键是唯一的，而值可以重复。当存在两个或多个键被哈希到同一个索引上时，称为哈希碰撞（hash collision）。
HashMap的优点包括快速的查找、插入和删除操作，适用于大量数据的存储和查询。然而，它的缺点是相对于其他数据结构，会占用更多的内存空间，并且在哈希碰撞较多时，性能可能会下降。
在许多编程语言和框架中，包括Java、C++、Python等，都提供了HashMap类或类似的数据结构，以方便开发者使用和操作键值对。
哈希碰撞（hash collision）
哈希碰撞（hash collision）指的是不同的键通过哈希函数计算后得到相同的哈希值，从而被映射到了哈希表（如HashMap）中的同一个桶（bucket）。哈希函数的设计目标是将键均匀地映射到不同的索引上，但由于哈希函数的输出空间通常远小于键的输入空间，碰撞是不可避免的。
解决哈希碰撞的常见方法有以下两种：
-
链地址法（Chaining）：在每个桶中使用链表（或其他数据结构，如红黑树）来存储多个键值对。当发生碰撞时，新的键值对可以添加到对应桶的链表（或其他数据结构）中。这样，每个桶实际上成为一个键值对的集合，通过遍历链表（或其他数据结构），可以在常数时间内找到特定的键值对。
当链表过长时，可能会导致性能下降，因为查找操作需要遍历整个链表。为了解决这个问题，一些哈希表实现在链表长度达到一定阈值时，会将链表转换为更高效的数据结构（如红黑树）。这样可以提高查找操作的效率。
-
开放寻址法（Open Addressing）：在每个桶中直接存储键值对，当发生碰撞时，通过一定的探测方法（如线性探测、二次探测等）在哈希表的其他位置寻找可用的空槽来存储冲突的键值对。这样，每个桶只存储一个键值对。
当进行查找操作时，如果遇到冲突的桶，会根据探测方法继续寻找下一个桶，直到找到目标键或者遇到空槽。开放寻址法的优点是可以减少额外的内存开销，但当哈希表填充度较高时，性能可能会下降。
在选择解决哈希碰撞的方法时，需要根据具体的应用场景和需求进行权衡。例如，链地址法适用于存储大量键值对且碰撞较多的情况，而开放寻址法适用于空间敏感、存储较少键值对且碰撞相对较少的情况。
另外，为了减少哈希碰撞的发生，设计良好的哈希函数至关重要。好的哈希函数能够将键均匀地映射到哈希表的不同桶中，从而减少碰撞的概率。
HashMap的swift实现
以下是一个简单的 HashMap 的 Swift 实现代码：
struct KeyValuePair<Key: Hashable, Value> {
let key: Key
var value: Value
}
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() 方法用于打印哈希表的内容，以便检查和调试。
