半岛,半岛体育,半岛体育app,半岛官网,半岛电竞,半岛真人,半岛棋牌,半岛体育官网注册,半岛体育官方app下载,半岛体育app下载,半岛体育怎么样,半岛体育官网,半岛体育登录入口,半岛体育官方网站

　　经 济 管理 与 干 部教育1 99 5年 第4期关 于 哈 希 法 查 找 效 率 的 分 析曾 绍 良摘 要:哈 希 法 是 查 找 中 的 一 项重 要 技米,很 多 专 著 对 这 项 技米都做 了 比 较 详 细 的 讨论。 如克努特 的 《计 算机 程 序设 计 技 巧 》,以 及各 大 专 院 校 教 材 《 数 据 结构 》 中 都 程 度 不 同地讨论 了 这个 问 题,并 分 析 了 哈 希 法 的 查 找效 率。笔者 对 这 些 分析 和 结 论 持 有 不 同 的 看 法。本 文 对 哈希 法 查 找效 率 问 题进 行 了 深 入 地探讨,得 出 了 相 应 的结 论,并 通 过 实 验 数据 对 所得 结 论进 行 了 ...

　　经 济 管理 与 干 部教育1 99 5年 第4期关 于 哈 希 法 查 找 效 率 的 分 析曾 绍 良摘 要:哈 希 法 是 查 找 中 的 一 项重 要 技米,很 多 专 著 对 这 项 技米都做 了 比 较 详 细 的 讨论。 如克努特 的 《计 算机 程 序设 计 技 巧 》,以 及各 大 专 院 校 教 材 《 数 据 结构 》 中 都 程 度 不 同地讨论 了 这个 问 题,并 分 析 了 哈 希 法 的 查 找效 率。笔者 对 这 些 分析 和 结 论 持 有 不 同 的 看 法。本 文 对 哈希 法 查 找效 率 问 题进 行 了 深 入 地探讨,得 出 了 相 应 的结 论,并 通 过 实 验 数据 对 所得 结 论进 行 了 验 证。一、引言哈 希 法是查 找中 的一种很重要 的方 法。与顺 序查 找、 折 半 查找 以 及 分 块 查 找 等 方法相比 较,哈希 法 的 突 出 特 点 是 查找效率高。因此,这种方 法 在编 译技术等 领域 得到 了 很广 泛 的 应用。关 于 哈希 法的查找 效 率,克 努特 做了 详 细的 分 析,清华大 学 《 数 据 结构 》 中 也进行了推导,笔者认 为 有 不 妥之 处。下面,仅 就 哈 希 法 的查找 效率 问 题 进 行分析。三、哈 希 法的查找效率设有数据项 集合 S,共n项,其关 键字 集合 为K。今 要 将其 存 储 在长度 为 m 的 表 中 ( n 镇 m),每个 数 据占据 表 中 的 一个 位 置。采 取 哈希 法进 行存 储,就需要 确 定一 个 定义 在集合 S 上 的 映象 H,使得 对于S中的任意元 素 S,令其关键字为 K,都 有:O 毛 H ( 民 ) 镇 m 一 l( 1 )满足上 述 要 求的 映 象 函 数 很多,通 常 称为哈 希 ( a H h s ) 函 数。利 用 哈 希 函 数,可 以 将 集 合 S 中每个数据项,依其 关键字的哈希 函 数 值,在存 储 表 中 确 定 其 存储位 置。最理想 的哈希 函 数 为:对 于 S 中的任 意两个元 素 S,S, ,若i 笋 j,则 H ( K ) 共 H ( j K )。这样 造 成的表称为 直 接 表。直 接 表的 处理 效率最高,对 于 S 中的任 一个数据项,无论 存 储 和 查找 都 是一 次成 功。然而这样的 函 数 很难找 到。根 据克努 特的分析,在长 度 为 4 1 的表 中 存储 3 1 个 数 据项,每 一千万个哈 希 函 数 中, 这 种 最理想的 函 数 只 有一个 。花 费太 大 的精 力 去 寻 找 这 样的 函 数 是不经 济 的。而且在实际应用 中,哈希 函 数 的形式越简 单 越好,这样不 仅使 确立 函 数的 工 作简 单,而且根据 关 键 字计 算 地址的步 骤 简单, 有利 于时间 的节省。因此,大多数 实 用 的哈希 函 数,都 不能 使 数据项 与表 中 的位置产生一一对应 的关 系。即 是 说,可能有 两个 或 两 个 以 上 的 数据项,其关 键 字的哈 希 函 数 值 是 相等的。而表中 的 一个 位 置 只 能存 储 一个 数据 项,于是就 发 生了“ 冲 突 ” 。这种 现象 称 为 堆积现象。在 实 际应用 中,为了 节省 存储 空 间,应尽 可能 地 使表的 长度 m 与数据 项 的 个 数n相 接 近。数据项的 个 数n与 存储表 长 m 的 比 值,称 为装填 因子,以a示 之。即( 2 )一3 9一