基于哈希查找的老窖字典

leolee82

月初下载的，楼上把代码发出来了，也把自己优化的分享一下:
v5.1：初始化时不分配数组空间,字典扩容时不测试内存(VB中内存不够会报错),优化了扩容规则
     添加元素时先扩容 , 不需要检测是否已存在
     增加了for each支持
     增加了ForEachItem和ForEachKey函数 , 在内部直接回调自定义函数, 回调方法也可以换成CallWindowProcA
     测试了VariantCopy , 但不支持有事件的对象
     RemoveAll改为逻辑清空 , 增加Reset函数用于重置字典释放内存
     更换了更快的hash函数(vs编译的dll),不区分大小写的提速比较明显,代码如下:
     long __stdcall HashCaseSensive1( const unsigned char* str, long iLen){
         register long hash = 0;
         while ((iLen -= 2) >= 0) { hash = hash * 131 + (*str); str += 2;}
         return  hash;
     }

     long __stdcall HashCaseInsensive1(const unsigned char* str, long iLen){
         register long hash = 0;
         while ((iLen-=2) >= 0) { hash = hash * 131 + (*str)& 0x5F;str += 2;}//'0X5F=0101 1111'
         return hash;
     }

clsDictionary.rar (8.61 KB, 下载次数: 31)

2023-2-26 13:20 上传

点击文件名下载附件
clsDictionary.

VBHelper.rar (43.42 KB, 下载次数: 35)

2023-2-26 13:21 上传

点击文件名下载附件

三坛老窖

等到了第七个年头，终于让老窖引来了“玉”。
随着灰袍法师等大佬的退出江湖，感觉到EH的人气日渐式微，而今连EH最受欢迎的香川裙子也有一年多没有露脸了，本以为这贴就这样了，没想到还有loquat、leolee82这二位老兄，在EH坛中作潜心研究。
老窖老矣，一时竟看不懂代码和思路，汗~，在此，老窖衷心感谢loquat、leolee82二位。

另：leolee82=lee1892 ？

loquat

leolee82 发表于 2023-2-26 13:24
月初下载的，楼上把代码发出来了，也把自己优化的分享一下:
v5.1：初始化时不分配数组空间,字典扩容时不测 ...

竟然ForEach是用Collection实现的，竟然比IEnumVARIANT效率还高，肯定是我IEnumVARIANT封装得不对，要不就是VBA版本的接口效率不行。

leolee82

loquat 发表于 2023-3-20 21:15
竟然ForEach是用Collection实现的，竟然比IEnumVARIANT效率还高，肯定是我IEnumVARIANT封装得不对，要不 ...

clsDictionary.rar (8.62 KB, 下载次数: 39)

2023-3-21 00:52 上传

点击文件名下载附件

一开始我也是觉得IEnumVARIANT快，应该是参数传递太多再加上操作复杂些的原因。Collection毕竟是C或C++优化过的东西，VBA没法比的。
不知道直接调用C++中hashtable里会快多少。

改掉了个bug，又折腾了好几个hash函数，下面是代码（MurmurHash3是开源的github上有源码），哪个最快我比较不出来，有随机性。不过CaseInsensitive的一定要自己写，Lcase效率低接近1半。

1. // @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。
   
2. size_t __stdcall HashCaseSensitive( const  wchar_t* str, long iLen){
   
3.         register size_t hash = 0;
   
4.         while ((--iLen) >= 0){
   
5.                 hash = hash * 131 + (*str++);  
   
6.         }
   
7.         return  hash;
   
8. }
   
9. 
   
10. size_t  __stdcall HashCaseInsensitive(const wchar_t* str, long iLen){
    
11.         register size_t hash = 0;
    
12.         while ((--iLen) >= 0){
    
13.                 hash = hash * 131 +( (*str > L'Z' or *str < L'A') ? (*str++) : ((*str++) | 0x20));
    
14.         }
    
15.         return hash;
    
16. }
    
17. 
    
18. _INLINE_VAR constexpr size_t _FNV_offset_basis = 2166136261U;
    
19. _INLINE_VAR constexpr size_t _FNV_prime = 16777619U;
    
20. size_t __stdcall HashCaseSensitive1(const  wchar_t* str, long iLen) {
    
21.         size_t hash = _FNV_offset_basis;
    
22.         while ((--iLen) >= 0) {
    
23.                 hash ^= static_cast<size_t>(*str++);
    
24.                 hash *= _FNV_prime;
    
25.         }
    
26.         return hash;
    
27. }
    
28. 
    
29. 
    
30. size_t __stdcall HashCaseInsensitive1(const  wchar_t* str, long iLen) {
    
31.         size_t hash = _FNV_offset_basis;
    
32.         while ((--iLen) >= 0) {
    
33.                 hash ^= static_cast<size_t>(((*str > L'Z' or *str < L'A') ? (*str++) : ((*str++) | 0x20)));
    
34.                 hash *= _FNV_prime;
    
35.         }
    
36.         return hash;
    
37. }
    
38. 
    
39. 
    
40. size_t __stdcall HashCaseSensitive2(const  wchar_t* str, long iLen) {
    
41.         size_t hash = 0;
    
42.         MurmurHash3_x86_32(str, iLen * sizeof(wchar_t), 0, &hash);
    
43.         return hash;
    
44. }
    
45. 
    
46. size_t __stdcall HashCaseInsensitive2(wchar_t* str, long iLen) {
    
47.         size_t hash = 0;
    
48.         long n = iLen;
    
49.         while ((--iLen) >= 0) {
    
50.                 if (*str <= L'Z' and *str >= L'A')  
    
51.                         *str |= 0x20;
    
52.                 ++str;
    
53.         }
    
54.         MurmurHash3_x86_32(str-n, n * sizeof(wchar_t), 0, &hash);
    
55.         return hash;
    
56. }
    

复制代码

ivccav

三坛老窖 发表于 2023-2-27 04:16
等到了第七个年头，终于让老窖引来了“玉”。
随着灰袍法师等大佬的退出江湖，感觉到EH的人气日渐式微，而 ...

EH论坛已成为免费找劳力的地方了。每天充斥着数不清的重复、简单求助，分享或者讨论技术的很少了。

loquat

leolee82 发表于 2023-3-21 01:08
一开始我也是觉得IEnumVARIANT快，应该是参数传递太多再加上操作复杂些的原因。Collection毕竟是C或C++ ...

参数传递这个之前没有想过有多大影响
不过个人觉得VBA里实现的IUnknow，肯定比其他语言实现的要慢

q3698995

好帖。技术贴

qlmgu

下载学习。

ychj526926

目前我用时发现一个问题，烦请百忙之中确认一下
‘' ===========================================================================================================
' 功能：提取字典中所有有效条目的键值，构成一个数组输出
'
' 描述：当输入参数Transpose为True时，输出二维数组，否则输出一维数组
'
' 参数：Transpose   是否转置
'
' 返回：键值数组
' ===========================================================================================================
Function Keys(Optional Transpose As Boolean = False) As Variant
    Dim temp(), i As Long, k As Long
   
    If Transpose Then
        ReDim temp(mLastPoint - mDelCount - 1, 0)
        For i = 1 To mLastPoint
            If mLinkedList(i) >= 0 Then
                temp(k, 0) = mKeys(i)
                k = k + 1
            End If
        Next i
    Else
        
        If mLastPoint - mDelCount - 1 >= 0 Then
            ReDim temp(mLastPoint - mDelCount - 1)
            For i = 1 To mLastPoint
                If mLinkedList(i) >= 0 Then
                    temp(k) = mKeys(i)
                    k = k + 1
                End If
            Next i
        Else
            ReDim temp(0)
        End If
    End If
    Keys = temp: Erase temp
   
End Function

’‘’问题   mLastPoint - mDelCount - 1 存在=-1的情况，当小于0时，则报错了，我暂时添加了判断，不知是否会影响整体效率

天地一相

leolee82 发表于 2023-3-21 01:08
一开始我也是觉得IEnumVARIANT快，应该是参数传递太多再加上操作复杂些的原因。Collection毕竟是C或C++ ...

请教，测试了老窖的，速度真的好快。测试你的，因为我的64位，就调整了声明部分，红字消失后测试，报错53，VBHelper.dll 未找到，搜索处理未成，特此求教，谢谢。