哈希表原理和实现

lccchengcheng

有空的时候琢磨一下，谢谢分享了

blackttea1

收藏学习了........

Zamyi

高度保密 发表于 2018-3-20 00:50
64位中这个StrPtr数据类型不匹配怎么解决呢

试试

1. Private Declare PtrSafe Function hash Lib "ntdll.dll" Alias "RtlComputeCrc32" (ByVal start As Long, ByVal data As Long, ByVal Size As Long) As Long
   
2. Private Hash_Table() As Long           '哈希表
   
3. Private Count_Table As Long            '哈希表大小
   
4. Private H As Long                      '哈希值
   
5. Public Count As Long                   'Keys实际数目
   
6. 
   
7. Public Sub Init(bCount&)  '初始化哈希表
   
8. Count = 0
   
9. Count_Table = bCount * 1.33
   
10. ReDim Hash_Table(Count_Table - 1)
    
11. End Sub
    
12. 
    
13. Public Function Add(Key, Keys, x&) As Boolean
    
14. Dim k As Long, P
    
15. P = StrPtr(Key)
    
16. H = (hash(0, P, LenB(Key)) And &H7FFFFFFF) Mod Count_Table
    
17. Do
    
18.   If Hash_Table(H) = 0 Then
    
19.     Count = Count + 1
    
20.     Hash_Table(H) = Count
    
21.     Keys(Hash_Table(H), x) = Key
    
22.     Add = True
    
23.     Exit Function
    
24.   End If
    
25.   If StrComp(Key, Keys(Hash_Table(H), x)) = 0 Then Exit Function
    
26.   k = k + 1
    
27.   H = (H + k * k) Mod Count_Table
    
28. Loop
    
29. End Function
    
30. 
    
31. Public Function GetX(Key, Keys, x&) As Long
    
32. Dim k As Long, P
    
33. P = StrPtr(Key)
    
34. H = (hash(0, P, LenB(Key)) And &H7FFFFFFF) Mod Count_Table
    
35. Do
    
36.   If Hash_Table(H) = 0 Then Exit Function
    
37.   If StrComp(Key, Keys(Hash_Table(H), x)) = 0 Then GetX = Hash_Table(H): Exit Function
    
38.   k = k + 1
    
39.   H = (H + k * k) Mod Count_Table
    
40. Loop
    
41. End Function

复制代码

高度保密

Zamyi 发表于 2018-4-5 21:23
试试

可以了，谢谢！
不过您的字典，在下面的附件中，这一句：        n = ds(Arr(i, 1))
会出现对象不支持该属性的问题，不知道能不能优化一下

Zamyi的字典.rar (16.52 KB, 下载次数: 21)

2018-4-7 20:37 上传

点击文件名下载附件

HHAAMM

明白了
hash(0, StrPtr(Key), LenB(Key)这句是关键，以前没见过
取余数是为了索引号在数组下标内但这样会出现重复，用H = (H + k * k)来改变索引
* 1.33是为什么，是估计的还是有什么道理，如果恰巧Do好多次后k = k + 1 k * k 得到的H有没有超出范围的可能。

谢谢楼主分享！

Zamyi

高度保密 发表于 2018-4-7 20:38
可以了，谢谢！
不过您的字典好像也有在64位excel也有兼容性问题，不知道能不能优化一下

手头没有64位Office测试，自己修改。调用Dll主要二点
1、声明Declare注意加上 PtrSafe，
2、StrPtr返回的是LongLong类型，需转换成Long型。

Zamyi

HHAAMM 发表于 2018-4-7 22:42
明白了
hash(0, StrPtr(Key), LenB(Key)这句是关键，以前没见过
取余数是为了索引号在数组下标内但这样会 ...

哈希查找实际是查找哈希表中未使用的位置（称之为空穴），以随机样本，空穴比例小于25%时查找的效率降低较大，所以最小取1.33（1/1.33≈0.75)。改变H值上面所说的应该是固定种子随机数更能保证不会超出范围，但随机数毕竟也耗费资源；固定长度对于数量大明显效率降低，灰袍法师和老窖字典用的是固定定长；用平方序列，会比固定定长效果好些。除非是刻意地构造数据，绝大多数情况下应该不会超出范围。

HHAAMM

1. Sub test()
   
2.     Dim A As Variant
   
3.     Dim B() As String
   
4.     Dim HT() As Long, I(1 To 2) As Long, C As Long, R As Long, Y As Long, X As Long, H As Long, J As Long, P As Long
   
5.     A = Sheet1.Range("a1", Sheet1.[b65536].End(3))
   
6.     R = UBound(A)
   
7.     C = R * 1.33
   
8.     ReDim B(1 To R, 1 To 3)
   
9.     For X = 1 To 2
   
10.         ReDim HT(C - 1)
    
11.         For Y = 1 To R
    
12.             P = 0
    
13.             H = (hash(0, StrPtr(A(Y, X)), LenB(A(Y, X))) And &H7FFFFFFF) Mod C
    
14.             Do
    
15.                 If HT(H) = 0 Then
    
16.                     I(X) = I(X) + 1
    
17.                     HT(H) = I(X)
    
18.                     B(HT(H), X) = A(Y, X)
    
19.                     Exit Do
    
20.                 ElseIf StrComp(A(Y, X), B(HT(H), X)) = 0 Then
    
21.                     Exit Do
    
22.                 Else
    
23.                     P = P + 1
    
24.                     H = (H + P * P) Mod C
    
25.                 End If
    
26.             Loop
    
27.         Next
    
28.     Next
    
29.     For Y = 1 To I(1)
    
30.         P = 0
    
31.         H = (hash(0, StrPtr(B(Y, 1)), LenB(B(Y, 1))) And &H7FFFFFFF) Mod C
    
32.         Do
    
33.             If HT(H) = 0 Then
    
34.                 Exit Do
    
35.             ElseIf StrComp(B(Y, 1), B(HT(H), 2)) = 0 Then
    
36.                 J = J + 1
    
37.                 B(J, 3) = B(Y, 1)
    
38.                 Exit Do
    
39.             Else
    
40.                 P = P + 1
    
41.                 H = (H + P * P) Mod C
    
42.             End If
    
43.         Loop
    
44.     Next
    
45.     Sheet1.Range("c1:e" & R) = B
    
46. End Sub
    
47. '弄成这样好理解些

复制代码

HHAAMM

Zamyi 发表于 2018-4-8 14:30
哈希查找实际是查找哈希表中未使用的位置（称之为空穴），以随机样本，空穴比例小于25%时查找的效率降低 ...

我将哈希表最大下标扩大很多，用一百万行数据测试，运行速度反而快不少。
* 20

hyqzzs

谢谢楼主，收藏学习了........