c - 用于数百万个UINT64 RGBZ图形像素的最快HASH算法

Question

Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？ Update the question，所以它是 on-topic，用于堆栈溢出。
                        
                        4年前关闭。
                                                                                            
                
        
在我尝试对数百万个48位RGB像素进行处理的3种领先的哈希算法中，性能差异很小。 Yann Collet的xxHash碰撞最少，时间乘积最低（不良）*碰撞（不良）：

Time=0.454 sec  XXH32_HASH_RGB        0.2486% Hash Collisions  =>     
1       time*coll=1.6258  << Lowest Time * collisions
Time=0.490 sec  fasthash32_HASH_RGB   0.2554% Hash Collisions  => 
1.0273  time*coll=1.7878 
Time=0.460 sec  MurmurHash3_x86_32    0.2542% Hash Collisions  => 
1.0225  time*coll=1.6421

xxHash-快速哈希算法
Yann Collet版权所有（C）2012-2015

MurmurHash3由Austin Appleby编写，并在公众场合公开发行...

fasthash32 // Merkle-Damgard构造的压缩函数。

我正在忽略PixelMunchingMonster哈希吗？

每种算法一次从内存数组中获取6个字节的数据，并输出32位值。

for(pidx=0; pidx < num_pix; pidx++)  {  // II is uint16 *, need 3/pixel
  time_event(E_XXH32_HASH_RGB, tsa, E_TIME_EVENT, debug);  // HASH! HASH!
  //MurmurHash3_x86_32((const void *)(fmem+pidx*3),6,seed,(void *)(&h32));
  //h32=(unsigned int)fasthash32((const void *)(fmem+pidx*3), 6, seed);
  h32=(unsigned int)XXH32((const void *)(fmem+pidx*3), (size_t) 6,seed);
}

针对win7 / 64编译的GCC，针对我的金属Intel 2700k进行了微调：

gcc -D__USE_MINGW_ANSI_STDIO -O4 -ffast-math -finline-functions -m64 -Ofast -march = corei7-avx -mtune = corei7 -Ic：/ bin / xxHash-master -Lc：/ bin / xxHash-master c：/ bin / stddev.c -oc：/bin/stddev.g6.exe

=================================================

@ BrianP007您的意思是99.76％吗？如果是这样，或者您的计算有问题，或者您非常幸运。即使具有理想的统一哈希函数，217MB / 48bpp〜= 36M像素也应仅产生99.58％的非冲突。 – MooseBoys 1小时前



0.2486％哈希冲突：89877 Diff_Color_Same_Hash / 36152320 pix

我对所有3,600万像素进行哈希处理，将RGB的48位压缩为32位哈希，然后在每次计算哈希时增加哈希数据值。

一共有3种情况，共计36152320像素（7360 * 4912）

A）唯一像素，一击=> 27558538

B）2个以上像素上的相同颜色=> 8503905

C）相同的哈希，不同的RGB ==碰撞！ => 89877

来自badass传感器的量子随机数据是唯一的解释！

uint16_t * fmem是内存中的RAW文件BLOB。 PIDX是PIXEL_InDeX，0-36M
Num_Pix = 36152320

该代码是白痴证明。 ew！

for(pidx=0; pidx < num_pix; pidx++)  {  
  h32=(unsigned int)XXH32((const void *)(fmem+pidx*3), (size_t) 6,seed);
}

我使用LOST魔术数字4815162342作为种子。我现在在名单上吗？

================================================== =====

冲突计数代码修复和新的冲突/性能比率...

我在碰撞处理代码中发现了一个错误。我只看着成对的散列。这对于将唯一哈希映射到恰好一个像素/ RGB的情况以及由于碰撞或共享该哈希色的恰好2个点而出现2次相同哈希的情况非常有用。

对于给定哈希的3个实例，第三个实例将在下一个循环中作为唯一值滑过。

解决方法是向下钻取哈希值的最后一次出现，并将RGB集映射映射到Pixel_IDs，将其映射到哈希映射到唯一函数。

如果它为具有该哈希值的每个像素返回1个唯一的RGB，则不存在冲突：结果：unique_colors ++，冲突未更改

对于N> 1 RGB的返回=> unique_colors + = N，碰撞+ = N

因此，如果4个像素具有共同的哈希值和2种不同的颜色（1、3中的一种，另一种或2和2没有区别），则结果是2种碰撞和2种不同的颜色。

fasthash32                     => 0.6474% Hash Collisions; 0.439, 0.440, 0.440 sec
XXH32                          => 0.6296% Hash Collisions; 0.439, 0.439, 0.438 sec  
MurmurHash3_x86_32 => 0.6448% Hash Collisions; 0.466, 0.435, 0.434 sec

Murmur散列可能在速度上略有领先，但是XXH32的碰撞较少，所以我选择了XXH（以尽量避免混淆）

对于额外的信用，InLining指令哪个更有效？

XXH和Murmur对于““ FORCE_INLINE”不兼容

I:\br3\pf.249465> gcc -D__USE_MINGW_ANSI_STDIO -O4 -ffast-math         -finline-function
s -flto -m64 -Ofast -march=corei7-avx -mtune=corei7 -Ic:/bin/xxHash-master -Lc:/
bin/xxHash-master c:/bin/stddev.c -o c:/bin/stddev.g6.exe
In file included from c:/bin/bpb.h:8:0,
                 from c:/bin/stddev.c:44:
c:/bin/xxHash-master/murmur3.c:16:0: warning: "FORCE_INLINE" redefined
 #define FORCE_INLINE __attribute__((always_inline)) inline
 ^
In file included from c:/bin/bpb.h:5:0,
                 from c:/bin/stddev.c:44:
c:/bin/xxHash-master/xxhash.c:90:0: note: this is the location of the     previous d
efinition
 #    define FORCE_INLINE static

注意：在测试另一个.c / .h行时，从项目包含文件中注释掉每一行，同时测试另一行，以便每个行都可以建立自己的方式。

最佳答案

如果您的RGB值表示跨越每个通道可表示范围的很大一部分的实际图像数据，则较低的位应该合理地分配且不相关。结果，低位的简单连接应该产生很少的冲突，并且计算起来非常快：

hash(RGB) = (R & 0x7FF) << 21 | (G & 0x7FF) << 10 | (B & 0x3FF);

关于c - 用于数百万个UINT64 RGBZ图形像素的最快HASH算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32192695/

上一篇：c - 调用相同函数时的线程问题

下一篇：c - 在内核模块中，如何知道给定路径是文件还是目录？

相关文章：

performance - apache 服务器达到 MaxClients 设置，考虑提高 MaxClients 设置

散列VS索引

java - 哈希码的理解

创建一个整数数组并以空白结束

c - 如果 C 中出现其他错误

c - 发出 dbus-send 命令后，如何使用 C 调用方法？

java - PackageInfo LoadLabel 性能低下

performance - Pointfree 版本使性能恶化

hash - 将 Rails 参数哈希传递给命名路由的更有效方法

c - C 转换字符 %.8f 有什么问题？

Answer 1

如果您的RGB值表示跨越每个通道可表示范围的很大一部分的实际图像数据，则较低的位应该合理地分配且不相关。结果，低位的简单连接应该产生很少的冲突，并且计算起来非常快：

hash(RGB) = (R & 0x7FF) << 21 | (G & 0x7FF) << 10 | (B & 0x3FF);