Hash Table(散列表)-Swift实现

定义

散列表是一种通过关键字key来实现查找和存储的结构，通过散列方法在存储值的位置和key之间建立一个确定的、对应的关系，使得每个key都对应一个存储位置。
散列方法又称为散列函数或者哈希函数。
大多数语言中的字典就是通过散列表的实现的，Swift中也不列外，Swift中字典的key要求遵守Hashable协议。

特性描述

其实散列表就是一个数组，不过具体存储value的位置，是将key带入到特定的“算法”中计算出来的。
上面的特定算法有很多种，如直接定址法，平方取中法、除留余数法，随机数法等等。但是所有的方法都不可避免的，会存在key1，key2两个不同的值，但是通过算法计算后，得到的在数组中的相同的存储位置，这时候就产生了冲突。
避免冲突也和算法一样有很多种，如再散列法、链地址法等，下面接受的实现就是通过链地址法实现的。
总之实现散列表的宗旨就是计算（即算法）要相对简单，同时在数组中的位置分布要相对均匀，尽量做到鱼和熊掌尽可能兼得。

实现

以字典来说，它可以根据key去读取、更新、存储值，根据这些特性来进行实现

//0
struct HashTable<Key: Hashable, Value> {
    //1
    private typealias Element = (key: Key, value: Value)
    private typealias Bukets = [Element]
    //2
    private var buckets: [Bukets]
    private(set) var count = 0
    
    var isEmpty: Bool { return count == 0 }
    //3
    init(_ capacity: Int) {
        assert(capacity > 0, "不能为负值")
        buckets = Array<Bukets>.init(repeating: [], count: capacity)
    }
  //4
    private func index(forKey key: Key) -> Int {
        return abs(key.hashValue) % buckets.count
    }
}

0.定义两个泛型 Key和Value座位键-值的类型，其中Key要继承HashTable

1.定义两种类型，一个元组，一个包含元祖的数组类型

2.定义散列表内存存储数据的数组，这个buckets的类型是[Bukets] ,内部的元素是数组，数组中的元素为元组：
[ [(key: Key, value: Value), (key: Key, value: Value), (key: Key, value: Value)], [(key: Key, value: Value), (key: Key, value: Value)]， [(key: Key, value: Value)] ]

3.通过初始化方法设定内部容量

通过 index方法计算key对应value的下标值，这里用的方法是除留余数法

通过下标来实现曾，删，查的操作

private func value(forKey key: Key) -> Value? {
        let index = self.index(forKey: key)
        for element in buckets[index] {
            if element.key == key {
                return element.value
            }
        }
        return nil
    }
    
    private mutating func upDateValue(value: Value, forKey key: Key) {
        let index = self.index(forKey: key)
        for (i, element) in buckets[index].enumerated() {
            if element.key == key {
                let bucketElement = buckets[index]
                var keyValue = bucketElement[i]
                keyValue.value = value
                return
            }
        }
        //如果不存在该key，则插入新的
        buckets[index].append((key, value))
        count += 1
    }
    
    private mutating func removeValue(forKey key: Key) -> Value? {
        let index = self.index(forKey: key)
        for (i, element) in buckets[index].enumerated() {
            if element.key == key {
                 buckets[index].remove(at: i)
                count -= 1
                return element.value
            }
        }
        return nil
    }
    
    ///通过下标进行增删查的操作
    subscript(key: Key) -> Value? {
        get {
            return value(forKey: key)
        }
        set {
            if let value = newValue {
                upDateValue(value: value, forKey: key)
            } else {
                let _ = removeValue(forKey: key)
            }
        }
    }

以上就是对散列表的简单实现，后面会逐步完善。

Hash Table(散列表)-Swift实现

定义

特性描述

实现

推荐阅读更多精彩内容