_UnsafeBitset

是一个固定大小的 bitmap，用来确定指定位置是否有元素存在。
HashTable

具体的 hash 碰撞算法在HashTable里实现，目前使用的是简单的开放地址法，使用算法是Linear probing。
HashTable 的属性
其实只有若干个 UInt，每一位用来表示状态，指定位置有没有被占用。
@usableFromInline
internal var words: UnsafeMutablePointer<Word>
算法相关
maxLoadFactor
/// The inverse of the maximum hash table load factor.
private static var maxLoadFactor: Double {
@inline(__always) get { return 3 / 4 }
}
寻找下一个可用的位置
@inlinable
internal func nextHole(atOrAfter bucket: Bucket) -> Bucket {
_internalInvariant(isValid(bucket))
// Note that if we have only a single partial word, its out-of-bounds bits
// are guaranteed to be all set, so the formula below gives correct results.
var word = bucket.word
if let bit =
words[word]
.complement
.subtracting(elementsBelow: bucket.bit)
.minimum {
return Bucket(word: word, bit: bit)
}
var wrap = false
while true {
word &+= 1
if word == wordCount {
_precondition(!wrap, "Hash table has no holes")
wrap = true
word = 0
}
if let bit = words[word].complement.minimum {
return Bucket(word: word, bit: bit)
}
}
}
根据 hash 值确定位置
其实就是取hash值的后几位internal func idealBucket(forHashValue hashValue: Int) -> Bucket {
return Bucket(offset: hashValue & bucketMask)
}
Delegate
@usableFromInline
internal protocol _HashTableDelegate {
func hashValue(at bucket: _HashTable.Bucket) -> Int
func moveEntry(from source: _HashTable.Bucket, to target: _HashTable.Bucket)
}
_HashTable 只是实现了 hash 冲突，计算 hash 值、移动元素，都让外部实现。在删除元素时会用到。