浅谈竞赛中哈希表的应用.pdf

浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 哈尔滨市第三中学 刘翀 哈尔滨市第三中学 刘翀 应用 哈希表 数据结构 关键词 应用 哈希表 数据结构 [关键词] [ ] 摘要 [摘要] [ ] 哈希表是一种高效的数据结构。本文分五个部分：首先提 出了哈 哈希表是一种高效的数据结构。本文分五个部分：首先提 出了哈 希表的优点，其次介绍了它的基础操作， 着从简单的例子中作 了效 希表的优点，其次介绍了它的基础操作， 着从简单的例子中作 了效 率对比，指出其适用范围以及特点，然后通过例子说明了如何在题 目 率对比，指出其适用范围以及特点，然后通过例子说明了如何在题 目 中运用哈希表以及需要注意的问题，最后总结全文。 中运用哈希表以及需要注意的问题，最后总结全文。 正文 [正文] [ ] 1. 引言 1. 引言 哈希表 （ ）的应用近两年才在 中出现，作为一种高效的数据结 哈希表 （ ）的应用近两年才在 中出现，作为一种高效的数据结 Hash Table NOI Hash Table NOI 构，它正在竞赛中发挥着越来越重要的作用。 构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可 以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越 以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越 来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的 来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的 特点之一。 特点之一。 哈希表又叫做散列表，分为 “开散列” 和 “闭散列”。考虑到竞赛时多数人 哈希表又叫做散列表，分为 “开散列” 和 “闭散列”。考虑到竞赛时多数人 通常避免使用动态存储结构，本文中的 “哈希表”仅指 “闭散列”，关于其他方面 通常避免使用动态存储结构，本文中的 “哈希表”仅指 “闭散列”，关于其他方面 读者可参阅其他书籍。 读者可参阅其他书籍。 2. 基础操作 2. 基础操作 2.1基本原理 2.1基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数 第 页 共 页 第 1 页 共 26 页 1 26 浅谈竞赛中哈希表的应用 浅谈竞赛中哈希表的应用 （哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值 （哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值 （即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简 （即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简 单的理解为，按照关键字为每一个元素 “分类”，然后将这个元素存储在 单的理解为，按照关键字为每一个元素 “分类”，然后将这个元素存储在 相应“类”所对应的地方。 相应“类”所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极