精易论坛

标题: 通用哈希表，简化操作和函数，修复原版内存泄露 [打印本页]
作者: 猫神父    时间: 2021-1-1 01:49
标题: 通用哈希表，简化操作和函数，修复原版内存泄露
本帖最后由 猫神父 于 2021-1-1 21:24 编辑

通用型哈希表，最早发出的哥们儿已经不知去向（感谢他），目前的更新和优化好像都是酷宝贝在做，不过我经常要导入模块，所以一直想用一个不需要类直接复制粘贴程序集就能用的版本，经过一段时间打磨，总算自己写了一个，调试过程还是有不少曲折的，但是考虑到易语言都过了二十年了，知名度依旧不高，所以没什么好吝啬的，分享出来，人海茫茫，你能碰到的都是兄弟，不是竞争对手。

碰巧写TCP组包，考虑用哈希表存储数据，这也引出了 将原先的哈希读写拆分出 取指针 和 指针操作 的需求。

这个程序集的特点:
' 分层次展现
' 中文函数(公开)为哈希表主要函数
' 中文函数(未公开)为哈希表扩展功能函数
' 英文函数为独立的工具函数
' 带_的英文函数是哈希表的附属函数

' 1.对于取哈希值的算法进行了扩展，变成4种
' 2.增加了CRC32_PTR汇编算法,使用查表方式计算，速度与按字节计算的传统哈希相近,比RtlComputeCrc32快且兼容性强，比传统的哈希算法碰撞率低
' 3.增加了hash_PTR汇编算法,按字节计算哈希结果和之前一样,按字和按3字计算可用于文本key(但要注意对齐，比如Unicode是字对齐)
' 4.增加了 哈希_更改 子程序，这是将key作为handle使用，用于快速管理资源的一种理解方式
' 5.在哈希取值之前分离出 哈希_取指针，返回数据的内存地址，同时让哈希_取值命令更加简单易读

' 6.增加了 取素数不小于 的函数，用于创建和扩展链表，最早的创建方式不科学，遇到有规律的数会产生严重碰撞
' 7.修复了内存泄露的bug，具体位置在 哈希_添加 中找到相同key数据之后，补充了heapfree命令
' 8.更改取值方式,这个我看到酷宝贝也改了,取值直接返回指针，而不是再度申请内存(该操作同样会泄露)


阐述一下CRC32_PTR,综合考量了速度、资源占用，将表作为数据置入，用CALL/POP取出，比API快，已对比过各易论坛、资源网、目前是最快最稳定的，欢迎高手拍砖！
  1. .版本 2

  3. .子程序 CRC32_PTR, 整数型
  4. .参数 addr, 整数型
  5. .参数 len, 整数型
  6. .局部变量 校验值, 整数型

  8. ' call 0x00010405
  9. 置入代码 ({ 232, 0, 4, 0, 0 })
  10. ' *** 数据段 ***

  12. 置入代码 ({ 0, 0, 0, 0, 150, 48, 7, 119, 44, 97, 14, 238, 186, 81, 9, 153, 25, 196, 109, 7, 143, 244, 106, 112, 53, 165, 99, 233, 163, 149, 100, 158, 50, 136, 219, 14, 164, 184, 220, 121, 30, 233, 213, 224, 136, 217, 210, 151, 43, 76, 182, 9, 189, 124, 177, 126, 7, 45, 184, 231, 145, 29, 191, 144, 100, 16, 183, 29, 242, 32, 176, 106, 72, 113, 185, 243, 222, 65, 190, 132, 125, 212, 218, 26, 235, 228, 221, 109, 81, 181, 212, 244, 199, 133, 211, 131, 86, 152, 108, 19, 192, 168, 107, 100, 122, 249, 98, 253, 236, 201, 101, 138, 79, 92, 1, 20, 217, 108, 6, 99, 99, 61, 15, 250, 245, 13, 8, 141, 200, 32, 110, 59, 94, 16, 105, 76, 228, 65, 96, 213, 114, 113, 103, 162, 209, 228, 3, 60, 71, 212, 4, 75, 253, 133, 13, 210, 107, 181, 10, 165, 250, 168, 181, 53, 108, 152, 178, 66, 214, 201, 187, 219, 64, 249, 188, 172, 227, 108, 216, 50, 117, 92, 223, 69, 207, 13, 214, 220, 89, 61, 209, 171, 172, 48, 217, 38, 58, 0, 222, 81, 128, 81, 215, 200, 22, 97, 208, 191, 181, 244, 180, 33, 35, 196, 179, 86, 153, 149, 186, 207, 15, 165, 189, 184, 158, 184, 2, 40, 8, 136, 5, 95, 178, 217, 12, 198, 36, 233, 11, 177, 135, 124, 111, 47, 17, 76, 104, 88, 171, 29, 97, 193, 61, 45, 102, 182, 144, 65, 220, 118, 6, 113, 219, 1, 188, 32, 210, 152, 42, 16, 213, 239, 137, 133, 177, 113, 31, 181, 182, 6, 165, 228, 191, 159, 51, 212, 184, 232, 162, 201, 7, 120, 52, 249, 0, 15, 142, 168, 9, 150, 24, 152, 14, 225, 187, 13, 106, 127, 45, 61, 109, 8, 151, 108, 100, 145, 1, 92, 99, 230, 244, 81, 107, 107, 98, 97, 108, 28, 216, 48, 101, 133, 78, 0, 98, 242, 237, 149, 6, 108, 123, 165, 1, 27, 193, 244, 8, 130, 87, 196, 15, 245, 198, 217, 176, 101, 80, 233, 183, 18, 234, 184, 190, 139, 124, 136, 185, 252, 223, 29, 221, 98, 73, 45, 218, 21, 243, 124, 211, 140, 101, 76, 212, 251, 88, 97, 178, 77, 206, 81, 181, 58, 116, 0, 188, 163, 226, 48, 187, 212, 65, 165, 223, 74, 215, 149, 216, 61, 109, 196, 209, 164, 251, 244, 214, 211, 106, 233, 105, 67, 252, 217, 110, 52, 70, 136, 103, 173, 208, 184, 96, 218, 115, 45, 4, 68, 229, 29, 3, 51, 95, 76, 10, 170, 201, 124, 13, 221, 60, 113, 5, 80, 170, 65, 2, 39, 16, 16, 11, 190, 134, 32, 12, 201, 37, 181, 104, 87, 179, 133, 111, 32, 9, 212, 102, 185, 159, 228, 97, 206, 14, 249, 222, 94, 152, 201, 217, 41, 34, 152, 208, 176, 180, 168, 215, 199, 23, 61, 179, 89, 129, 13, 180, 46, 59, 92, 189, 183, 173, 108, 186, 192, 32, 131, 184, 237, 182, 179, 191, 154, 12, 226, 182, 3, 154, 210, 177, 116, 57, 71, 213, 234, 175, 119, 210, 157, 21, 38, 219, 4, 131, 22, 220, 115, 18, 11, 99, 227, 132, 59, 100, 148, 62, 106, 109, 13, 168, 90, 106, 122, 11, 207, 14, 228, 157, 255, 9, 147, 39, 174, 0, 10, 177, 158, 7, 125, 68, 147, 15, 240, 210, 163, 8, 135, 104, 242, 1, 30, 254, 194, 6, 105, 93, 87, 98, 247, 203, 103, 101, 128, 113, 54, 108, 25, 231, 6, 107, 110, 118, 27, 212, 254, 224, 43, 211, 137, 90, 122, 218, 16, 204, 74, 221, 103, 111, 223, 185, 249, 249, 239, 190, 142, 67, 190, 183, 23, 213, 142, 176, 96, 232, 163, 214, 214, 126, 147, 209, 161, 196, 194, 216, 56, 82, 242, 223, 79, 241, 103, 187, 209, 103, 87, 188, 166, 221, 6, 181, 63, 75, 54, 178, 72, 218, 43, 13, 216, 76, 27, 10, 175, 246, 74, 3, 54, 96, 122, 4, 65, 195, 239, 96, 223, 85, 223, 103, 168, 239, 142, 110, 49, 121, 190, 105, 70, 140, 179, 97, 203, 26, 131, 102, 188, 160, 210, 111, 37, 54, 226, 104, 82, 149, 119, 12, 204, 3, 71, 11, 187, 185, 22, 2, 34, 47, 38, 5, 85, 190, 59, 186, 197, 40, 11, 189, 178, 146, 90, 180, 43, 4, 106, 179, 92, 167, 255, 215, 194, 49, 207, 208, 181, 139, 158, 217, 44, 29, 174, 222, 91, 176, 194, 100, 155, 38, 242, 99, 236, 156, 163, 106, 117, 10, 147, 109, 2, 169, 6, 9, 156, 63, 54, 14, 235, 133, 103, 7, 114, 19, 87, 0, 5, 130, 74, 191, 149, 20, 122, 184, 226, 174, 43, 177, 123, 56, 27, 182, 12, 155, 142, 210, 146, 13, 190, 213, 229, 183, 239, 220, 124, 33, 223, 219, 11, 212, 210, 211, 134, 66, 226, 212, 241, 248, 179, 221, 104, 110, 131, 218, 31, 205, 22, 190, 129, 91, 38, 185, 246, 225, 119, 176, 111, 119, 71, 183, 24, 230, 90, 8, 136, 112, 106, 15, 255, 202, 59, 6, 102, 92, 11, 1, 17, 255, 158, 101, 143, 105, 174, 98, 248, 211, 255, 107, 97, 69, 207, 108, 22, 120, 226, 10, 160, 238, 210, 13, 215, 84, 131, 4, 78, 194, 179, 3, 57, 97, 38, 103, 167, 247, 22, 96, 208, 77, 71, 105, 73, 219, 119, 110, 62, 74, 106, 209, 174, 220, 90, 214, 217, 102, 11, 223, 64, 240, 59, 216, 55, 83, 174, 188, 169, 197, 158, 187, 222, 127, 207, 178, 71, 233, 255, 181, 48, 28, 242, 189, 189, 138, 194, 186, 202, 48, 147, 179, 83, 166, 163, 180, 36, 5, 54, 208, 186, 147, 6, 215, 205, 41, 87, 222, 84, 191, 103, 217, 35, 46, 122, 102, 179, 184, 74, 97, 196, 2, 27, 104, 93, 148, 43, 111, 42, 55, 190, 11, 180, 161, 142, 12, 195, 27, 223, 5, 90, 141, 239, 2, 45 })
  13. ' pop dword ptr [ebp-0x04] 弹出数据段地址到 校验值
  14. 置入代码 ({ 143, 69, 252 })
  15. ' push edi
  16. ' push esi
  17. ' push edx
  18. ' cmp dword ptr [ebp+0x0C] , 0x00000000
  19. ' je _label_1
  20. ' mov eax , dword ptr [ebp+0x08]
  21. ' test eax , eax
  22. ' jle _label_1
  23. ' mov esi , eax
  24. ' mov edi , dword ptr [ebp-0x04]
  25. ' xor eax , eax
  26. ' dec eax
  27. ' xor ecx , ecx
  28. ' _label_2
  29. ' xor edx , edx
  30. ' mov dl , byte ptr [ecx+esi]
  31. ' xor dl , al
  32. ' mov edx , dword ptr [edi+edx*4]
  33. ' shr eax , 0x08
  34. ' and eax , 0x00FFFFFF
  35. ' xor eax , edx
  36. ' inc ecx
  37. ' cmp ecx , dword ptr [ebp+0x0C]
  38. ' _label_1
  39. ' jl _label_2
  40. ' pop edx
  41. ' pop esi
  42. ' pop edi
  43. ' not eax
  44. ' mov dword ptr [ebp-0x04] , eax

  46. 置入代码 ({ 87, 86, 82, 131, 125, 12, 0, 116, 41, 139, 69, 8, 133, 192, 126, 34, 137, 198, 139, 125, 252, 49, 192, 72, 49, 201, 49, 210, 138, 20, 49, 48, 194, 139, 20, 151, 193, 232, 8, 37, 255, 255, 255, 0, 49, 208, 65, 59, 77, 12, 124, 230, 90, 94, 95, 247, 208, 137, 69, 252 })
  47. 返回 (校验值)
复制代码


一个小插曲:
测试过程中发现同样的代码却莫名其妙地崩溃，删掉了几乎所有无关函数后连数据对比都用上了，还以为是插件带毒，结果是 通用型 出了错，取变量指针 函数的通用型失效了，导致堆栈不平衡。


hashtable(改1).e

83.68 KB, 下载次数: 215, 下载积分: 精币 -2 枚

修复测试崩溃问题
作者: 不苦小和尚    时间: 2021-1-1 09:24
试试看，谢谢分享
作者: bdancerlc    时间: 2021-1-1 10:32
自带例子中的速度测试到这一步就崩了。

开始运行被调试程序
* 使用默认算法进行哈希值计算
* 实际创建的哈希表大小为:1511
* 当前数据量:1133大于扩容临界值1133，进行扩容操作!
* 当前数据量:2267大于扩容临界值2267，进行扩容操作!
* 更新结果:1 在偏移1024写入的值为:1000
* 对地址直接操作结果,写入的值:1001
* 在3000个数据的情况下,碰撞率:6.3%
* 使用CRC32进行哈希值计算
* CRC32存消耗时间:547ms.
* CRC32取消耗时间:7344ms.
* 按字进行哈希值计算
被调试易程序运行完毕
作者: 已注销541904    时间: 2021-1-1 10:52
提示: 作者被禁止或删除 内容自动屏蔽
作者: 外星星人    时间: 2021-1-1 11:43
感谢楼主无私奉献！
作者: fyh505099    时间: 2021-1-1 16:28
谢谢楼主分享 先收藏了
作者: emodiyu    时间: 2021-1-1 17:25
谢谢楼主分享
作者: 杨明煜    时间: 2021-1-1 20:05
学习........
作者: qwe1123121    时间: 2021-1-2 19:57
看的眼花啊
作者: 821888290    时间: 2021-1-3 16:26
支持开源
作者: 懒人定制软件    时间: 2021-1-7 01:01
大神，请收下我的膝盖  
作者: sostemp    时间: 2021-1-20 13:56
人海茫茫，你能碰到的都是兄弟，不是竞争对手。
作者: 广二爷xxoo    时间: 2021-2-3 11:57
是不是不能放到类里使用  好像输出值的时候 输出的却是key
作者: 892141059    时间: 2021-4-21 04:12
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
作者: 猫神父    时间: 2021-5-7 21:09
bug提醒
不可编译后使用 哈希_取值  获取非整数型数据
原因是编译后会将数据地址释放，所以建议放弃 哈希_取值 函数，改用 哈希_取指针

我也是最近使用文本型数据时才发现，并且参考了一下K大的哈希表，发现他早就已经修复了

这个bug很诡异，调试状态不崩
作者: Myaddgogo    时间: 2021-6-1 21:34
感谢 支持开源！
作者: 79961565    时间: 2021-7-2 12:13
支持开源~！感谢分享
作者: 一瓶矿泉水    时间: 2021-7-5 17:36
猫神父 发表于 2021-5-7 21:09
bug提醒
不可编译后使用 哈希_取值  获取非整数型数据
原因是编译后会将数据地址释放，所以建议放弃 哈希_ ...

意思是 编译后获取整数型数据，用哈希_取指针 得到的就是数据了,还是指针地址?
作者: tmtony    时间: 2021-10-5 08:21
先来学习吧
作者: 猫神父    时间: 2021-10-8 19:22
一瓶矿泉水 发表于 2021-7-5 17:36
意思是 编译后获取整数型数据，用哈希_取指针 得到的就是数据了,还是指针地址? ...

用例子来说明吧

test.e

14.73 KB, 下载次数: 12, 下载积分: 精币 -2 枚

作者: 一瓶矿泉水    时间: 2021-10-8 21:15
猫神父 发表于 2021-10-8 19:22
用例子来说明吧

感谢，老哥有心了，这么久的帖子 居然都回复了。赞
作者: 凝逸反病毒    时间: 2021-10-23 11:53
        感谢发布原创作品，精易因你更精彩！
作者: 诺言55    时间: 2023-5-3 05:20
有一个问题 创建 值 必须非文本型 如果值为文本型 取指针方式 取结果直接崩溃
作者: zuoliwei    时间: 2024-1-5 22:55
666666666666666666666666



欢迎光临 精易论坛 (https://125.confly.eu.org/) Powered by Discuz! X3.4