发明者不知道。
发明的目的是提高海量数据的查找速度。
简单问题举例:
数据表中有N个无序的字符串(例如:英文人名)
给你一个字符串,请迅速找到它在数据表中的序号。
最笨的方法是逐个比较的方式来查找。查找时间是O(N),简单说最后的
情况是比较N次。
hash 表能够加快查找速度。使用hash表首先要申请一个定长的指针数组。
通过在建立数据表时通过特定的计算公式(hash散列函数)计算出每个字符串对应的一个数值。而后把此数值作为数组下标,把此字符串在数据表的序号保存在此数组元素中。(可以扩展到保存一个结构体指针)
将来想查找某字符串对应位置时,只需要通过hash散列函数计算出字符串对应的值就可以直接知道此字符串的序号等信息了。这样查找时间是O(1)了。因为不需要查找了,知道数组下标就能访问数组相应元素了,而元素中保存的就是序号等信息。