清华大学出版社 TSINGHUA UNIVERSITY PRESS 第8章Hash表技术 8.1Hash表的基本概念 8.2几种常用的Hash表
第8章 Hash表技术 8.1 Hash表的基本概念 8.2 几种常用的Hash表
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 8.1.1直接查找技术 8.1.2Hash表 8.1.3Hash码的构造
8.1 Hash表的基本概念 8.1.1 直接查找技术 8.1.2 Hash表 8.1.3 Hash码的构造
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 8.1.1直接查找技术 设表的长度为n。如果存在一个函数i=i(k),对于表中 的任意一个元素的关键字k,满足以下条件: (1)1≤i≤n; (2)对于任意的元素关键字k1≠k2,恒存在i(k1)≠i(k2) 则称此表为直接查找表。其中函数i=i(k)称为关键字k 的映象函数
8.1 Hash表的基本概念 8.1.1 直接查找技术 设表的长度为n。如果存在一个函数i＝i(k)，对于表中 的任意一个元素的关键字k，满足以下条件： (1)1≤i≤n； (2)对于任意的元素关键字k1≠k2，恒存在i(k1)≠i(k2)。 则称此表为直接查找表。其中函数i＝i(k)称为关键字k 的映象函数
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 1.直接查找表的填入 要将关键字为k的元素填入到直接查找表,只需做以下两 步: (1)计算关键字k的映象函数i=i(k); (2)将关键字k及有关元素信息填入到表的第i项
8.1 Hash表的基本概念 1.直接查找表的填入 要将关键字为k的元素填入到直接查找表，只需做以下两 步： (1)计算关键字k的映象函数i＝i(k)； (2)将关键字k及有关元素信息填入到表的第i项
清华大学出版社 TSINGHUA UNIVERSITY PRESS 8.1Hash表的基本概念 2.直接查找表的取出 要在直接査找表中取出关键字k的元素,也只需做以下两 步: (1)计算关键字k的映象函数i=i(k); (2)检查表中第i项: 若第i项为空,则说明表中没有关键字为k的元素; 否则取出第i项中的元素即可
8.1 Hash表的基本概念 2.直接查找表的取出 要在直接查找表中取出关键字k的元素，也只需做以下两 步： (1)计算关键字k的映象函数i＝i(k)； (2)检查表中第i项： 若第i项为空，则说明表中没有关键字为k的元素； 否则取出第i项中的元素即可