• HashMap的swift实现
  • 发布于 2个月前
  • 101 热度
    0 评论
  • 飛雲
  • 0 粉丝 36 篇博客
  •   
什么是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
}
// 堆代码 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() 方法用于打印哈希表的内容,以便检查和调试。

用户评论