基于哈希查找的老窖字典

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, 下载次数: 22)

2023-2-26 13:20 上传

点击文件名下载附件
clsDictionary.

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

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, 下载次数: 23)

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

下载学习。