包概述
Hash 包包含用于管理以二进制或字符串为键的哈希表的若干子包函数。两个子包都建立在简单哈希表的基本思想之上。哈希表由两部分组成:数据存储和哈希函数。数据存储是一个含 n 个单元的数组,每个单元的索引位于 0 到 n-1 范围内。哈希函数是对键执行的一种数学运算,返回 0 到 n-1 之间的整数。当客户端向哈希表插入新的 (key,value) 对时,哈希函数决定用于存储该值的单元;哈希函数也可用于检索与给定键关联的值。
由于地址空间有限,两个不同的键可能映射到同一个单元(即冲突)。出现这种情况时,Hash 包会将新值追加到目标单元中的链表。较大的哈希表冲突较少,但整表需要更多内存。可以插入哈希表的唯一 (key,value) 对数量仅受工作站可用内存的限制。
如果哈希表必须为重复的键存储值,建议为每个重复键使用手工维护的列表。这样会形成如图 1所示的数据结构。每个哈希表单元要么包含单个 (key,value) 对,要么包含自动维护的唯一 (key,value) 对链表,其中某些值本身可以是同一键多个值的手工维护列表。实现这种链式方法的工作流程在 prg_bin_hash_table_item_insert() 和 prg_string_hash_table_item_insert() 中有说明。
**警告:**出于效率考虑,Hash 包中的函数未做成 MT-safe(线程安全)。因此在并行仿真中,对共享哈希表的访问必须由外部串行化。
图 1:哈希表结构示例
