hashtable深度探索

1.什么是哈希表（hashtable）？为什么要发明哈希表？

首先回答第二个问题，在之前的数据结构中我们学习了数组，链表，二叉树等数据结构，记录在结构中的相对位置是随机的，和记录的关键字之前不存在确定的关系，因此，在结构中查找记录时需要进行一系列和关键字的比较。这类查找方法是建立在“比较”基础上。在顺序查找时，比较的结果为“=”与“≠”两种可能；在折半查找，二叉排序查找和B树查找时，比较结果为“<”,“=”和“>”三种可能。查找效率依赖于查找过程中进行的比较次数。哈希表就是为了减少比较次数，尽可能通过关键字更快的找出所需记录。

哈希表是通过一个对应关系f，使得每个关键字和结构中一个唯一的存储位置相对应。因此在查找时，只需要根据对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，我们称这个对应关系f为哈希(Hash)函数，按这种思想建立的表称为哈希表。

2.如上图所示，这里我们只是对关键字H做取余处理（即哈希方法f为取余），当我们的空间充足时，我们可以在每个对应的f(H)位置放置元素（哈希值相同可以按序将安插位置后移，两个关键字哈希值相同称之为冲突），当空间不足时该如何处理（这里其实不够准确，这里应该说的是哈希表的主链长度小于要放入的元素个数，要是真的内存或硬盘空间不足时，也只能通过通过物理扩容来解决，程序应该解决不了这样的问题）？我们在之前初步认识hashtable时已经了解到，在横向发展受到阻碍时，可以尝试纵向发展，即为该f(H)位置纵向添加链表，来解决哈希值相同的问题。

这里其实是将问题转移了，我们前面说到过，我们使用哈希表就是为了一次计算直接找到记录，这里又对该关键字的记录做串长处理，这不是又倒回去了吗？这里我的理解这就是一种平衡，当某个篮子（bucket）下的元素过多时，则必须对篮子进行扩容，在扩容后对现有的元素要进行重新哈希。因此，一个哈希表的好坏取决于其哈希方法的是否高明。

3.模板参数解释

Value为元素类型，Key为关键字类型，HashFcn是获取hashcode的方法，ExtractKey为获取key的方法，EqualKey为判断key值是否相同的方法，存放bucket的容器为vector。

4.实例

这里的实例的hashtable的value和key类型均为字符串类型，hash方法为自带的全特化方法，key值为value本身，key值判断相等与否为包装后的strcmp

从下图我们可以看到，自带的特化特化了多种类型的hash方法

对于参数为const char*类型的数据，获取其hashcode的方法如下

巴特西

hashtable深度探索

最新文章

热门文章