定义
- 散列表是一种通过关键字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)
}
}
}
以上就是对散列表的简单实现，后面会逐步完善。
