了解实际开发中 Hashtable 的特性原理

今天又重新整理了一下和集合类型相关的3篇文章，温故而知新。

 

 

 

 

    Hashtable 是现代大多数程序员居家旅行, 不可不备的利器. 如 ASP.NET 程序员天天要打交道的 Application Items, Cache Items 均由 Hashtable 实现. 日常存储配置参数, 数据列, 我们也会用到 Hashtable 或是基于其的结构如 NameValueCollection 等等, .NET 2.0 推出后更增加了一个 System.Collections.Generic.Dictionary, 用法乍一看和 Hashtable 差不多, 甚至还有泛型的优势. 那么是否能说 Dictionary 将会取代 Hashtable?  Hashtable 是如何实现的? 究竟适用于哪些场合? 有何优劣值得玩味之处? Microsoft 官方文档交待得不甚明确. 我们不妨自己来进行一些初步研究. 同时也结合 Java 和 PHP 中的实现做一些比较.

 

 

    从狭义上来看, Hashtable 可以是一种具体类型名称, 比如 .NET 中的 System.Collections.Hashtable 类, 或是 JAVA 中的 java.util.Hashtable 类. 从广义上来看, 她指的是一种数据结构, 即哈希表, 她牵涉了多种具体类型, 像 HashMap, 文章开头提到的 Dictionary 等等虽然称谓五花八门, 都属于哈希表的范畴. 下文中将出现的名词 Hashtable, 除非特别说明, 也是指广义上的哈希表.

 

    哈希表的原始定义和基本原理各种数据结构教程上都有阐述. 简而言之, 哈希表之所以能够实现根据关键字 (典型的例子是一个字符串键值) 来获取记录,  是因为她在内部建立了记录存储位置 - 即内部数组中的索引号和关键字的一套对应关系 f, 因而在查找时, 只需根据这个映射关系 f 找到给定键值 K 对应的数 f(K), 就可直接从数组中取得目的数据 Hashtable[K] = Hashtable.InternalArray[f(K)], 而不必对数组进行遍历和比较. 这个对应关系 f 我们称为哈希函数.

 

    哈希函数 f 的两个重要特点:
[1] 哈希函数可以自定义, 只要使得整数 f(K) 的范围不超出哈希表内部存储数组的上下界即可.
[2] K 的取法有任意种, 但 f(K) 只能固定在一个范围, 因此不同的关键字可能对应了相同的哈希值, 形成了冲突.

 

    需要注意的是哈希函数的运算和冲突的处理都需要系统开销, 尤其后者代价不菲. 因此产生了两个关键问题: 如何设计函数 f 的算法, 以及如何处理冲突, 才能使得哈希表更加高效.

 

    不同语言, 不同运行环境的解决方案都有所不同, 思路上甚至差别很大. 比如 .NET 的 System.Collections.Hashtable 和 Java 的 java.util.Hashtable 虽然称呼完全一样, 但内部算法是不尽相同的, 应此也产生了使用性能的差异.

 

    这里我们选择几个常见的实例来深入分析:
[1] .NET 2.0, System.Collections.Hashtable
[2] .NET 2.0, System.Collections.Generic.Dictionary<K, V>
[3] Java, java.util.HashMap (java.util.Hashtable 的轻量级实现)
[4] PHP5, PHP 是弱类型语言, Hashtable 对编程者是透明的, 在后台运行时实现.

注: 以上 .NET 源代码来自 Reflector 反编译, Java 源代码参见 jdk, PHP 源代码参见 PHP sdk. 同时为便于说明, 下文采用了部分伪代码.

.NET 中的 System.Collecitons.Hashtable (以下简称 Hashtable) 是一种忠于传统的实现, 很有代表风格. 各类数据结构的教科书上一般就是采用类似的原理作为开篇教学. (当然书中的要简单, 原始得多, 离现实还有一定差距)

 

    Hashtable 中的实际数据都存储在一个内部 Array 中 (当然和普通数组一样, 有固定容量, 上下标, 以数字索引存取), 当用户希望取得 Hashtable[K] 值的时候, Hashtable 进行如下处理:

[1] 为了保证 f(K) 的取值范围在  0 <= f(K) < Array.Length, 函数 f 的关键步骤是取模运算, 算得实际数据存储位置为 f(K) = HashOf(K) % Array.Length, 至于这个 HashOf(K) 怎么算出来的, 简单举例来说她可以取关键字的 ASCII 码根据一定规则运算得到.

 

[2] 如果发生多个 K 值的哈希值重复, 即 f(K1) = f(K2), 而 f(K1) 位置已经有数据占用了, Hashtable 采用的是 "开放定址法" 处理冲突, 具体行为是把 HashOf(K2) % Array.Length 改为 (HashOf(K2) + d(K2)) % Array.Length , 得出另外一个位置来存储关键字 K2 所对应的数据, d 是一个增量函数. 如果仍然冲突, 则再次进行增量, 依此循环直到找到一个 Array 中的空位为止. 将来查找 K2 的时候先搜索 HashOf(K2) 一档, 发现不是 K2, 那么增量 d(K2) 继续搜索, 直到找到为止. 连续冲突次数越多, 搜索次数也越多, 效率越低.

 

 

[3] 当插入数据量达到 Hashtable 容量上限时, 对内部 Array 进行扩容 (重新 new  一个更大的数组, 然后把数据 copy 过去), 不仅如此, 由于 Array.Length 发生了变化, 扩容后要对所有现存数据重新计算 f(K). 所以说扩容是个耗能比较惊人的内部操作. Hashtable 之所以写入效率仅为读取效率的 1/10 数量级, 频繁的扩容是一个因素.

 

    f(K) 的取法是哈希表的关键所在, 从根本上决定了该哈希表的许多重要特征, 例如 .NET 中 System.Collections.Hashtable 的哈希函数 f 其算法决定了这样一些方面:

[1] 数组容量 Array.Length 越大, 冲突的机会越小. 由于 f(K) 的取值范围等于 Array.Length, 因此随着 Array.Length 的增长, f(K) 的值也更加多样性, 不容易重复.

 

[2] 数组容量 Array.Length 期望是一个 "比较大的质数", 这样 f(K) = HashOf(K) % Array.Length 取模运算之后得出的数冲突机会较小. 想象一个极端例子, 假设 Array.Length = 2, 则只要 HashOf(K) 是偶数, f(k) 都为 0. 所以说哈希表的实际容量一般都是有规律的, 和数组不一样, 不能任意设置.

 

[3] 随着插入的数据项逐渐增多, Hashtable 内部数组剩余的空位也越来越少, 下一次冲突的可能性也越来越多严重影响效率. 因此不能等到数组全部塞满后才进行扩容处理. 在 .NET 中, 当插入数据个数和数组容量之比为 0.72 时,  就开始扩容. 这个 0.72 称为装填因子 - Load Factor. 这是一个要求苛刻的数字, 某些时刻将装填因子增减 0.01, 可能你的 Hashtable 存取效率就提高或降低了 50%, 其原因是装填因子决定 Array.Length, Array.Length 影响 f(K) 的冲突几率, 进而影响了性能. 0.72 是 Microsoft 经过长期实验得出的一个比较平衡的值. (取什么值合适和 f(K) 的算法也有关, 0.72 不一定适合其他结构的哈希表)

 

[4] Hashtable 的初始容量 Array.Length 至少为 11, 再次扩容的容量至少为 "不小于 2 倍于当前容量的一个质数". 这里举一个例子, 方便大家看看 Hashtable 是多么浪费空间.

 

    假设以默认方式初始化一个 Hashtable, 依次插入 8 个值,  由于 8 / 0.72 > 11, 因此  Hashtable 自动扩容, 新的容量为不小于 11 * 2 的质数, 即 23. 所以, 实际仅有 8 个人吃饭, 却不得不安排一桌 23 个座儿的酒席, 十分奢侈. 避免如此铺张的途径是在初始化 Hashtable 时用带参构造方式直接指定 capacity 为 17, 但即便这样仍浪费了 9 个空间.

 

    有心的读者经过计算, 可能会问为什么不是指定初始容量为 13, 13 是质数啊, 13 * 0.72 > 8 啊. 确实理想情况是这样, 但实际上由于动态计算并判断一个数是否质数需要大量时间, 故 .NET Hashtable 中的 capacity 值是内部预设的一个数列, 只能为 3, 7, 11, 17, 23... 所以十分遗憾. (注: 只有当 Array.Length > 0x6DDA89 时动态计算扩容容量, 正常情况下我们不会存如此多的数据进去)

 

    .NET 的 Hashtable 就是以这种方式来减少冲突, 以牺牲空间为代价换取读写速度. 假设你在实际开发中对内存空间要求很敏感, 譬如开发 ASP.NET 超大型 B/S 网站时, 就十分有必要检讨使用 Hashtable 的场景需求, 有的时候能否换个方式, 采取自定义 struct, 或者数组来高效实现呢?

 

    下面会说到 Java 和 PHP 的基本哈希表实现.

 

    上面谈到 .NET 的 Hashtable 属于比较传统的算法. 并籍此复习了哈希表这种数据结构的经典原理. 下面我们来看看 Java 和 PHP 中又是如何实现 Hashtable 的. 之所以把 Java 和 PHP 的场景结合一起, 是因为他们俩的处理方式非常相似. 论述将以 java.util.HashMap 为主, 该原理同样也适于 PHP. HashMap 是 java.util.Hashtable 的轻量级实现, 且允许 NULL 作为关键字.

 

    通过前文, 我们已知由于 .NET Hashtable 哈希函数 f(K) 的取模运算特征决定了其容量大小必然是某个质数 (若不明白请回顾第一篇). 而 Java HashMap 则恰恰相对, 她们要求哈希表的容量是一个偶数, 且为 2 的 N 次幂. 即 Array.Length = 2, 4, 8, 16, 32, 64... (转化为二进制恰好为 1111 ... 110 形式). 这是由于 Java HashMap 的哈希算法核心为与 (&) 运算, f(K) = HashOf(K) & (Array.Length - 1), 运算时 HashOf(K) 的高位同 0 相与被丢弃, 低位同 1 相与被保留, 以次保证 0 <= f(K) < Array.Length.

 

    HashMap 的冲突处理方式也区别于 .NET Hashtable 的开放定址法, 为 "链地址法". 当后插入的 K2, K3, K4 等与先插入的 K1 位置冲突时, 在 K1 位置建立一个链表, 把 K2, K3, K4... 另存至链表中, 即一个位置可以对应 "一串" 数据. 搜索 K2, K3, K4 的时候先查找 f(K1) 位置本身, 若不符则顺序遍历链表. 这样处理的好处是不会产生如同 .NET Hashtable 中开放定址法的二次聚集现象 (在探测空位时产生连续冲突).

 

    HashMap 也存在一个 Load Factor, 其值为 0.75. 我们看到 HashMap 的冲突处理方式不会产生二次聚集, 因此装填因子可以适当放大一些. 其初始默认容量为 16, 当实际装入数据和容量之比超过 0.75 时开始自动扩容, 新的容量为原始容量的 2 倍 (32, 64, 128... 依此类推). 乘 2 运算通过左移直接实现, 没有 .NET 那般运算判断质数的困扰.

 

    PHP 的 Hashtable 构造和 Java HashMap 基本相通, 只是 Load Factor 值为 1.

 

    从理论上来说, .NET Hashtable 的平均搜索步长约为 -ln(1-x)/x, 而 Java HashMap 的平均搜索步长约为  1 + x/2, 这里 x 为实际装入数据个数和容量之比, 由此看出一个哈希表的平均查找长度为 x 的函数, 且 0 <= x < Load Factor, 而非插入数据个数 N 的函数, 因此她的查找复杂度为 O(1).

 

    从实际运算来看, 性能评估是比较复杂的事情, 不仅仅取决于理论搜索步长, 还取决于实际 Load Factor 的取值, HashOf(K) 的效率, Resize() 的效率, 探测数组和拆链装链的效率, 甚至函数的压参传值这种微小开销累积起来也对总体性能有可观的影响. 在 C# 中仿照 Java HashMap 简单写了一个采用链地址法的哈希表, 初步测试显示其与 .NET 原始的 Hashtable 相比读取速度较快但写入较慢, 互有胜负. 考虑到 Hashtable 还有线程安全处理, 慢一点可以理解, 情况要比想象的好.

 

    下面我们从 Java 回到 .NET, 介绍一下 2.0 新推出的 System.Collections.Generic.Dictionary<K, V> 类型 (以下简称 Dictionary).

 

    Dictionary 的用法与 Hashtable 差不多, f(K) 也采用相同的取模算法, 但其余内部结构无论同 Hashtable 还是 HashMap 都有很大区别. 体现在:
[1] Dictionary 没有 Load Factor 变量, 或可理解为 Load Factor = 1, 插入数据可以最大限度填满容量空间.
[2] 大体上, Dictionary 内的元素有按照先后插入顺序排列的特性. 区别于 Hashtable 及 HashMap 的离散型.

 

    Dictionary 内部拥有两列数组, 姑且成为 "状态串" 和 "数据串", 数据串按顺序接受插入的数据并加以封装 (封装了一个 next 指针, 方便今后装链), 状态串以 f(K) 为索引, 存放 f(K) 到 K 在数据串内的位置映射. 查找时先访问状态串找 f(K), 然后根据映射关系找到数据串中的实际数据. 当有多个 f(K) 重复时, 状态串里面保留第一个 f(K), 在数据串内对冲突的数据建立链关系.

 

 

    由图我们可以看出, 数据串忠实按照 K1, K2, K3 ... 的插入顺序排列, 直至排满数据串, 这个过程中自然不会发生冲突, 冲突只出现在状态串中, 同时, 发生冲突时并不需探测空位和挪动数据本身, 只需将冲突的数据链在一起即可.

 

    Dictionary 默认初始大小为 3, 扩容方式和 Hashtable 一样, 为不小于当前容量的 2 倍的一个质数. 在速度方面, Dictionary 读取快于 Hashtable, 但不如用 C# 自写的链地址法的哈希表, 写入要慢于 Hashtable, 但快于链地址法的哈希表. 考虑到 Dictionary 隐含的装填因子为  1, 可以最大限度利用空间, 是一种以速度换空间的做法, 这个结果是可以接受的.

 

    由于 Hashtable 和 Dictionary 同时存在, 在使用场景上必然存在选择性, 并不任何时刻都能相互替代.
[1] 单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分.

[2] 多线程程序中推荐使用 Hashtable, 默认的 Hashtable 允许单线程写入, 多线程读取, 对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型. 而 Dictionary 非线程安全, 必须人为使用 lock 语句进行保护, 效率大减.

[3] Dictionary 有按插入顺序排列数据的特性 (注: 但当调用 Remove() 删除过节点后顺序被打乱), 因此在需要体现顺序的情境中使用 Dictionary 能获得一定方便.

 

    以上分别谈到了  Hashtable, HashMap 和 Dictionary 三种类型, 介绍告一段落, 下面增加一些不成熟的观点:

[1] 三种哈希表均允许任意 object 做关键字, 但实际使用中我们一般只用 string 做键值, 对 string 做 HashOf(string) 处理比较单纯, 速度较快, 而对 object 取 HashOf(object) 则情况复杂. 若想进一步提高速度, 可以考虑自定义一个只允许 string 作为关键字的哈希表.

 

[2] Java HashMap 由于 f(K) 取与运算的特性, 每次扩容必须是 2 倍, 没有价钱可讲. 但 .NET Hashtable 和  Dictionary 的容量理论上只要求是质数, 新容量不一定要达到旧容量的 2 倍以上, 因而想进一步提高内存利用率, 可以考虑重写 Resize() 方法, 使得每次扩容变成稍大一点的质数即可. 当然这样一来插入效率会降低, 自行取舍.

 

[3] 对 Hashtable  初始化时直接指定 capacity 是个好主意, 减少了 Resize() 的次数, 降低开销.

 

 

 

今天整理的另两篇相关文章：
《Vector、ArrayList、List使用深入剖析》http://tonylian.iteye.com/blog/384067
《ArrayList的使用方法》http://tonylian.iteye.com/blog/384071