面试题：Swift自定义哈希表及其性能优化

自定义哈希表设计与实现

定义哈希表结构体

struct CustomHashTable<Key: Hashable, Value> {
    private var buckets: [Bucket]
    private let capacity: Int
    private var count: Int = 0

    private struct Bucket {
        var pairs: [(Key, Value)] = []
    }

    init(capacity: Int = 16) {
        self.capacity = capacity
        self.buckets = Array(repeating: Bucket(), count: capacity)
    }
}

哈希函数
- 在Swift中，Hashable协议已经为我们提供了生成哈希值的方法。对于自定义类型，如果遵循Hashable协议，会自动生成哈希值。
- 这里简单地使用key.hashValue % capacity作为哈希函数来确定键值对应该存储在哪个桶中。

private func hash(forKey key: Key) -> Int {
    return abs(key.hashValue) % capacity
}

处理冲突的方法 - 链地址法
- 采用链地址法处理哈希冲突。每个桶（bucket）实际上是一个数组，用于存储所有哈希值相同的键值对。
- 插入操作：

mutating func insert(key: Key, value: Value) {
    let index = hash(forKey: key)
    var bucket = buckets[index]
    for (i, pair) in bucket.pairs.enumerated() {
        if pair.0 == key {
            bucket.pairs[i].1 = value
            return
        }
    }
    bucket.pairs.append((key, value))
    buckets[index] = bucket
    count += 1
    if Double(count) / Double(capacity) >= 0.75 {
        resize()
    }
}

- 查询操作：

func lookup(key: Key) -> Value? {
    let index = hash(forKey: key)
    let bucket = buckets[index]
    for pair in bucket.pairs {
        if pair.0 == key {
            return pair.1
        }
    }
    return nil
}

性能优化
- 负载因子调整：负载因子是哈希表中已存储元素的数量与哈希表容量的比值。这里选择0.75作为负载因子的阈值，当负载因子达到或超过这个值时，进行扩容。这是一个常见的经验值，在空间利用率和查询性能之间有较好的平衡。
- 扩容策略：

private mutating func resize() {
    let newCapacity = capacity * 2
    var newBuckets = Array(repeating: Bucket(), count: newCapacity)
    for bucket in buckets {
        for pair in bucket.pairs {
            let newIndex = abs(pair.0.hashValue) % newCapacity
            newBuckets[newIndex].pairs.append(pair)
        }
    }
    buckets = newBuckets
}

- 扩容时，将当前哈希表中的所有键值对重新计算哈希值，并插入到新的更大容量的哈希表中。这样可以降低哈希冲突的概率，提高查询性能。

通过以上设计和实现，我们构建了一个能够处理哈希冲突，并且在性能上可以通过负载因子和扩容策略进行优化的自定义哈希表。

星途面试题库

面试题：Swift自定义哈希表及其性能优化

知识考点

面试题答案

自定义哈希表设计与实现