[Swift]深入剖析基础--Dictionary&Hash

Author Avatar
与狼同行 11月 27, 2016

本文整理自:http://www.jianshu.com/p/138ccbc75803

Dictionary

我们都知道哈希表不可避免的会产生冲突,有拉链法和线性法来解决冲突。其中Swift就是用线性探测来解决哈希表的冲突问题。

拉链法和线性探测


线性探测 直接使用数组来存储数据。可以想象成一个停车问题。若当前车位已经有车,则你就继续往前开,直到找到下一个为空的车位。

性能比较:对于 线性探测 来说动态调整数组大小是必要的,不然会产生死循环。

拉链法 的删除操作比较方便,直接链表修改地址即可。而 线性探测 删除操作很复杂,而且 线性探测 耗费的内存比拉链法要多。

线性探测是指,如果出现第二个Key的哈希值和第一个Key的哈希值冲突,则会检查第一个Key对应位置的后一个位置是否可用,如果可用则把第二个Key对应的Value放在这里,否则就继续向后寻找。
一个容量为8的字典,它实际上只能存储7个Key-Value对,这是因为字典需要至少一个空位置作为插入和查找过程中的停止标记。我们把这个位置称为“洞”。
举个例子,假设Key1和Key2具有相同的哈希值,它们都存储在字典中。现在我们查找Key3对应的值。Key3的哈希值和前两者相同,但它不存在于字典中。查找时,首先从Key1所在的位置开始比较,因为不匹配所以比较Key2所在的位置,而且从理论上来说只用比较这两个位置即可。如果Key2的后面是一个洞,就表示查找到此为止,否则还得继续向后查找。
在实际内存中,它的布局看上去是这样的:

创建字典时会分配一段连续的内存,其大小很容易计算:

1
size = capacity * (sizeof(Bitmap) + sizeof(Keys) + sizeof(Values))

从逻辑上来看,字典的组成结构如下:

其中每一列称为一个bucket,其中存储了三样东西:位图的值,Key和Value。bucket的概念其实已经有些类似于我们实际使用字典时,Key-Value对的概念了。

bucket中位图的值用于表示这个bucket中的Key和Value是否是已初始化且有效的。如果不是,那么这个bucket就是一个洞。

介绍完以上基本概念后,我们由底层向高层介绍字典的实现原理:

_HashedContainerStorageHeader(结构体)


这个结构体是字典所使用内存的头部,它有三个成员变量:

capacity:字典的容量,表示字典当前最多可以存储多少Key-Value对
count:字典中元素数量,表示字典当前实际存储的Key-Value对的数量
maxLoadFactorInverse:当字典需要扩容时使用到的因子,新的capacity是旧的capacity乘以这个因子。

1
2
3
4
@_transparent
internal var _hashContainerDefaultMaxLoadFactorInverse: Double {
return 1.0 / 0.75
}

这是默认的负载因子。

_NativeDictionaryStorageImpl

这个类是ManagedBuffer<_hashedcontainerstorageheader, uint8="">的子类。

这个类的作用是为字典分配需要使用的内存,并且返回指向位图、Key和Value数组的指针。比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
internal var _values: UnsafeMutablePointer<Value> {
let keysSizeInBytes = _unsafeMultiply(_body.capacity, strideof(Key.self))
let start = UnsafeMutablePointer<UInt8>(_keys) + keysSizeInBytes
return _roundUp(start, toAlignmentOf: Value.self)
}
internal var _keys: UnsafeMutablePointer<Key> {
let bitMapSizeInBytes =
_unsafeMultiply(
_UnsafeBitMap.sizeInWords(forSizeInBits: _body.capacity),
strideof(UInt.self))
let start =
UnsafeMutablePointer<UInt8>(_initializedHashtableEntriesBitMapStorage)
+ bitMapSizeInBytes
return _roundUp(start, toAlignmentOf: Key.self)
}

由于位图、Key和Value数组所在的内存是连续分配的,所以Value数组的指针values_pointer 等于 keys_pointer + capacity * keys_pointer 。

在分配内存的过程中,位图数组中所有的元素值都是0,这就表示所有的bucket都是洞。另外需要强调的一点是,到目前为止(分配字典所用内存)范型Key不必实现Hashable协议。
目前,字典的结构组成示意图如下:

_NativeDictionaryStorage(结构体)

这个结构体将_NativeDictionaryStorageImpl结构体封装为自己的buffer属性,它还提供了一些方法将实际上有三个连续数组组成的字典内存转换成逻辑上的bucket数组。而且,这个结构体将bucket数组中的第一个bucket和最后一个bucket在逻辑上链接起来,从而形成了一个bucket环,也就是说当你到达bucket数组的末尾并且调用next方法时,你又会回到bucket数组的开头。

在进行插入或查找操作时,我们需要算出这个Key对应哪个bucket。由于Key实现了Hashable,所以它一定实现了hashValue方法并返回一个整数值。但这个哈希值可能比字典容量还大,所以我们需要压缩这个哈希值,以确保它属于区间[0, capacity):

1
2
3
4
@warn_unused_result
internal func _bucket(k: Key) -> Int {
return _squeezeHashValue(k.hashValue, 0..<capacity)
}

通过_index和_prev函数,我们可以遍历整个bucket数组,这里虽然使用了溢出运算符,但实际上并不会发生溢出,个人猜测是为了性能优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
internal var _bucketMask: Int {
return capacity &- 1
}
@warn_unused_result
internal func _next(bucket: Int) -> Int {
return (bucket &+ 1) & _bucketMask
}
@warn_unused_result
internal func _prev(bucket: Int) -> Int {
return (bucket &- 1) & _bucketMask
}

字典容量capacity一定可以表示为2的多少次方,因此_bucketMask这个属性如果用二进制表示,则一定全部由1组成。举个例子体验一下,假设capacity = 8:

bucket = 6,调用_next方法,返回值为 7 & 7,也就是7.
bucket = 7,调用_next方法,返回值为 8 & 7,二进制表示为1000 & 0111,因此返回值为0。也就是返回了数组的起始位置。
bucket = 0,调用_prev方法,返回值为 -1 & 7,二进制表示为1…1111 & 0…0111,因此返回值为111,也就是7,回到了数组的结束位置。
在插入一个键值对时,我们首先计算出Key对应哪个bucket,然后调用下面的方法把Key和Value写入到bucket中,同时把位图的值设置为true:

1
2
3
4
5
6
7
8
9
internal func initializeKey(_ k: AnyObject, value v: AnyObject, at i: Int
) {
_sanityCheck(!isInitializedEntry(at: i))
(keys + i).initialize(to: k)
(values + i).initialize(to: v)
initializedEntries[i] = true
_fixLifetime(self)
}

另一个需要重点介绍的函数是_find:

_find函数用于找到Key对应的bucket
需要指定需要指定从哪个bucket开始寻找,因此需要_buckey(key)函数的配合
如果参数key和某个bucket中的Key匹配,则返回这个bucket的位置
如果没有找到,则返回接下来的第一个洞,表示key可以插入到这里
通过位图判断当前bucket是不是一个洞
这种算法被称为线性探测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@inline(__always)
internal func _find(_ key: Key, startBucket: Int)
-> (pos: Index, found: Bool) {
var bucket = startBucket
// The invariant guarantees there's always a hole, so we just loop
// until we find one
while true {
let isHole = !isInitializedEntry(at: bucket)
if isHole {
return (Index(nativeStorage: self, offset: bucket), false)
}
if self.key(at: bucket) == key {
return (Index(nativeStorage: self, offset: bucket), true)
}
bucket = _index(after: bucket)
}
}

一般来说,_squeezeHashValue函数的返回值就是Key对应的bucket的下标,不过需要考虑不同的Key哈希值冲突的情况。
在这种情况下,_find函数会找到下一个可用的洞,以便插入数据。

hashValue优化

_squeezeHashValue函数的本质是对Key的哈希值再次求得哈希值,而一个优秀的哈希函数是提高性能的关键。_squeezeHashValue函数基本上符合要求,不过目前惟一的缺点是哈希变换的种子还是一个占位常量,有兴趣的读者可以阅读完整的函数实现,其中的seed就是一个值为0xff51afd7ed558ccd的常量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func _squeezeHashValue(hashValue: Int, _ resultRange: Range<UInt>) -> UInt {
let mixedHashValue = UInt(bitPattern: _mixInt(hashValue))
let resultCardinality: UInt = resultRange.endIndex - resultRange.startIndex
if _isPowerOf2(resultCardinality) {
return mixedHashValue & (resultCardinality - 1)
}
return resultRange.startIndex + (mixedHashValue % resultCardinality)
}
func _mixUInt64(value: UInt64) -> UInt64 {
// Similar to hash_4to8_bytes but using a seed instead of length.
let seed: UInt64 = _HashingDetail.getExecutionSeed()
let low: UInt64 = value & 0xffff_ffff
let high: UInt64 = value >> 32
return _HashingDetail.hash16Bytes(seed &+ (low << 3), high)
}
static func getExecutionSeed() -> UInt64 {
// FIXME: This needs to be a per-execution seed. This is just a placeholder
// implementation.
let seed: UInt64 = 0xff51afd7ed558ccd
return _HashingDetail.fixedSeedOverride == 0 ? seed : fixedSeedOverride
}
static func hash16Bytes(low: UInt64, _ high: UInt64) -> UInt64 {
// Murmur-inspired hashing.
let mul: UInt64 = 0x9ddfea08eb382d69
var a: UInt64 = (low ^ high) &* mul
a ^= (a >> 47)
var b: UInt64 = (high ^ a) &* mul
b ^= (b >> 47)
b = b &* mul
return b
}

目前,字典的结构总结如下:

_NativeDictionaryStorageOwner(类)

这个类被用于管理字典的引用计数,以支持写时复制(COW)特性。由于Dictionary和DictionaryIndex都会引用实际存储区域,所以引用计数为2。不过写时复制的唯一性检查不考虑由DictionaryIndex导致的引用,所以如果字典通过引用这个类的实例对象来管理引用计数值,问题就很容易处理。

1
2
3
4
/// 这个类用于区分以下两种引用:
/// - `Dictionary` and `NSDictionary`,
/// - `DictionaryIndex`.
/// 这是因为写时复制的唯一性检查只考虑第一种引用

现在,字典的结构变得有些复杂,难以理解了:

_VariantDictionaryStorage (枚举)

这个枚举类型中有两个成员,它们各自具有自己的关联值,分别表示Swift原生的字典和Cocoa的字典:

1
2
case Native(_NativeDictionaryStorageOwner<Key, Value>)
case Cocoa(_CocoaDictionaryStorage)

这个枚举类型的主要功能是:

  1. 根据字典的不同类型(原生 or Cocoa)执行对应的增删改查函数
  2. 如果字典已经满了,则扩容
  3. 更新或初始化Key-Value对:

    1
    2
  4. 如果移除某个Key-Value对,就会在原地留下一个洞。下一次线性查找时有可能会提前停止,为了解决这个问题,我们需要在移除Key-Value对后,移动另一个Key-Value对补上这个洞,源码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    /// - parameter idealBucket: The ideal bucket for the element being deleted.
    /// - parameter offset: The offset of the element that will be deleted.
    /// Requires an initialized entry at offset.
    internal mutating func nativeDeleteImpl(
    nativeStorage: NativeStorage, idealBucket: Int, offset: Int
    ) {
    _sanityCheck(
    nativeStorage.isInitializedEntry(offset), "expected initialized entry")
    // remove the element
    nativeStorage.destroyEntryAt(offset)
    nativeStorage.count -= 1
    // If we've put a hole in a chain of contiguous elements, some
    // element after the hole may belong where the new hole is.
    var hole = offset
    // Find the first bucket in the contiguous chain
    var start = idealBucket
    while nativeStorage.isInitializedEntry(nativeStorage._prev(start)) {
    start = nativeStorage._prev(start)
    }
    // Find the last bucket in the contiguous chain
    var lastInChain = hole
    var b = nativeStorage._next(lastInChain)
    while nativeStorage.isInitializedEntry(b) {
    lastInChain = b
    b = nativeStorage._next(b)
    }
    // Relocate out-of-place elements in the chain, repeating until
    // none are found.
    while hole != lastInChain {
    // Walk backwards from the end of the chain looking for
    // something out-of-place.
    var b = lastInChain
    while b != hole {
    let idealBucket = nativeStorage._bucket(nativeStorage.keyAt(b))
    // Does this element belong between start and hole? We need
    // two separate tests depending on whether [start,hole] wraps
    // around the end of the buffer
    let c0 = idealBucket >= start
    let c1 = idealBucket <= hole
    if start <= hole ? (c0 && c1) : (c0 || c1) {
    break // Found it
    }
    b = nativeStorage._prev(b)
    }
    if b == hole { // No out-of-place elements found; we're done adjusting
    break
    }
    // Move the found element into the hole
    nativeStorage.moveInitializeFrom(nativeStorage, at: b, toEntryAt: hole)
    hole = b
    }
    }

这段代码理解起来可能比较费力,我想举一个例子来说明就比较简单了,假设一开始有8个bucket,bucket中的value就是bucket的下标,最后一个bucket是洞:

1
2
Bucket数组中元素下标: {0, 1, 2, 3, 4, 5, 6, 7(Hole)}
bucket中存储的Value: {0, 1, 2, 3, 4, 5, 6, null}

接下来我们删除第五个bucket,这会在原地留下一个洞:

1
2
Bucket数组中元素下标: {0, 1, 2, 3, 4(Hole), 5, 6, 7(Hole)}
bucket中存储的Value: {0, 1, 2, 3, , 5, 6 }

为了补上这个洞,我们把最后一个bucket中的内容移到这个洞里,现在第五个bucket就不是洞了:

1
2
Bucket数组中元素下标: {0, 1, 2, 3, 4, 5, 6(Hole), 7(Hole)}
bucket中存储的Value: {0, 1, 2, 3, 6, 5, , }

字典的完整结构

Dictionary结构体持有一个_VariantDictionaryStorage类型的枚举,作为自己的成员属性,所以整个字典完整的组成结构如下图所示:

哈希

有两个字典,分别存有 100 条数据和 10000 条数据,如果用一个不存在的 key 去查找数据,在哪个字典中速度更快?

有两个字典,分别存有 100 条数据和 10000 条数据,如果用一个不存在的 key 去查找数据,在哪个字典中速度更快?

在 Redis 中,得益于自动扩容和默认哈希函数,两者查找速度一样快。在 Java 和 Objective-C 中,如果哈希函数不合理,返回值过于集中,会导致大字典更慢。Java 由于存在链表和红黑树互换机制,搜索时间呈对数级增长,而非线性增长。在理想的哈希函数下,无论字典多大,搜索速度都是一样快。

```

概念整理:

  1. 哈希表的存储过程如下:

    根据 key 计算出它的哈希值 h。
    假设箱子的个数为 n,那么这个键值对应该放在第 (h % n) 个箱子中。
    如果该箱子中已经有了键值对,就使用开放寻址法或者拉链法解决冲突。

  1. 负载因子(load factor):它用来衡量哈希表的 空/满 程度,一定程度上也可以体现查询的效率,计算公式为:

    负载因子 = 总键值对数 / 箱子个数
    负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。因此,一般来说,当负载因子大于某个常数(可能是 1,或者 0.75 等)时,哈希表将自动扩容。

哈希表在自动扩容时,一般会创建两倍于原来个数的箱子,因此即使 key 的哈希值不变,对箱子个数取余的结果也会发生改变,因此所有键值对的存放位置都有可能发生改变,这个过程也称为重哈希(rehash)。

哈希表的扩容并不总是能够有效解决负载因子过大的问题。假设所有 key 的哈希值都一样,那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低,但实际存储在每个箱子中的链表长度并不发生改变,因此也就不能提高哈希表的查询性能。

基于以上总结,细心的读者可能会发现哈希表的两个问题:

  1. 如果哈希表中本来箱子就比较多,扩容时需要重新哈希并移动数据,性能影响较大。
  2. 如果哈希函数设计不合理,哈希表在极端情况下会变成线性表,性能极低。
    我们分别通过 Java 和 Redis 的源码来理解以上问题,并看看他们的解决方案。

Java8对哈希的优化策略

JDK 的代码是开源的,可以从这里下载到,我们要找的 HashMap.java 文件的目录在 openjdk/jdk/src/share/classes/java/util/HashMap.java。
在 HashMap 中定义了几个常量:

学过概率论的读者也许知道,理想状态下哈希表的每个箱子中,元素的数量遵守泊松分布:

当负载因子为 0.75 时,上述公式中 λ 约等于 0.5,因此箱子中元素个数和概率的关系如下:

数量 概率
0 0.60653066
1 0.30326533
2 0.07581633
3 0.01263606
4 0.00157952
5 0.00015795
6 0.00001316
7 0.00000094
8 0.00000006

这就是为什么箱子中链表长度超过 8 以后要变成红黑树,因为在正常情况下出现这种现象的几率小到忽略不计。一旦出现,几乎可以认为是哈希函数设计有问题导致的。

Java 对哈希表的设计一定程度上避免了不恰当的哈希函数导致的性能问题,每一个箱子中的链表可以与红黑树切换

Redis对哈希的优化策略

Redis 是一个高效的 key-value 缓存系统,也可以理解为基于键值对的数据库。它对哈希表的设计有非常多值得学习的地方,在不影响源代码逻辑的前提下我会尽可能简化,突出重点。

  1. 头插法:
    新插入的键值对会放在箱子中链表的头部,而不是在尾部继续插入。这个细节上的改动至少带来两个好处:
    找到链表尾部的时间复杂度是 O(n),或者需要使用额外的内存地址来保存链表尾部的位置。头插法可以节省插入耗时。
    对于一个数据库系统来说,最新插入的数据往往更有可能频繁的被获取。头插法可以节省查找耗时。

  2. 增量式扩容:
    所谓的增量式扩容是指,当需要重哈希时,每次只迁移一个箱子里的链表,这样扩容时不会出现性能的大幅度下降。

  3. 默认哈希函数
    与 Java 不同的是,Redis 提供了 void * 类型 key 的哈希函数,也就是通过任何类型的 key 的指针都可以求出哈希值。具体算法定义在 dictGenHashFunction 函数中,由于代码过长,而且都是一些位运算,就不展示了。

它的实现原理是根据指针地址和这一块内存的长度,获取内存中的值,并且放入到一个数组当中,可见这个数组仅由 0 和 1 构成。然后再对这些数字做哈希运算。因此即使两个指针指向的地址不同,但只要其中内容相同,就可以得到相同的哈希值。

Objective-C 的实现和 Java 比较类似,当我们需要重写 isEqual() 方法时,还需要重写 hash 方法。这两种语言并没有提供一个通用的、默认的哈希函数,主要是考虑到 isEqual() 方法可能会被重写,两个内存数据不同的对象可能在语义上被认为是相同的。如果使用默认的哈希函数就会得到不同的哈希值,这两个对象就会同时被添加到 NSSet 集合中,这可能违背我们的期望结果。

根据我的了解,Redis 并不支持重写哈希方法,难道 Redis 就没有考虑到这个问题么?实际上还要从 Redis 的定位说起。由于它是一个高效的,Key-Value 存储系统,它的 key 并不会是一个对象,而是一个用来唯一确定对象的标记。

一般情况下,如果要存储某个用户的信息,key 的值可能是这样: user:100001。Redis 只关心 key 的内存中的数据,因此只要是可以用二进制表示的内容都可以作为 key,比如一张图片。Redis 支持的数据结构包括哈希表和集合(Set),但是其中的数据类型只能是字符串。因此 Redis 并不存在对象等同性的考虑,也就可以提供默认的哈希函数了。

Redis、Java、Objective-C 之间的异同再次证明了一点:

没有完美的架构,只有满足需求的架构。