理解哈希表（Hash Table）
用于确定：某个元素是否在已知集合中。
本质上和排序+二分法的查找一样，都是把已知集合的本质特征提取出来，就像匹配时，用主分量分析一样。实现起来，把已知集合的数据经过处理，得到hash table，这个table中，每一项对应一个或多个数据，所以必须有处理这个问题（术语叫冲突）的机制。例如：10000个数据，都除以100，得到100个数，就是hash表，这样，可以搜索很小的hash表代替搜索原来的大表。本质上，就是用已知元素的前几位（不考虑十位和百位）作为其特征。实际中这样一般不行，我想，对于随机集合来说，用素数是个不错的主意。但对于大多数有特征的数据，还需要好好考虑如何提取其特征（术语上称之为hash函数的设计）。像是单词之类，肯定不是随机的，必然有特征，如果按随机数据考虑，显然会增加冲突的机会，导致浪费时间。本质上和排序+二分法的查
阅读背景：
理解哈希表2（Hash Table）
来源：互联网
分享到：
