哈希表原理和实现

Nick_Chen0622

老师，我下载了您的附件，可是我并不能运行您的程序，显示缺失模块，可以把代码黏贴出来让我看一下吗？

liucqa

三坛老窖 发表于 2018-4-10 19:51
呵呵，老大你是挣钱挣糊涂了吧。

哈希技术是成熟技术，这个没错，就像从多算法技术一样，在许多项目中 ...

所谓对牛弹琴大概说得就是你这种不在一个频道上的对话了。

我理解算法外行对技术的渴求和期盼，不过，在发表技术观点之前，希望你还是能认真学习一下理论基础。

1、hash表并不是简单的数组，虽然你看到的代码是数组，但那并不是真正的hash表。
2、hash表并不能处理大数据，除非你认为几十万的数据也算大数据。
3、字典是哈希表构建的，这句话没错。哈希表的构建方法很多，最简单的是数组+链表。在不同系统中实现hash表的处理碰撞的方法也不同，例如java中是数组+链表/红黑树，某些系统中使用hash扩容技术。需要指出的是：hash表是个逻辑概念，通常说的hash表指的是逻辑数据结构而不是代码。用某种方式的代码实现的hash表叫做hashmap(java)，也叫做字典(windows)。所以，一楼的代码应该叫做hashmap（当然，在我看来，那更像是个数组而已。）
4、现在你明白为什么我说是"重复造轮子"了吧。因为我们没必要用vba代码来实现这个，windows提供的字典功能已经很完善了。除非你想在某些场合要求更快的速度，而采用空间换速度的方法自己写个hash表的简易实现，例如一楼的那种代码。需要指出的是，一楼的代码仅仅是个代码，它展示了hash表的作用，但并不能代表hash表的原理和技术。

最后说一点：
我并不打算和你争论那些百度可以轻松查到原理和技术实现的东西，给小白扫盲是我的责任，但教小白学习技术就不是我力所能及的了。所以，不要指望我会发一些百度上比比皆是的原理技术贴到EH上，因为我不认为百度上面的东西你学不会发到EH上面你就能学会了。

三坛老窖

liucqa 发表于 2018-4-11 07:36
所谓对牛弹琴大概说得就是你这种不在一个频道上的对话了。

我理解算法外行对技术的渴求和期盼，不过， ...

呵呵，看得出老大你还真有点生气了，这个问题有些严重了。

是真的，我除了会VBA和一点点VB外，像C、C#、Java等等一些主流的开发工具都没学过。与你对话可能真不在一个频道上。
但是我明白一点，我们说的哈希是一种算法，而算法是不会因所用开发工具的不同，而在本质上改变的。你能用Java之类的工具实现其功用，用VBA也可以实现的，只是实现起来的难易程度不同而已。
你第3点所说的，我觉得是在混淆概念，或者说是在玩概念。哈希方法也被人称作杂凑法，哈希表也称作散列表，你所列举的“数组+链表”和“数组+链表/红黑树”，何来杂凑、散列这一说。

论坛嘛，有争论是好事，大家各自发表自己的认识和观点，对参与者和观贴者都是一个学习的机会。

真心希望你能用你所说的“真正的哈希表”，用VBA写一段代码，贴上来让我等学习学习。
（Ctrl+C、Ctrl+V某论坛的文字或非VBA代码，就不劳你了）

三坛老窖

liucqa 发表于 2018-4-11 07:36
所谓对牛弹琴大概说得就是你这种不在一个频道上的对话了。

我理解算法外行对技术的渴求和期盼，不过， ...

嗯，这里正好有个题目，题意很简单，就是从一个子集中抽取给定关键字的关联信息（80万条记录抽取几千个关键字的关联信息），目前正在求助中，看老大是否能用“真正的哈希表”给予援手。
http://club.excelhome.net/thread-1406388-12-1.html

Zamyi

liucqa 发表于 2018-4-11 07:36
所谓对牛弹琴大概说得就是你这种不在一个频道上的对话了。

我理解算法外行对技术的渴求和期盼，不过， ...

很好！但你是学导，计算机专业，但请不要这种语气对待其他童鞋！
有几点请教：
1、21楼说需解决碰撞，1楼不是说了三个方法吗？何谓碰撞？即是不同字符串取得相同的H值。下面做了一个最极端的测试，所有的关键字的H值都取0，结果也可以找到。

1. Sub test()
   
2. Dim H_t() As Long, C As Long, bC As Long, H As Long, Seed As Single
   
3. Dim a(), n&, i&, mm&
   
4. n = 10
   
5. bC = 1.5 * n
   
6. ReDim H_t(bC - 1)
   
7. ReDim a(1 To n, 1 To 2)
   
8. Seed = Rnd
   
9. For i = 1 To n
   
10.   S = Format(Int(n * Rnd), "AB00000")
    
11.   H = 0 '(hash(0, StrPtr(s), LenB(s)) And &H7FFFFFFF) Mod bC
    
12.   r = Rnd(Seed)
    
13.   Do
    
14.     If H_t(H) = 0 Then
    
15.       C = C + 1
    
16.       H_t(H) = C
    
17.       a(C, 1) = S
    
18.       Exit Do
    
19.     End If
    
20.     If StrComp(S, a(H_t(H), 1)) = 0 Then Exit Do
    
21.     mm = mm + 1
    
22.     H = (H + bC * Rnd) Mod bC
    
23.   Loop
    
24. Next
    
25. MsgBox 1 + mm / C & "  " & C
    
26. End Sub

复制代码

2、23楼说哈希表的尺寸最好是一个质数，我理解这仅仅指用定长方法改变H值有用，其他方法没有多少作用。
3、这里谈论的VB，什么链表，VB能有吗？不管怎么说，不管Microsoft的字典是用什么写的，但它没我写的速度快，内存也不见得能省多少，这就足够了。

liucqa

Zamyi 发表于 2018-4-11 11:00
很好！但你是学导，计算机专业，但请不要这种语气对待其他童鞋！
有几点请教：
1、21楼说需解决碰撞，1 ...

所以我说你写的是一个简易的代码实现。没有链表或hash扩容等功能的代码算不上是哈希表原理。

最后说一下，你说vb没有链表，这说明你不知道链表是什么。

链表并不是哪个语言给提供的现成的功能，链表是可以用任何一门语言来实现的数据结构形式，这和vb之类的没有关系。我不想说你的技术水平如何，但我还是希望你在谈到什么原理、技术之类的宽泛词汇的时候，能够先学一下算法的基础知识和实现代码，这些在百度都能找到的。

liucqa

三坛老窖 发表于 2018-4-11 09:29
呵呵，看得出老大你还真有点生气了，这个问题有些严重了。

是真的，我除了会VBA和一点点VB外，像C、C# ...

好吧，我还得给你讲一下哈希和哈希表的区别

哈希是散列算法，哈希表是根据关键码值(Key value)而直接进行访问的数据结构。这俩不是一回事。

谈到哈希表的原理，我们通常要解决两个问题：
1、更好的散列算法，保证碰撞的概率尽可能低。
2、更好的碰撞算法，保证在大数据量的时候不会造成检索效率降低。
只有实现了这两方面的功能的代码，才能谈得上是哈希表的实现代码。

哈希表通过散列算法将数据存储在数组中，而这个数组并不是你想象的那种数值数组。链表和红黑树或者hash扩容技术，是确保碰撞发生之后的数据检索效率不会剧烈降低。

我还是那句话：希望论坛的会员在谈论算法、原理之类话题的时候，能够先去百度学习一下基础知识。

三坛老窖

liucqa 发表于 2018-4-11 16:46
好吧，我还得给你讲一下哈希和哈希表的区别

哈希是散列算法，哈希表是根据关键码值(Key value)而直接 ...

感谢老大能心平气和的给我等讲解哈希和哈希表的区别之类的知识。
不过你讲的这部分内容，在你讲解之前，我想我已经掌握了。

你楼上回复楼主的“没有链表或hash扩容等功能的代码算不上是哈希表原理”，我不认同。
我认为哈希原理的精锐是：Key值通过哈希函数得到一个整数，以此整数作为哈希表的地址，在哈希表中存放Key所在位置指针。
至于是否使用链表和能否扩容，则是根据具体应用而可用的选项，如果说没有使用链表算不得应用了哈希原理，那么，你所给出的链接中提到的开放式寻址法作何解释？
你的这个观点是出于哪位学者或哪本教科书？而或是你根据何种理论推演得出的？

你有这样的观点，就不难理解你前面说的，楼主介绍的不是“真正的哈希表”了

三坛老窖

liucqa 发表于 2018-4-11 16:46
好吧，我还得给你讲一下哈希和哈希表的区别

哈希是散列算法，哈希表是根据关键码值(Key value)而直接 ...

恕我直言，老大你可莫生气哟。

从你上面所发的文字内容来看，你并未真正掌握哈希算法的精锐。就像我当初看过灰袍法师有关哈希算法的帖子及百度上一些介绍哈希算法的文章时一样，处于似懂非懂的状态。

另外，百度上能搜到的一些介绍算法的文章，基本上多是泛泛而谈的，就像你所列链接中的文章一样，只能看个大概，你要细究起来，往往会让你的脑袋里灌满浆糊。

zopey

通过对象棋开局库中盘面记录 索引号的分析 （ 抽丝剥茧），是我对哈希表的一点了解。

http://club.excelhome.net/thread-1385165-1-1.html