转自：码农阿宇

cnblogs.com/CoderAyu/p/10360608.html

从一道亲身经历的面试题说起

半年前 , 我参加我现在所在公司的面试 , 面试官给了一道题 , 说有一个 Y 形的链表 , 知道起始节点 , 找出交叉节点 .

为了便于描述 , 我把上面的那条线路称为线路 1, 下面的称为线路 2.

思路 1

先判断线路 1 的第一个节点的下级节点是否是线路 2 的第一个节点 , 如果不是 , 再判断是不是线路 2 的第二个 , 如果也不是 , 判断是不是第三个节点 , 一直到最后一个 .

如果第一轮没找到 , 再按以上思路处理线路一的第二个节点 , 第三个 , 第四个 ... 找到为止 .

时间复杂度 n2, 相信如果我用的是这种方法 , 可肯定被 Pass 了 .

思路 2

首先 , 我遍历线路 2 的所有节点 , 把节点的索引作为 key, 下级节点索引作为 value 存入字典中 .

然后 , 遍历线路 1 中节点 , 判断字典中是否包含该节点的下级节点索引的 key, 即 dic.ContainsKey((node.next)
, 如果包含 , 那么该下级节点就是交叉节点了 .

时间复杂度是 n.

那么问题来了 , 面试官问我了 , 为什么时间复杂度 n 呢 ? 你有没有研究过字典的 ContainsKey 这个方法呢 ? 难道它不是通过遍历内部元素来判断 Key 是否存在的呢 ? 如果是的话 , 那时间复杂度还是 n2 才是呀 ?

我当时支支吾吾 , 确实不明白字典的工作原理 , 厚着面皮说
" 不是的 , 它是通过哈希表直接拿出来的 , 不用遍历 ", 面试官这边是敷衍过去了 , 但在我心里却留下了一个谜 , 已经入职半年多了 , 欠下的技术债是时候还了 .

带着问题来阅读

在看这篇文章前 , 不知道您使用字典的时候是否有过这样的疑问 .

1. 字典为什么能无限地 Add 呢 ?

2. 从字典中取 Item 速度非常快 , 为什么呢 ?

3. 初始化字典可以指定字典容量 , 这是否多余呢 ?

4. 字典的桶 buckets 长度为素数 , 为什么呢 ?

不管您以前有没有在心里问过自己这些问题 , 也不管您是否已经有了自己得答案 , 都让我们带着这几个问题接着往下走 .

从哈希函数说起

什么是哈希函数 ?

哈希函数又称散列函数 , 是一种从任何一种数据中创建小的数字“指纹”的方法。

下面 , 我们看看 JDK 中 Sting.GetHashCode() 方法 .

[code]

 public int hashCode() { int h = hash; //hash default value : 0 if (h == 0 && value.length > 0) { //value : char storage char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } 

[/code]

可以看到 , 无论多长的字符串 , 最终都会返回一个 int 值 , 当哈希函数确定的情况下 , 任何一个字符串的哈希值都是唯一且确定的 .

当然 , 这里只是找了一种最简单的字符数哈希值求法 , 理论上只要能把一个对象转换成唯一且确定值的函数 , 我们都可以把它称之为哈希函数 .

这是哈希函数的示意图 .

所以 , 一个对象的哈希值是确定且唯一的 !.

字典

如何把哈希值和在集合中我们要的数据的地址关联起来呢 ? 解开这个疑惑前我来看看一个这样不怎么恰当的例子 :

有一天 , 我不小心干了什么坏事 , 警察叔叔没有逮到我本人 , 但是他知道是一个叫阿宇的干的 , 他要找我肯定先去我家 , 他怎么知道我家的地址呢 ? 他不可能在全中国的家庭一个个去遍历 , 敲门 , 问阿宇是你们家的熊孩子吗 ?

正常应该是通过我的名字 , 找到我的身份证号码 , 然后我的身份证上登记着我的家庭地址 (我们假设一个名字只能找到一张身份证).

阿宇-----> 身份证 (身份证号码 , 家庭住址)------> 我家

我们就可以把由阿宇找到身份证号码的过程 , 理解为哈希函数 , 身份证存储着我的号码的同时 , 也存储着我家的地址 , 身份证这个角色在字典中就是
bucket, 它起一个桥梁作用 , 当有人要找阿宇家在哪时 , 直接问它 , 准备错的 , 字典中 ,bucket 存储着数据的内存地址 (索引), 我们要知道 key 对应的数据的内存地址 , 问 buckets 要就对了 .

key--->bucket 的过程 ~= 阿宇-----> 身份证 的过程 .

警察叔叔通过家庭住址找到了我家之后 , 我家除了住我 , 还住着我爸 , 我妈 , 他敲门的时候 , 是我爸开门 , 于是问我爸爸 , 阿宇在哪 , 我爸不知道 , 我爸便问我妈 , 儿子在哪 ? 我妈告诉警察叔叔 , 我在书房呢 . 很好 , 警察叔叔就这样把我给逮住了 .

字典也是这样 , 因为 key 的哈希值范围很大的 , 我们不可能声明一个这么大的数组作为 buckets, 这样就太浪费了 , 我们做法时 HashCode%BucketSize 作为 bucket 的索引 .

假设 Bucket 的长度 3, 那么当 key1 的 HashCode 为 2 时 , 它数据地址就问 buckets2 要 , 当 key2 的 HashCode 为 5 时 , 它的数据地址也是问 buckets2 要的 .

这就导致同一个 bucket 可能有多个 key 对应 , 即下图中的 Johon Smith 和 Sandra
Dee, 但是 bucket 只能记录一个内存地址 (索引), 也就是警察叔叔通过家庭地址找到我家时 , 正常来说 , 只有一个人过来开门 , 那么 , 如何找到也在这个家里的我的呢 ? 我爸记录这我妈在厨房 , 我妈记录着我在书房 , 就这样 , 我就被揪出来了 , 我爸 , 我妈 , 我
就是字典中的一个 entry.

果有一天 , 我妈妈老来得子又生了一个小宝宝 , 怎么办呢 ? 很简单 , 我妈记录小宝宝的位置 , 那么我的只能巴结小宝宝 , 让小宝宝来记录我的位置了 .

既然大的原理明白了 , 是不是要看看源码 , 来研究研究代码中字典怎么实现的呢 ?

DictionaryMini

上次在苏州参加苏州微软技术俱乐部成立大会时 , 有幸参加了蒋金楠 老师讲的 Asp .net
core 框架解密 , 蒋老师有句话让我印象很深刻 ," 学好一门技术的最好的方法 , 就是模仿它的样子 , 自己造一个出来 " 于是他弄了个 Asp .net core
mini, 所以我效仿蒋老师 , 弄了个 DictionaryMini

源代码放在 Github 仓库 , 有兴趣的可以看看 :

https://github.com/liuzhenyulive/DictionaryMini

我觉得字典这几个方面值得了解一下 :

1. 数据存储的最小单元的数据结构

2. 字典的初始化

3. 添加新元素

4. 字典的扩容

5. 移除元素

字典中还有其他功能 , 但我相信 , 只要弄明白的这几个方面的工作原理 , 我们也就恰中肯綮 , 他么问题也就迎刃而解了 .

数据存储的最小单元 (Entry) 的数据结构

[code]

 private struct Entry { public int HashCode; public int Next; public TKey Key; public TValue Value; } 

[/code]

一个 Entry 包括该 key 的 HashCode, 以及下个 Entry 的索引 Next, 该键值对的 Key 以及数据 Vaule.

字典初始化

[code]

 private void Initialize(int capacity) { int size = HashHelpersMini.GetPrime(capacity); _buckets = new int[size]; for (int i = 0; i <_buckets.Length; i++) { _buckets[i] = -1; } _entries = new Entry[size]; _freeList = -1; } 

[/code]

字典初始化时 , 首先要创建 int 数组 , 分别作为 buckets 和 entries, 其中 buckets 的 index 是 key 的哈希值 %size, 它的 value 是数据在 entries 中的 index, 我们要取的数据就存在 entries 中 . 当某一个 bucket 没有指向任何 entry 时 , 它的 value 为-1

另外 , 很有意思得一点 ,buckets 的数组长度是多少呢 ? 这个我研究了挺久 , 发现取的是大于 capacity 的最小质数 .

添加新元素

[code]

 private void Insert(TKey key, TValue value, bool add) { if (key == null) { throw new ArgumentNullException(); } // 如果 buckets 为空 , 则重新初始化字典 . if (_buckets == null) Initialize(0); // 获取传入 key 的 哈希值 var hashCode =_comparer.GetHashCode(key); // 把 hashCode%size 的值作为目标 Bucket 的 Index. var targetBucket = hashCode %_buckets.Length; // 遍历判断传入的 key 对应的值是否已经添加字典中 for (int i =_buckets[targetBucket]; i > 0; i =_entries[i].Next) { if (_entries[i].HashCode == hashCode &&_comparer.Equals(_entries[i].Key, key)) { // 当 add 为 true 时 , 直接抛出异常 , 告诉给定的值已存在在字典中 . if (add) { throw new Exception(" 给定的关键字已存在 !"); } // 当 add 为 false 时 , 重新赋值并退出 . _entries[i].Value = value; return; } } // 表示本次存储数据的数据在 Entries 中的索引 int index; // 当有数据被 Remove 时 ,freeCount 会加 1 if (_freeCount > 0) { //freeList 为上一个移除数据的 Entries 的索引 , 这样能尽量地让连续的 Entries 都利用起来 . index =_freeList; _freeList =_entries[index].Next; _freeCount--; } else { // 当已使用的 Entry 的数据等于 Entries 的长度时 , 说明字典里的数据已经存满了 , 需要对字典进行扩容 ,Resize. if (_count ==_entries.Length) { Resize(); targetBucket = hashCode %_buckets.Length; } // 默认取未使用的第一个 index =_count; _count++; } // 对 Entries 进行赋值 _entries[index].HashCode = hashCode; _entries[index].Next =_buckets[targetBucket]; _entries[index].Key = key; _entries[index].Value = value; // 用 buckets 来登记数据在 Entries 中的索引 . _buckets[targetBucket] = index; } 

[/code]

字典的扩容

[code]

 private void Resize() { // 获取大于当前 size 的最小质数 Resize(HashHelpersMini.GetPrime(_count), false); } private void Resize(int newSize, bool foreNewHashCodes) { var newBuckets = new int[newSize]; // 把所有 buckets 设置-1 for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1; var newEntries = new Entry[newSize]; // 把旧的的 Enties 中的数据拷贝到新的 Entires 数组中 . Array.(_entries, 0, newEntries, 0,_count); if (foreNewHashCodes) { for (int i = 0; i <_count; i++) { if (newEntries[i].HashCode != -1) { newEntries[i].HashCode =_comparer.GetHashCode(newEntries[i].Key); } } } // 重新对新的 bucket 赋值 . for (int i = 0; i <_count; i++) { if (newEntries[i].HashCode > 0) { int bucket = newEntries[i].HashCode % newSize; newEntries[i].Next = newBuckets[bucket]; newBuckets[bucket] = i; } } _buckets = newBuckets; _entries = newEntries; } 

[/code]

移除元素

[code]

 // 通过 key 移除指定的 item public bool Remove(TKey key) { if (key == null) throw new Exception(); if (_buckets != null) { // 获取该 key 的 HashCode int hashCode =_comparer.GetHashCode(key); // 获取 bucket 的索引 int bucket = hashCode %_buckets.Length; int last = -1; for (int i =_buckets[bucket]; i >= 0; last = i, i =_entries[i].Next) { if (_entries[i].HashCode == hashCode &&_comparer.Equals(_entries[i].Key, key)) { if (last < 0) { _buckets[bucket] =_entries[i].Next; } else { _entries[last].Next =_entries[i].Next; } // 把要移除的元素置空 . _entries[i].HashCode = -1; _entries[i].Next =_freeList; _entries[i].Key = default(TKey); _entries[i].Value = default(TValue); // 把该释放的索引记录在 freeList 中 _freeList = i; // 把空 Entry 的数量加 1 _freeCount++; return true; } } } return false; } 

[/code]

我对 .Net 中的 Dictionary 的源码进行了精简 , 做了一个 DictionaryMini, 有兴趣的可以到我的 github 查看相关代码 .

https://github.com/liuzhenyulive/DictionaryMini

答疑时间

字典为什么能无限地 Add 呢

向 Dictionary 中添加元素时 , 会有一步进行判断字典是否满了 , 如果满了 , 会用 Resize 对字典进行自动地扩容 , 所以字典不会向数组那样有固定的容量 .

为什么从字典中取数据这么快

Key-->HashCode-->HashCode%Size-->Bucket Index-->Bucket-->Entry Index-->Value

整个过程都没有通过遍历来查找数据 , 一步到下一步的目的性时非常明确的 , 所以取数据的过程非常快 .

初始化字典可以指定字典容量 , 这是否多余呢

前面说过 , 当向字典中插入数据时 , 如果字典已满 , 会自动地给字典 Resize 扩容 .

扩容的标准时会把大于当前前容量的最小质数作为当前字典的容量 , 比如 , 当我们的字典最终存储的元素为 15 个时 , 会有这样的一个过程 .

new Dictionary()------------------->size:3

字典添加低 3 个元素---->Resize--->size:7

字典添加低 7 个元素---->Resize--->size:11

字典添加低 11 个元素--->Resize--->size:23

可以看到一共进行了三次次 Resize, 如果我们预先知道最终字典要存储 15 个元素 , 那么我们可以用 new Dictionary(15) 来创建一个字典 .

new Dictionary(15)---------->size:23

这样就不需要进行 Resize 了 , 可以想象 , 每次 Resize 都是消耗一定的时间资源的 , 需要把 OldEnties to NewEntries
所以我们在创建字典时 , 如果知道字典的中要存储的字典的元素个数 , 在创建字典时 , 就传入 capacity, 免去了中间的 Resize 进行扩容 .

Tips:

即使指定字典容量 capacity, 后期如果添加的元素超过这个数量 , 字典也是会自动扩容的 .

为什么字典的桶 buckets 长度为素数

我们假设有这样的一系列 keys, 他们的分布范围时 K={ 0, 1,..., 100
}, 又假设某一个 buckets 的长度 m=12, 因为 3 是 12 的一个因子 , 当 key 时 3 的倍数时 , 那么 targetBucket 也将会是 3 的倍数 .

[code]

 Keys {0,12,24,36,...} TargetBucket 将会是 0. Keys {3,15,27,39,...} TargetBucket 将会是 3. Keys {6,18,30,42,...} TargetBucket 将会是 6. Keys {9,21,33,45,...} TargetBucket 将会是 9. 

[/code]

如果 Key 的值是均匀分布的 (K 中的每一个 Key 中出现的可能性相同), 那么 Buckets 的 Length 就没有那么重要了 , 但是如果 Key 不是均匀分布呢 ?

想象一下 , 如果 Key 在 3 的倍数时出现的可能性特别大 , 其他的基本不出现 ,TargetBucket 那些不是 3 的倍数的索引就基本不会存储什么数据了 , 这样就可能有 2/3 的 Bucket 空着 , 数据大量第聚集在 0,3,6,9 中 .

这种情况其实时很常见的。
例如，又一种场景，您根据对象存储在内存中的位置来跟踪对象 , 如果你的计算机的字节大小是 4，而且你的 Buckets 的长度也为 4, 那么所有的内存地址都会时 4 的倍数 , 也就是说 key 都是 4 的倍数 , 它的 HashCode 也将会时 4 的倍数 , 导致所有的数据都会存储在 TargetBucket=0(Key%4=0) 的 bucket 中 , 而剩下的 3/4 的 Buckets 都是空的 .
这样数据分布就非常不均匀了 .

K 中的每一个 key 如果与 Buckets 的长度 m 有公因子 , 那么该数据就会存储在这个公因子的倍数为索引的 bucket 中 . 为了让数据尽可能地均匀地分布在 Buckets 中 , 我们要尽量减少 m 和 K 中的 key 的有公因子出现的可能性 . 那么 , 把 Bucket 的长度设为质数就是最佳选择了 , 因为质数的因子时最少的 . 这就是为什么每次利用 Resize 给字典扩容时会取大于当前 size 的最小质数的原因 .

确实 , 这一块可能有点难以理解 , 我花了好几天才研究明白 , 如果小伙伴们没有看懂建议看看这里 .

https://cs.stackexchange.com/questions/11029/why-is-it-best-to-use-a-prime-number-as-a-mod-in-a-hashing-function/64191#64191

最后 , 感谢大家耐着性子把这篇文章看完 , 欢迎 fork DictionaryMini 进行进一步的研究 , 谢谢大家的支持 .

https://github.com/liuzhenyulive/DictionaryMini