【数据结构】如何给哈希集设计哈希算法
# 如何给哈希集设计哈希算法## 概念解释
### 什么是哈希算法
哈希函数算法也叫 **数据摘要算法** ，对一串数据进行各种计算，最终得到一个新的数据，它 **能代表原始的那串数据** ，但是无法还原成原始数据。哈希函数算法按照用途分为：
- **数据正确性校验** 用的哈希函数算法
- **密码学安全** 用的哈希函数算法
- **数据结构** 管理数据时使用的简单哈希算法
### 什么叫「哈希碰撞」
不同的原始数据生成出相同的哈希值的情况叫「哈希碰撞」。一个哈希算法的设计需要尽可能避免其发生哈希碰撞。哈希碰撞率高的哈希算法是设计失败的哈希算法。
### 什么叫「密码学安全」
符合密码学安全的哈希算法不仅需要有极低的哈希碰撞率，而且必须确保攻击者难以通过一个已有的哈希值逆推出原始数据。
### 什么叫「数据正确性校验」
在传输数据的过程中，数据里附带了一个原始数据的哈希值。接收方在接收到数据后，对数据使用相同的哈希算法重新计算一遍，看看算出来的哈希值是否和发过来的哈希值相同，如果是，那就认定数据的传输是无误的。
### 常见哈希函数算法（以下这些不使用于哈希集等数据结构用途）
- 循环校验算法 CRC（通常不用于密码学范畴，主要用于进行数据正确性校验）
- CRC16（用于网络传输层验证网络数据包是否被正确传输）
- CRC32（除了众所周知的 `CRC32` 外，还有其它的版本比如 `CRC32b`、`CRC32c` 等）
- Message Digest（如 MD4、MD5。主要用于密码学范畴）
- MD4（由于安全问题已被弃用。例：Windows XP 的用户开机密码以 `MD4` 形式存储于其中的 `sam` 文件中，而不少「开机密码破解软件」可以无需联网直接破解出 **密码原文** ）
- MD5（由于 **使用广泛** ，不少人制作了 「MD5碰撞库」，这导致 `MD5` 在某些场合具有 *安全风险* ，比如对 **用户密码的哈希处理** ）
- 因此在使用 `MD5` 处理用户密码时，通常需要再对用户密码 **加盐处理** 。
- SHA 系列（安全哈希算法）
- SHA1（多年前谷歌公司花费一年的时间[破解了它](https://shattered.io/static/shattered.pdf)，于是说它有安全问题。因此被弃用）
- SHA2（因为上述原因导致大家不爱用 `SHA1`，现在的人喜欢使用它替代旧的 `SHA1` 的使用场景）。现在通常所说的「SHA256」「SHA512」其实是「SHA2-256」「SHA2-512」。
- SHA3 （2015 年诞生。由于出现了理论上可破解 MD5 和 SHA2 的说法，SHA3 应运而生。）
- BLAKE
- Argon
以上这些哈希算法不适合被用到诸如哈希集、哈希表等数据结构上。不适合的原因是因为这些算法的设计目标是 **极尽最大可能可能减少哈希碰撞** ，从而符合 **密码学安全** 的要求或者 **数据准确性校验时避免发生哈希碰撞** ，但是并不太在乎计算的速度和算出来的哈希值的长度。 **给哈希集等类似的数据结构使用的快速哈希函数的设计** 应当尽可能简化，并且放宽对哈希碰撞概率的要求。
### 什么是哈希表
哈希表、哈希集是一种数据结构，其使用「桶」作为数组单元，然后管理「桶数组」。所谓「桶」，是一种存储数据的容器，我们对它的要求是它要能存储多个数据。因此，「桶」可以是数组，也可以是链表。通常情况下的桶都被设计为链表形式。
哈希表常被用做 **字典** ，也就是一个键（Key）对应一个值（Value），最典型的例子是某 **学生管理系统** 可以使用学生的「学号」作为 Key，而查询出来的值（Value）则是该学生的姓名和身份信息。使用哈希表查询数据的过程远远快于数组遍历的方式。
哈希集常被用做 **集合** 。不同于数组等其它数据结构，哈希集的内容不会重复。哈希集被用于交并补集合运算，并且能快速判断其是否包含有某个数据。同样，哈希集查询数据的速度远高于数组遍历。
### 常见的哈希表实现方法
在从哈希表里使用一个 Key 查询数据时，这个 Key 的哈希值被计算出来。这个哈希值被当作数组的 **索引** 来直接定位「桶」。读到这里，大家肯定会想到 Key 的哈希值应该是一串看似毫无规则的、位数很多、数值明显大于「桶数组」大小的值，事实上就是如此，绝大多数情况下哈希值会超出数组下标。此时可以使用各种方式缩短哈希值的长度来使其不超出数组长度，一个典型的做法是强制使桶数组长度符合 2 的 N 次方大小（实际需要的桶没那么多时则插入空桶，有时根据可能存储的数据的大致数量来预分配桶数组的大小），然后对哈希值做 **位运算** ，只取其低位来作为数组 index，就不会超出桶数组下标了，然后使用这个 index 直接定位桶。这个桶里就有我们需要查询的数据，遍历匹配其元素内容即可得到我们需要的数据；或者我们如果要插入数据到哈希集/哈希表，则也是插入到这个桶里。
至此，一个最基本的哈希表/哈希集就实现了。
## 给哈希表设计适合其使用的哈希函数
数据结构中的哈希表需要的哈希函数 **并不需要很讲究密码学安全** ，但是需要它足够简单，足够快，并且尽可能还是要减少碰撞概率的，但是 **并不讲究极端的哈希碰撞避免概率** 。
### 使用「学校班主任管理一个班级」的虚拟场景具体描述什么是哈希算法
在 *某学校* 的场景里，班主任负责管理班级学生。这里面的 *班级* 相当于 **数据的容器（桶）** ， *班主任* 相当于 **负责管理容器数据的软件** ，而 *学生* 则相当于 **容器里的数据** 。由于某种原因，比如班级里大量的人重名了，有很多个「李华」和「张三」，为了能根据学生的身体、面部特征等区分每一个人 **（为了给一串串不同长度不同内容的数据进行「摘要」）** ，班主任开始对学生 **起外号** 。这个起外号的过程就叫哈希计算。
首先我们假设每个同学的体型、外貌、生活习性等都具有非常鲜明的差异（以便于确保班主任起的外号不容易重复），那我先举三个例子：
- 比如某同学每个月才洗一次澡，还每天都喷很多廉价香水，班主任计算了一下，觉得可以根据他的气味给他起外号叫「深海鱼人」。
- 比如某同学有个习惯，无论什么场合，只要看见有人错误使用「的地得」这三个助词，他都会将其指出来。班主任给他起外号叫「的地得警察」。
- 比如某同学喜欢二次元，上衣印了个长着一双难以区分其为兔耳朵还是驴耳朵的二次元可爱女孩子的图画，下身印着「RHODES ISLAND」，班主任给他起外号叫「未成年博士」。
然后要给学生分班，此时，班主任按外号的字数来分班，比如「三个字的」「四个字的」「五个字的」。
班主任给在计算机上，给每人创建了一个文件夹，并对每个人拍了张照存入文件夹，然后文件夹的名字就是这个学生的外号。在此时，班主任已经完成了他对数据的摘要处理，并完成了哈希集的构建。
### 尝试设计哈希函数
#### 设计1
```
size_t Hash(const char* data, size_t data_size)
{
size_t ret = 0;
for (size_t i = 0; i < data_size; i++)
{
ret += data;
}
return ret;
}
```
这应该是最简单的哈希函数了。全部数据加起来求和。缺点很明显：`data` 里的字符顺序的变化不会改变哈希值，这就导致了极高的碰撞率。它无法区分单词 `reverse` 和 `reserve`，会生成相同的哈希值。因此我们需要让哈希值的计算 **考虑数据的顺序** 。
#### 设计2
```
size_t Hash(const char* data, size_t data_size)
{
size_t ret = 0;
for (size_t i = 0; i < data_size; i++)
{
ret += (size_t)data << ((i % sizeof(size_t)) * 8);
}
return ret;
}
```
我们把数据左移了一下再加入到哈希值里，就能体现出数据的顺序性了。但是这样的哈希算法依然有个缺陷：它只能一次性接受数据，然后进行计算。它不能对很长的数据进行分段的计算，因此需要改进。
#### 设计3
```
size_t Hash(size_t old_hash, const char* data, size_t data_size)
{
size_t ret = old_hash;
for (size_t i = 0; i < data_size; i++)
{
ret <<= 4;
ret += (size_t)data;
}
return ret;
}
```
此处的改动是先读取旧哈希值拿来计算，每次计算时使哈希值左移 4，这样的话，先来的数据就会被移动到高位，然后再加上后来的数据。但是这个算法 **还是有问题** ：对于两个数据，如果第二个数据足够长且尾部经过了特殊的处理比如它的尾部和第一个数据相同，那么它就会 **把所有的先来的数据都挤掉，导致哈希碰撞** 。
#### 设计4
```
size_t Hash(size_t old_hash, const char* data, size_t data_size)
{
size_t ret = old_hash;
for (size_t i = 0; i < data_size; i++)
{
size_t high = ret >> (sizeof(size_t) * 8 - 4);
ret <<= 4;
ret |= high; // 此处相当于执行了一个 ROL(4)
ret += (size_t)data;
}
return ret;
}
```
使用向左滚动 4-bit 的方式保留了高位，再加上数据。这个哈希算法是一个比较理想的哈希算法， **对字符串应该是足够好用的** 。
### 尝试针对非字符串设计哈希函数
非字符串的情况下，我们的数据可能可以不以 `char` 为单位进行计算。`char` 太短了，每次进行那么多次的计算，只为处理一个 `char`，这样会让你的哈希函数效率降低。
此处例举一个以 `int` 为单位的哈希函数：
```
size_t Hash(size_t old_hash, const int* data, size_t data_count)
{
size_t ret = old_hash;
for (size_t i = 0; i < data_count; i++)
{
ret = (ret << 4) | (ret >> (sizeof(size_t) * 8 - 4));
ret += (size_t)data;
}
return ret;
}
```
好像也差不多，只不过每次处理的是一个 `int`。
## 结论
给哈希表/哈希集等数据结构设计的哈希函数需要考虑到以下几个方面：
- 哈希值要保留数据的顺序性
- 哈希算法要能分块处理数据
- 哈希算法要能在计算较长数据时保留早期加入哈希计算的数据的痕迹
最主要的：哈希表/哈希集使用的哈希算法要快。因此避免以下行为：
- 无意义的乘法和无法解释的魔法数字的使用
- 任何除法运算
- 对任意数据仅使用适用于字符串哈希计算的哈希算法 lichao 发表于 2024-2-26 16:58
的确世上不存在100%的概率，用的多库的确实也不可能100%可靠，不过从概率上还是比用的少的库好点，这些都 ...
结论不就是 CRC32 在我们这的服务器上比 SHA1 慢，SHA1 比 MD5 慢么？运行环境 曙光X640 服务器，Ubuntu 最新版系统，使用语言 JDK8（项目要求），以 Docker 容器方式部署，我们公司的架构师在测试数据库性能的时候发现的。
我举得例子里 gcc 那几个 bug 你不觉得严重么？你到底用过几次 gcc 哦？这么出名的大项目能有这么严重的 bug，那么一个算法也可能隐藏着重大 bug 也是有可能的吧？
zlib/zstd 你真的就确定第三方在使用这俩库的时候就已经保证了正确性和多线程没问题的呢？另外你有没有想过有一种可能：facebook 的服务器是 *nix 服务器，而 *nix 的传统，就是喜欢使用 *进程池* （*nix 是不区分进程和线程的，此处的“进程”指的是内存空间不共享的进程），而使用 *进程池* 就会避开它的多线程问题，再加上很少有人在 Windows 上使用 zstd，所以它被“你的第三方”认定是没有 bug 的了。
的确世上不存在100%的概率，用的多库的确实也不可能100%可靠
开源社区讲究的就是谁发现 bug，谁修复 bug，开源算法也一样。有的人喜欢参与推进开源项目，贡献代码修补错误或者增加新的功能，有的人则是拿来主义，而且基本上商业开发者在使用开源项目的产品的时候都是拿来主义，因为你在混工作的时候，其实你只会想给你的老板交差，除非在此之上你还有余力去参与开源项目的推进，否则只要能编译通过、通过代码审计、要不就再来个 code linting 审查。只要你的老板发现不了 bug，只要你的服务能顺利上线，甚至某些公司的服务以不合规的方式上线，只要你的老板满意，你就不会再做其它的多余的事情。否则要是被老板发现你工作强度不饱和，你会遇到职场问题。
而参与开源项目/开源算法的人的能力水平参差不齐，有工作了很多年的程序员，有业余爱好者，有还没毕业的大学生，甚至还有众多初中生、高中生甚至小学生，有的甚至连基本的计算机编程能力都没有，但是却喜欢瞎几把微调各种参数配置。越是用得广泛的开源项目，想要往里面拉屎的人就越多。不能迷信开源大法，也不能迷信“维护得久的算法”，因为对于一个算法/软件库的开发者而言，鬼知道你家公司生产环境会使用哪个版本的算法实现，以及你的生产环境机器是什么样的架构。 misakarinkon 发表于 2024-2-26 16:44
用的广和写的早，生命周期长，跟它快不快没什么关系吧
不同用途和不同思路写出来的同一个算法实现，由于考虑的因素不同，不能单纯因为它经过了多年的维护而认定它“性能一定是最佳的”。 感觉用乘法还是比较有意义的吧，根据二进制的特性只要乘的是一个奇数就不会有信息丢失，可以完全还原，但又类似非对称加密那样需要乘以另一个不同的奇数才能还原回来。 防止碰撞的同时又让hash算法简单的办法之一是，双hash，两种非常简单但是不同的算法 YY菌 发表于 2024-2-19 20:39
感觉用乘法还是比较有意义的吧，根据二进制的特性只要乘的是一个奇数就不会有信息丢失，可以完全还原，但又 ...
hash做的太复杂不切合实际使用，和加密传输性目的性不同，前者主要目的是准确性，防止处理异常不可预知的数据，后者是为了数据安全性，前者更注重自动化处理，后者注重于使用者隐私 AyalaRs 发表于 2024-2-20 02:26
防止碰撞的同时又让hash算法简单的办法之一是，双hash，两种非常简单但是不同的算法 ...
这个不就相当于提升hash值的位宽吗？计算两个32位hash跟计算一个64位hash没啥本质区别吧。 AyalaRs 发表于 2024-2-20 02:33
hash做的太复杂不切合实际使用，和加密传输性目的性不同，前者主要目的是准确性，防止处理异常不可预知的 ...
一个乘法不复杂啊，但是可以降低碰撞概率嘛。 本帖最后由 AyalaRs 于 2024-2-21 01:24 编辑
YY菌 发表于 2024-2-20 23:50
一个乘法不复杂啊，但是可以降低碰撞概率嘛。
你实际跑一下性能就知道乘法和加法与位运算差多少性能了，找个4mb的文件测试下就知道了，要看首次执行时间
俩不同算法hash和提升位宽差别很大的，最简单的例子缺乏数据顺序的检测的hash算法，提升位宽依然无法检测数据顺序
.data
data1 dd 0,0,0,0,'a',0,0,0
len1 equ $-offset data1
data2 dd 0,0,0,0,0,'a',0,0
len2 equ $-offset data2
data3 dd 0,0,0,0,0,0,0,0c2h,0,32 dup(0)
len3 equ $-offset data3
.code
hash proc uses esi edi ebx key,src,n
mov ecx,n
mov ebx,key
mov esi,src
xor edi,edi
.while ecx >0
lodsd
add edi,eax
add edi,ecx
rol ebx,1
add ebx,eax
dec ecx
.endw
mov eax,ebx
mov edx,edi
ret
hash endp
_main proc
invoke hash,0,offset data1,len1 / 4
invoke crt_printf,$CTA0("%08X,%08X\n"),eax,edx
invoke hash,0,offset data2,len2 / 4
invoke crt_printf,$CTA0("%08X,%08X\n"),eax,edx
invoke hash,0,offset data3,len3 / 4
invoke crt_printf,$CTA0("%08X,%08X\n"),eax,edx
invoke crt_system,$CTA0("pause")
ret
_main endp
运行结果如下
00000308,00000085
00000184,00000085
00000184,0000041F
请按任意键继续. . .
.data
data1 dd 0,0,0,0,'b',0,0,0
len1 equ $-offset data1
data2 dd 0,0,0,0,0,'b',0,0
len2 equ $-offset data2
data3 dd 0,0,0,0,'1',0,0,0
len3 equ $-offset data3
运行结果
00000310,00000086
00000188,00000086
00000188,00000055
请按任意键继续. . . AyalaRs 发表于 2024-2-21 01:21
你实际跑一下性能就知道乘法和加法与位运算差多少性能了，找个4mb的文件测试下就知道了，要看首次执行时 ...
乘法和位运算性能的差别我是知道的，但要降低碰撞率的情况下还是有必要用到的。反正性能和碰撞率总得二选一吧。
你说到“缺乏数据顺序的检测的hash算法，提升位宽依然无法检测数据顺序”，那两次缺乏数据顺序的检测的hash算法，不依然还是无法检测数据顺序吗？ 本帖最后由 lichao 于 2024-2-22 09:45 编辑
实际的App中大部分都是用MD5和SHA1，少数用SHA256及更高，或者套个HMAC，目前还没遇到过自己开发哈希算法的，可能实际中也并没有必要。毕竟设计这些算法需要很深的密码学知识，这样才能兼顾安全性和速度。如果设计出来还不如CRC或者SHA1等就没有意义。追求速度用CRC，追求安全用SHA1。自己设计的哈希算法。如果项目不对外自己用是没啥问题的，否则万一别人把你的算法误用到线上产品可能会造成一些问题。
不过加解密算法却有自己开发的，比起设计哈希算法，设计加密算法更有意义，App大部分还是采用大部分是RSA/AES等常规算法，少数App魔改已有算法，比如小红书魔改AES，少数App纯自研的比如DY的Gorgon。
YY菌 发表于 2024-2-22 09:19
乘法和位运算性能的差别我是知道的，但要降低碰撞率的情况下还是有必要用到的。反正性能和碰撞率总得二选 ...
俩算法只要分布不同，结果对数值变化就是敏感的，就算俩算法都是无法检测顺序的 lichao 发表于 2024-2-22 09:24
实际的App中大部分都是用MD5和SHA1，少数用SHA256及更高，或者套个HMAC，目前还没遇到过自己开发哈希算法的 ...
SHA1 不安全，不过关键是你说追求速度用 CRC，实际上 CRC 的速度比不过 SHA1，而 SHA 1 的速度比不过 MD5，不信你可以自己测测试试。
另外，请你仔细审题。本文内容描述的是数据结构使用的简单哈希算法，而不是信息安全使用的安全哈希算法。什么是数据结构呢？给你打个比方：C++ 的 std::unordered_set 和 std::unordered_map，以及 Java 的 HashMap，就是这类的数据结构，作为容器，它组织数据需要一个简单哈希算法，本文描述的就是这样的哈希算法的设计，请了解。
顺便展示一下代码，简单体现一个针对自定义类的哈希算法的设计和对应数据结构的应用：
如图所示，这是我的自定义类，其中的 vec3 和 vec2 是 glm 库提供的，你可以理解为 vec3 里面存储了一个 float x, y, z;，而 vec2 里面则没有 z 成员，只有 float x, y;
相当于，我的自定义类展平了就是 8 个 float 值。
这是这个自定义类的哈希算法，这是给数据结构用的，因此要求就是计算要快，哈希值要能体现数据的顺序性。这里我调用了我的库里面的 UIntHash::HashInts()，这个函数是用来给 int 类型的数组做简单哈希计算的，而我将我的自定义类的指针直接转换为一个 int* 类型，以便于让 UIntHash::HashInts()处理。在这个过程中，我将这个 由 8 个 float 构成的数据 直接 视为 8 个 int 构成的数组 来处理，能这样做是因为 float 和 int 长度相同。
你可能会注意到有个 HashShifts 参数，这其实是一个 constexpr int 值，也就是一个常量定义，这里它的值目前是 8。它使我可以微调位移哈希值时使用的位移量。
请看 UIntHash::HashInts() 的实现：
它就是典型的针对 int 的简单哈希计算函数，使用了 ROL() 操作和加法操作。
那么我把这个自定义类用到了哪里呢？请看以下截图：
这是我的三维建模软件库的类，上文中的我的“自定义类”其实是三维模型的顶点数据，每三个顶点表示一个三角形面片。
你再注意看我的“自定义类”的内容：
vec3 Position; // 顶点位置
vec2 TexCoord; // 顶点贴图坐标
vec3 Normal; // 顶点法向量
是不是发现其中的内容都是三维建模需要用到的？
注意看 std::vector<ModelerVertex> Vertices; 这个成员，我使用 std::vector 组织我的顶点数据，但是在建模的过程中，很容易出现有大量重复信息的顶点被加入到场景里，需要去除重复；因此我需要改变存储的形式，使用索引值来表示对顶点信息的引用，这样我在导出 Mesh 数据的时候就不会有一个大的内存使用量峰尖。
其中的 std::unordered_map<ModelerVertex, int, ModelerVertex::Hash> VertIndexer; 用于索引顶点数据，利用它，我可以通过提供顶点数据来获取已有的索引值；或者编入新的索引值。这个过程中，std::unordered_map 会利用我提供的哈希函数快速索引到它里面的桶，然后得到索引值数据。
在这样的使用场景里，安全哈希算法比如 CRC、SHA、MD5 等进行的大量的计算就显然很多余了。
lichao 发表于 2024-2-22 09:24
实际的App中大部分都是用MD5和SHA1，少数用SHA256及更高，或者套个HMAC，目前还没遇到过自己开发哈希算法的 ...
校验和算hash算法么，如果按分布要求可能不算，校验和，移位校验和，补位校验和，这些的分布都不算好 0xAA55 发表于 2024-2-22 10:46
SHA1 不安全，不过关键是你说追求速度用 CRC，实际上 CRC 的速度比不过 SHA1，而 SHA 1 的速度比不过 MD5 ...
数据储存优化么，可以考虑用字典 AyalaRs 发表于 2024-2-22 12:04
数据储存优化么，可以考虑用字典
例子上的 std:unordered_map 就是使用哈希表的字典（无序 map），有序字典（根据 Key 的大小比对进行排序）则是 std::map，内部使用红黑树算法。 本帖最后由 AyalaRs 于 2024-2-22 16:50 编辑
0xAA55 发表于 2024-2-22 14:16
例子上的 std:unordered_map 就是使用哈希表的字典（无序 map），有序字典（根据 Key 的大小比对进行排序 ...
我不确定你的key使用时的作用，也不知道你对数据是否进行了等距排布，一般来说生成数据和使用数据的时间是不对等的，比如制作游戏地图和角色模型，生成数据的时候可以慢些，但是使用数据的时候要快些，
生成数据时：计算hash，求模得出(一次函数hash=ax+ b）分布图，再进行一次排序映射得出等距分布得出章(hi)节(lo)
使用数据时：直接根据关系定位数据，数据=数据表->章->节[数据大小]，或者数据=数据表[章][节][数据大小]
如果没等距排布，就需要使用查找树来储存，使用数据的时候效率会相对降低 AyalaRs 发表于 2024-2-22 16:20
我不确定你的key使用时的作用，也不知道你对数据是否进行了等距排布，一般来说生成数据和使用数据的时间 ...
1、Key 就是建模用的顶点数据，作用是找出相同顶点数据在向量（动态数组）里的 index。
2、你说的对数据进行等距排布，指的是哈希表组织数据的方式吗？C++ 的 std::unordered_map 使用桶数组排布数据，是等距的。我使用的哈希表正是 C++ 自带那一套。本文所述全部哈希表/哈希集都指的是高级语言（C++/Java/Python/JS等）自带的数据结构。
3、C++ 的 std::unordered_map 在“使用”数据时确实是差不多按照你那一套实现的。
4、你说的查找树，在 C++ 是 std::map。
5、正常情况下我都会使用 std::unordered_map，因为它在多数时候比 std::map 快。
0xAA55 发表于 2024-2-22 19:25
1、Key 就是建模用的顶点数据，作用是找出相同顶点数据在向量（动态数组）里的 index。
2、你说的对数据 ...
不太一样，我说那个初始化效率低，占用空间低，运行时候执行效率高，范围查找效率高，有序，动态修改能力弱，特别适合存只读数据，一般用数组存，属于无序map和map的平衡的产物，把数据扩展成树就是带hash的同时满足数组结构的树，但是占用空间会变多，如果等距排布，不排序则接近无序树
初始化的时候产生一个hash，等距排布的时候会生成一个新的hash,初始化时候的hash是无规律的，等距排布之后的hash是完全线性散布的
AyalaRs 发表于 2024-2-22 19:52
不太一样，我说那个初始化效率低，占用空间低，运行时候执行效率高，范围查找效率高，有序，动态修改能力 ...
我这边的不是游戏开发，而是建模软件开发，所谓“初始化”主要是加载建模构件库、材质库，所谓“执行的时候”是在拿到“建模要求”的时候根据其要求来创建多边形。建模过程中，已经创建了的多边形要被复用。
使用场景与你描述的完全不同。此外，我在截图例子的时候，删除了所有的 OpenMP 并发处理语句，实际上我的这个软件是多线程并发处理的。
实际运行过程中，我的软件以 JNI 的形式由 Java 后端程序（Springboot 框架 + Docker 容器封装）并发调用，生成出来的 Mesh 数据在经过压缩后传输到微信小程序里面使用。
因此对于需要复用的多边形数据，我使用顶点 index 描述这些数据，然后做成 std::vector（C++ 的动态数组），成为一个个可复用的多边形数据。再把这些多边形数据再使用哈希集的方式来管理，使用字符串的多边形名称作为 Key，然后多边形数据作为 Value 来组织数据。微信小程序前端使用 three.js 加载模型后，需要通过判断字符串值来判断这个多边形属于哪一类，从而对多边形进行各种不同的分组处理。此时的 Mesh 信息同时包含两样内容，一份是无重复数据的顶点数据，一份是描述多边形的顶点 index 数据，在移动端 WebGL 上渲染显示时，这两组数据全部丢进 GPU 显存里使用。 0xAA55 发表于 2024-2-23 09:52
我这边的不是游戏开发，而是建模软件开发，所谓“初始化”主要是加载建模构件库、材质库，所谓“执行的时 ...
其实本质问题是需不需要改，以及在储存，运行内存，以及运行效率的取舍
对于模型复用，改变模型大小是否定义为同一模型，如果是就需要储存比例，牺牲执行效率，如果不是就需要扩展数据表，生成新的索引集表示不同比例的模型
如果模型修改是频繁的，那么就不需要实时扩展表，操作时只使用标准数据，最后只会在保存时扩展数据表
如果模型修改不频繁那就可以存储比例来保存模型扩展信息，数据表不必发生变化
页:
[1]
2