什么是HashMap？

HashMap是一种常见的数据结构，用于存储键值对（key-value pairs）。它提供了高效的插入、删除和查找操作，并且允许根据键快速访问对应的值。

HashMap的核心思想是使用哈希函数将键映射到存储桶（bucket）的索引上。存储桶是一个数组，每个桶可以存储一个或多个键值对。通过哈希函数，键被转换成一个整数索引，然后将对应的值存储在该索引对应的桶中。

当需要插入、查找或删除一个键值对时，HashMap会使用哈希函数计算键对应的索引，然后在对应的桶中执行操作。哈希函数的设计目标是将键均匀地映射到不同的索引上，这样可以使得操作的时间复杂度接近常数级别。

在HashMap中，键是唯一的，而值可以重复。当存在两个或多个键被哈希到同一个索引上时，称为哈希碰撞（hash collision）。

HashMap的优点包括快速的查找、插入和删除操作，适用于大量数据的存储和查询。然而，它的缺点是相对于其他数据结构，会占用更多的内存空间，并且在哈希碰撞较多时，性能可能会下降。

在许多编程语言和框架中，包括Java、C++、Python等，都提供了HashMap类或类似的数据结构，以方便开发者使用和操作键值对。

哈希碰撞（hash collision）

哈希碰撞（hash collision）指的是不同的键通过哈希函数计算后得到相同的哈希值，从而被映射到了哈希表（如HashMap）中的同一个桶（bucket）。哈希函数的设计目标是将键均匀地映射到不同的索引上，但由于哈希函数的输出空间通常远小于键的输入空间，碰撞是不可避免的。

解决哈希碰撞的常见方法有以下两种：

1. 链地址法（Chaining）：在每个桶中使用链表（或其他数据结构，如红黑树）来存储多个键值对。当发生碰撞时，新的键值对可以添加到对应桶的链表（或其他数据结构）中。这样，每个桶实际上成为一个键值对的集合，通过遍历链表（或其他数据结构），可以在常数时间内找到特定的键值对。

   当链表过长时，可能会导致性能下降，因为查找操作需要遍历整个链表。为了解决这个问题，一些哈希表实现在链表长度达到一定阈值时，会将链表转换为更高效的数据结构（如红黑树）。这样可以提高查找操作的效率。

2. 开放寻址法（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() 方法用于打印哈希表的内容，以便检查和调试。