哈希表

哈希表

使用哈希函数插入数据的数组叫哈希表

哈希化

把一个大范围的数字转化成一个小范围的数字叫哈希化

哈希函数

把一个大范围的数字转化成一个小范围的数字的函数叫哈希函数

把关键字转化为数组下标

1、关键字不需要转换，比如员工编号从0到1000，关键字员工编号可以直接做为数组下标

2、把一部英文字典装入哈希表，a是1，b是2，c是3，依此类推，z是26，还有空格是0

1）数字相加 cats=3+1+20+19=43
假设单词最长有10个字母组成a的编码是1，zzzzzzzzzz是26*10=260，这样单词编码的范围是从1到260。不幸的是，字典中一共有50000个单词。数组下标太少，每个数组元素大概要存储50000/260=192个单词。

2）幂的连乘
7564= 7*10³ + 5*10² + 6*10¹  +  4*10⁰
cats=  3*27³ + 1*10² + 20*10¹+ 19*10⁰
这样每个单词对应独一无二的一个数字
最长的10个字母的单词zzzzzzzzzz，将转化成26*27⁹+26*27⁸+26*27⁷+26*27⁶+26*27⁵+26*27⁴+26*27³+26*27²+26*27¹+26*27⁰
仅27⁹就超过7000000000000，结果非常巨大，内存中的数组根本不可能有这么多的单元，产生的数组下标太多

3)哈希函数

取余法
index = x / arrayLength

哈希化后的冲突

开放地址法

线性探测、二次探测、再哈希法

链地址法

哈希表

原文：https://www.cnblogs.com/Mike_Chang/p/10424364.html