哈希表原理和实现

liucqa

真正的哈希表比这个要复杂得多，至少要解决碰撞问题才能谈到实用性
https://kb.cnblogs.com/page/189480/

从头到尾彻底解析Hash表算法

liucqa

https://blog.csdn.net/vking_wang/article/details/14166593
HashMap实现原理分析

这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

liucqa

https://blog.csdn.net/vking_wang/article/details/14166593

哈希表的数组是定长的，如果太大，则浪费，如果太小，体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数。当然，根据不同的数据量，会有不同的哈希表的大小。对于数据量时多时少的应用，最好的设计是使用动态可变尺寸的哈希表，那么如果你发现哈希表尺寸太小了，比如其中的元素是哈希表尺寸的2倍时，我们就需要扩大哈希表尺寸，一般是扩大一倍。

下面是哈希表尺寸大小的可能取值：

17,            37,          79,        163,          331,
673,           1361,        2729,       5471,         10949,
21911,          43853,      87719,      175447,      350899,
701819,         1403641,    2807303,     5614657,     11229331,
22458671,       44917381,    89834777,    179669557,   359339171,
718678369,      1437356741,  2147483647

yqdaqinqin

哈希表，第一次映入视线，好东西，学习了

HHAAMM

就是给Key找个合适的索引号，这应该是数学问题，其他的很简单吧。
我测试声明很大很大的哈希表数组也没对运行效率有什么影响反而比楼主的*1.33还要快些，可能是少了几次Do吧。估计现在机器内存都不是问题，大点也没关系毕竟又不在其中循环。

三坛老窖

liucqa 发表于 2018-4-10 07:24
真正的哈希表比这个要复杂得多，至少要解决碰撞问题才能谈到实用性
https://kb.cnblogs.com/page/189480/
...

不知老大所指的“真正的哈希表”是啥样的，我觉得楼主的这个哈希表已经解决了碰撞问题，如果理解了其运行机制，在针对大数据处理时，还是相当之实用的。

三坛老窖

liucqa 发表于 2018-4-10 07:26
https://blog.csdn.net/vking_wang/article/details/14166593

哈希表的数组是定长的，如果太大，则浪费 ...

笼统的说哈希表的尺寸最好是一个质数，是没有根据的。当使用链表法解决冲突时，哈希表尺寸是否质数根本无关紧要，而用线性探测法解决冲突，用质数作为哈希表尺寸，其目的就是防止无限循环的探测，如果你设计的探测函数本身就能避免无限循环探测，就将没必要一定使用质数做哈希表的尺寸了。

liucqa

三坛老窖 发表于 2018-4-10 15:20
笼统的说哈希表的尺寸最好是一个质数，是没有根据的。当使用链表法解决冲突时，哈希表尺寸是否质数根本无 ...

哈希表已经是成熟技术了，所以没必要重复造轮子。

顺便说一下，在我看来，楼主的代码更像是数组而不是哈希表。

其它的问题，建议你看看我给的三个链接里面的算法和代码，如果能翻译成完整的vba代码，也算是好事了。

三坛老窖

liucqa 发表于 2018-4-10 17:51
哈希表已经是成熟技术了，所以没必要重复造轮子。

顺便说一下，在我看来，楼主的代码更像是数组而不是 ...

呵呵，老大你是挣钱挣糊涂了吧。

哈希技术是成熟技术，这个没错，就像从多算法技术一样，在许多项目中早已得到成熟的应用。至于有没有必要重复造轮子，不知轮子是啥意思？我映象中轮子是泛指李洪志的“法轮功”。我猜你说的是指用不着在此介绍哈希原理。如果我猜的没错，则我不认同你的观点，理由如下：
1、虽然对专业人员来说，这算不得什么高难的技术，但对我等非专业人员来说，要理解并掌握这项技术也非易事。当年法师的贴和你给出的连接中的内容（以前看过），我看过几遍后，都是似懂非懂的，直到某一天才突然想通的。
2、掌握该项技术后，可轻松搞掂对大数据量处理的问题，而大数据量处理的问题，在VBA板块中的求助帖，占有相当的比例。

我倒是认为，介绍此类原理的技术贴，却是老大你的职责所在（学导的字面理解）。

“楼主的代码更像是数组而不是哈希表”？哈希表本身就是数组呀，我没见过不是数组的哈希表。

三坛老窖

“字典内部就由哈希表构建的”，说的不够严密，大家常用VBScript字典，据我测试推断，其内部肯定不是由哈希表构建的，估计是B+之类的平衡树。

我看了你的介绍，也是一头雾水，觉得不好理解，希望楼主的叙述更加严密些，最好多配一些图片来说明。