哈希表查找9.4哈希表的基本概念9.4.11哈希表设要存储的元素个数为n，设置一个长度为m（m≥n）的连续内存单元。以每个元素的关键字k；（0≤i≤n-1）为自变量，通过一个哈希函数h把k,映射为内存单元的地址（或相对地址）h(ki)。并把该元素存储在这个内存单元中。1/62
设要存储的元素个数为n，设置一个长度为m（m≥n）的连续内存 单元。 以每个元素的关键字ki（0≤i≤n-1）为自变量，通过一个哈希函 数h把ki映射为内存单元的地址（或相对地址）h(ki)。 并把该元素存储在这个内存单元中。 1/62
n个对象个数m（m≥n）的连续内存单元哈希函数h存储地址存储地址=h(key)2/62
哈希函数h 存储 地址 存储地址=h(key) n个对象个数 m（m≥n）的连续内存单元 2/62
哈希表ha学号姓名哈希地址分数0王华9020180011学号姓名分数2王华9020180013刘丽622018010n=7m=12李英4822018005陈明542018006h（学号）=学号-2018001陈明542018006张强9520180096许兵762018007许兵7620180077李萍8820180128张强952018009李英8220180059刘丽62201801010李萍11882018012查找学号为2018010的学生分数：先计算h（2018010）=2018010-2018001=9再取ha[9]元素的分数62即可。对应的查找时间为0(1)。3/62
学号 姓名 分数 2018001 王华 90 2018010 刘丽 62 2018006 陈明 54 2018009 张强 95 2018007 许兵 76 2018012 李萍 88 2018005 李英 82 哈希地址 学号 姓名 分数 0 2018001 王华 90 9 2018010 刘丽 62 5 2018006 陈明 54 8 2018009 张强 95 6 2018007 许兵 76 11 2018012 李萍 88 4 2018005 李英 82 1 2 3 7 10 n=7 m=12 h(学号)=学号-2018001 查找学号为2018010的学生分数： 先计算h(2018010)=2018010-2018001=9。 再取ha[9]元素的分数62即可。 对应的查找时间为O(1)。 哈希表ha 3/62
对于两个不同的关键字k;和k，（i≠j）出现h(k;)=h(k,)，这种现象称为哈希冲突。将具有不同关键字而具有相同哈希地址的元素称为“同义词”，这种冲突也称为同义词冲突，需要解决哈希冲突4/62
对于两个不同的关键字ki和kj（i≠j）出现h(ki)=h(kj)，这种现象 称为哈希冲突。 将具有不同关键字而具有相同哈希地址的元素称为“同义词”，这种 冲突也称为同义词冲突。 需 要 解 决哈希 冲突 4/62
哈希函数构造方法9.4.2构造哈希函数的目标：使得到的哈希地址尽可能均匀地分布在m个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率。根据关键字的结构和分布的不同，有多种构造哈希函数的方法。5/62
构造哈希函数的目标：使得到的哈希地址尽可能均匀地分布在m个连 续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的 时间效率。 根据关键字的结构和分布的不同，有多种构造哈希函数的方法。 5/62