基于哈希查找的老窖字典

yanglinzi

谢谢分享。。

leolee82

天地一相 发表于 2024-11-8 09:49
请教，测试了老窖的，速度真的好快。测试你的，因为我的64位，就调整了声明部分，红字消失后测试，报错53 ...

VBHelper.dll是我用C++写的，里面主要是封装了一个计算hash的算法（还有排序算法以及一些回调功能函数等）。hash算法用的开源的，并与针对VB6的不同数据类型简单优化了下，可惜我用不到64位，目前DLL只支持32位，下面附上了hash的C++代码。其他用到VBHelper.dll的地方我都注释掉了，只把hash函数替换就可以不用VBHelper.dll了

我把VBHelper.dll和最新的字典代码也传上来吧。原来的有个bug，数据量大了才能看出来，也增加了一些功能函数，最实用的应该是ItemArrayView，字典Item是数组时，可以直接修改这个数组的元素，而不用创建一新的数组替换。
其实这个封装的HASH函数提升也不是很大，我记得数据量小时系统自带的字典快些。可以尝试调用C#中的字典之类的，估计会好用些。

1. //BKDRHash
   
2. /// @brief BKDR Hash Function  
   
3. /// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得 名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。
   
4. inline
   
5. size_t  __stdcall _HashCaseSensitive(wchar_t* str, ULONG iLen) {
   
6.         size_t hash = 0;
   
7.         while (iLen--) {
   
8.                 hash = hash * 131 + (*str++);   // 也可以乘以31、131、1313、13131、131313..  
   
9.                 // 有人说将乘法分解为位运算及加减法可以提高效率，如将上式表达为：hash = hash << 7 + hash << 1 + hash + ch;  
   
10.                 // 但其实在Intel平台上，CPU内部对二者的处理效率都是差不多的，  
    
11.                 // 我分别进行了100亿次的上述两种运算，发现二者时间差距基本为0（如果是Debug版，分解成位运算后的耗时还要高1/3）；  
    
12.                 // 在ARM这类RISC系统上没有测试过，由于ARM内部使用Booth's Algorithm来模拟32位整数乘法运算，它的效率与乘数有关：  
    
13.                 // 当乘数8-31位都为1或0时，需要1个时钟周期  
    
14.                 // 当乘数16-31位都为1或0时，需要2个时钟周期  
    
15.                 // 当乘数24-31位都为1或0时，需要3个时钟周期  
    
16.                 // 否则，需要4个时钟周期  
    
17.                 // 因此，虽然我没有实际测试，但是我依然认为二者效率上差别不大
    
18.                 //str += 2;
    
19.         }
    
20.         return  hash;
    
21. }
    
22. 
    
23. size_t __stdcall HashCaseSensitive(void* p) {
    
24.         VARTYPE vt = ((VARIANT*)(p))->vt;
    
25. 
    
26.         //VT_BYREF
    
27.         if ((vt & VT_BYREF) == VT_BYREF) {
    
28.                 p = ((VARIANT*)(p))->byref;
    
29.                 vt &= ~VT_BYREF;
    
30.         }
    
31.         else
    
32.                 p = &((VARIANT*)(p))->byref;
    
33. 
    
34.         //VARIANT
    
35.         if ((vt & VT_VARIANT) == VT_VARIANT) {
    
36.                 vt &= ~VT_VARIANT;
    
37.         }
    
38. 
    
39.         if (vt == VT_BSTR) {
    
40.                 {
    
41.                         return _HashCaseSensitive((wchar_t*)(*(long*)(p)), (*((long*)(*(long*)(p)) - 1)) >> 1);
    
42.                 }
    
43.         }
    
44. 
    
45.         //2 个字节 Boolean  Integer
    
46.         if (vt == VT_I2 || vt == VT_BOOL) return *reinterpret_cast<UINT16*>(p);
    
47. 
    
48.         //4 个字节 Long Single
    
49.         if (vt == VT_I4 || vt == VT_R4) return *reinterpret_cast<size_t*>(p);
    
50. 
    
51.         //8 个字节 Double LongLong Date Currency
    
52.         if (vt == VT_R8 || vt == VT_DATE || vt == VT_CY || vt == VT_I8) return _HashCaseSensitive((wchar_t*)p, 4);
    
53. 
    
54.         //16 个字节 Decimal
    
55.         if (vt == VT_DECIMAL) return _HashCaseSensitive((wchar_t*)p, 8);
    
56. 
    
57.         //1 个字节 Byte
    
58.         if (vt == VT_UI1) return *reinterpret_cast<unsigned char*>(p);
    
59. 
    
60.         return 0;
    
61. }
    
62. inline
    
63. size_t  __stdcall _HashCaseInsensitive(wchar_t* str, ULONG iLen) {
    
64.         size_t hash = 0;
    
65.         while (iLen--) {
    
66.                 hash = hash * 131 + ((*str > L'Z' || *str < L'A') ? (*str++) : ((*str++) | 0x20));
    
67.         }
    
68.         return hash;
    
69. }
    
70. size_t __stdcall HashCaseInsensitive(void* p) {
    
71.         VARTYPE vt = ((VARIANT*)(p))->vt;
    
72. 
    
73.         //vbNullString/vbEmpty返回0
    
74.         if (((VARIANT*)(p))->byref == nullptr) return 0;
    
75. 
    
76.         //VT_BYREF
    
77.         if ((vt & VT_BYREF) == VT_BYREF) {
    
78.                 p = ((VARIANT*)(p))->byref;
    
79.                 vt &= ~VT_BYREF;
    
80.         }
    
81.         else
    
82.                 p = &((VARIANT*)(p))->byref;
    
83. 
    
84.         //VARIANT
    
85.         if ((vt & VT_VARIANT) == VT_VARIANT) vt &= ~VT_VARIANT;
    
86. 
    
87.         if (vt == VT_BSTR) return _HashCaseInsensitive((wchar_t*)(*(long*)(p)), (*((long*)(*(long*)(p)) - 1)) >> 1);
    
88. 
    
89.         //2 个字节 Boolean  Integer
    
90.         if (vt == VT_I2 || vt == VT_BOOL) return *reinterpret_cast<UINT16*>(p);
    
91. 
    
92.         //4 个字节 Long Single
    
93.         if (vt == VT_I4 || vt == VT_R4) return *reinterpret_cast<size_t*>(p);
    
94. 
    
95.         //8 个字节 Double LongLong Date Currency
    
96.         if (vt == VT_R8 || vt == VT_DATE || vt == VT_CY || vt == VT_I8) return _HashCaseSensitive((wchar_t*)p, 4);
    
97. 
    
98.         //16 个字节 Decimal
    
99.         if (vt == VT_DECIMAL) return _HashCaseSensitive((wchar_t*)p, 8);
    
100. 
     
101.         //1 个字节 Byte
     
102.         if (vt == VT_UI1) return *reinterpret_cast<unsigned char*>(p);
     
103. 
     
104.         return 0;
     
105. }
     

复制代码

VBHelper.zip (92.63 KB, 下载次数: 1)

2024-11-11 09:16 上传

点击文件名下载附件

clsDictionary.rar (13.52 KB, 下载次数: 1)

2024-11-11 09:16 上传

点击文件名下载附件