如何把guid发散（或收敛）为32位（或64位）int

guid据说是绝对不会重复，虽然我一直有点担心，但是基本也按这么使用了
但是有些场合，还是需要32位（或64位）int做关联，所以希望能有一个函数：
把guid发散（或收敛）为32位（或64位）int
同时，撞车的可能尽量的低
（不撞车是不可能的，128位信息缩略为32或64位，肯定有不同的guid被对应到相同的int了）
简单写了一个反复xor（顺便加点循环移位）的函数
结果，32位时，大约10万个guid就会遇到撞车了
有没有更难撞车（上千万的guid才遇到int32结果相同）的算法？
这也是一种hash算法吧GUIDhash发散算法

解决方案 »

  1.   

    {B0B21AFF-D6D9-4B50-B63D-A3519BBBC105}0DC25B46
    {20C31952-EE62-4521-BA21-F5832DBE0DAA}18C424030DC25B46{66A2F9C5-2854-4239-8E2C-EAF8E8A683B9}63C89658
    49153{38DDC5D5-BED6-46AA-85B5-2DD61799B177}34D82AF263C89658{527D9497-3408-4B43-BA17-CAC666883C50}D8D75357
    {B35F102F-523B-4000-AB2E-F3CBD0B7A77D}04451F15D8D75357{66A2F9C5-2854-4239-8E2C-EAF8E8A683B9}63C89658
    49153{38DDC5D5-BED6-46AA-85B5-2DD61799B177}34D82AF263C89658
    上面是hash为64位时，后32位撞车的例子下面是hash为32位时，撞车的例子
    153096——测试的guid总数
    {C3F9BD70-81D3-4CEC-859F-5820A04A0B00}E1042564
    {EFD6D8FB-D8D5-4DEC-AFA9-588C6D8B78F4}E1042564{8AD2CE8A-DC31-40AB-9887-2F1E2CA6D844}258A51CD
    {7C294294-E8E6-47AF-845E-BF3131C0C990}258A51CD{5A9A1212-1E52-44B3-B5DC-FFB228A27D09}3455C213
    {8D3E8E43-63ED-4EA3-BD8E-7B573C8D32FD}3455C213
    {93263DDF-DA44-48B7-8EF0-F7164ECD46E1}E6FE51BA
    {6752E762-4134-4CAE-B5B7-EDA5A9D9CF09}E6FE51BA{CAB0FBC5-ED89-41AB-81AB-54B365051BE2}24CFBC27
    {5962B36F-FC1E-484A-B439-A522415A4B59}24CFBC27{E206FFCB-A58F-4320-8BDF-B26C03718080}D756366B
    {BADF7BEF-EA7F-4217-89FB-4B987EE4370C}D756366B{6632F0E2-9A41-4232-99CF-B4FE86ECE57E}114CC86A
    {856EA4F7-4DF9-41F8-A448-4ABF15B9243C}114CC86A166494——测试的guid总数
    {B3E0CA2B-49DC-4961-9DBF-B3DF8CFF903F}35FA7BC1
    125191{A4E8EBE4-293E-430E-B28A-A605BA6070AB}35FA7BC1#164554——行首和行尾的数字是这2个guid的出现顺序{966FAC93-3DF8-44BD-AFC2-1F5CE82E42C8}302B3916
    128249{781C70AF-1A71-47F3-AB8D-9EF178068867}302B3916#157710{397CCB49-F62D-4328-AC3D-1BC4FD69341A}4E27EB26
    6462{7126E992-F229-4A46-8AF9-2DD8782433A4}4E27EB26#95023{41D8F102-D7B0-4F9B-8589-F6C3B2AA2357}87F1495E
    23684{7890C2D9-0A22-4C38-88D6-42123C0A8748}87F1495E#41440{E5B67072-0CF6-427D-A1EE-B982D9210984}4A660CA8
    21505{05055230-0C99-4C08-8E4D-3D392C3830EE}4A660CA8#22797
      

  2.   

    {B0B21AFF-D6D9-4B50-B63D-A3519BBBC105}
    用啥算法求出的 0DC25B46 ?
      

  3.   

    搬张板凳来good good study，day day up 
      

  4.   

      CreateGUID(g);  pb:=@g;
      p:=Pint(pb);
      d:=p^;  for i:=1 to SizeOf(Tint)-1 do
      Begin
        inc(pb,SizeOf(Tint)); p:=Pint(pb); t:=p^;
        d:=d xor ror(t,i*3);
      End;
      s16:=Format('%.8x',[d]);
      

  5.   

    for i:=1 to SizeOf(Tguid) div SizeOf(Tint)-1 do
      

  6.   

    {569022F1-D42D-48E8-B78B-E13CE069CAFF}9D57E450
    {EE680DBB-33F3-412C-A80F-4B0DCE050494}9D57E450
      

  7.   

    你是否要求特定的GUID映射为特定的int64/int？如果不是的话可以引入某种随机量参与运算。
      

  8.   


    不太明白？需求是把 原来用guid作为唯一性的id 的做法，改为由int32作为唯一性的id
    因为不同的机器、系统可能并行地在生成guid，所以要求这些guid的对应int32也不能相同
    否则靠这些int32关联就错乱了但是guid的总个数不会太多，最多上万
      

  9.   

    意思是每次输入某个GUID，输出的int64/int是否是固定的？每次都是它？这种算法是多对1的关系，产生的碰撞概率大一些，如果对于输入的同一GUID，算法每次产生的输出不一定相同，碰撞的概率就小一些。
      

  10.   

    每次输入某个GUID，输出的int64/int是否是固定的？
    对如果不同，就失去了对应的价值
      

  11.   

    你试试这个：function PackGUID64(const G: TGUID): int64;
    asm
      movdqu xmm0,[eax]
      pshufhw xmm1,xmm0,0c9h  // word order 3 0 2 1 of high 64-bit
      pshuflw xmm2,xmm0,72h   // word order 1 3 0 2 of low 64-bit
      psrldq xmm1,8
      psllq xmm1,1
      psrlq xmm2,1
      pxor xmm1,xmm2
      movd eax,xmm1
      psrldq xmm1,4
      movd edx,xmm1
    end;function PackGUID32(const G: TGUID): longint;
    asm
      movdqu xmm0,[eax]       // dword order 3 2 1 0
      pshufd xmm1,xmm0,39h    // dword order 0 3 2 1
      pshufd xmm2,xmm0,4eh    // dword order 1 0 3 2
      pshufd xmm3,xmm0,93h    // dword order 2 1 0 3
      pxor xmm0,xmm1
      pxor xmm2,xmm3
      psllq xmm0,1
      psrlq xmm2,1
      pxor xmm0,xmm2
      movd eax,xmm0
    end;
      

  12.   

    谢谢不过32位时，123497个guid里，也出现了2对撞车的：
    !32!{760A3509-4BFF-45EF-AF12-5CD78695F2E1}FC9DBE78
    23420{25EC5239-D754-42FA-880B-0257CD626332}FC9DBE78#113472!32!{C796FA6D-553B-45A3-8EDB-F95B87BD78B9}752BEDA8
    16872{B9DC4A0E-F1E3-4916-969E-A48D73AAD9A4}752BEDA8#103241
      

  13.   

    个人感觉貌似在第几个撞车是几率问题，这次 在 10万个左右出现第一个撞车，下次从头开始生成GUID时可能在1000个左右就出现第一个撞了...    应该是在某一较大范围内 出现撞车的次数基本一致，但是第一次撞车出现在何处却是不定的，和具体生成的GUID有关...   不知是否是这样，如果是这样，那就无解了...
      

  14.   


    那你用PackGUID64的低32位结果看看会不会好一些，理论上来说，洗牌粒度越小效果就越好，按word洗牌就比按dword洗输出结果分布均匀，按byte或者bit洗就更好了。
    另外，14楼说的很有道理，你最好把用到的整个GUID范围，比如1000万个，都测试一下，这样才能比较出算法的好坏。
      

  15.   


    不太明白？需求是把 原来用guid作为唯一性的id 的做法，改为由int32作为唯一性的id
    因为不同的机器、系统可能并行地在生成guid，所以要求这些guid的对应int32也不能相同
    否则靠这些int32关联就错乱了但是guid的总个数不会太多，最多上万想从guid生成极难重复的int32，基本上不用考虑了。要用int32做为主键，全局计数器是最佳的办法，Oracle、SQLServer、postgresql都有相应的功能。
      

  16.   


    不太明白？需求是把 原来用guid作为唯一性的id 的做法，改为由int32作为唯一性的id
    因为不同的机器、系统可能并行地在生成guid，所以要求这些guid的对应int32也不能相同
    否则靠这些int32关联就错乱了但是guid的总个数不会太多，最多上万想从guid生成极难重复的int32，基本上不用考虑了。要用int32做为主键，全局计数器是最佳的办法，Oracle、SQLServer、postgresql都有相应的功能。系统可能在不同位置有自己的数据库，最终可能合并在一起
      

  17.   


    愣了一下才明白你是什么意思。以前我们遇到过类似的情况。在做一个项目时，我们把所有没有明显关键字的表和需要做为外键的表都设置了一个自增长字段作为主键。后来由于网络条件的限制，客户要示我们提供一些单机版的子系统，在数据采集时将数据保存到本地数据库，回来后再导入主数据库，结果在导入数据时遇到了大麻烦。由于数据库结构不能轻易改动，最后我们专为导入数据做了很多个导入程序，将客户数据库中的数据读入内存并对象化，然后把它们当作新增对象来写入主数据库。从那以后，我们在遇到需要给表额外增加主键字段时，一概选择GUID。想把GUID缩短长度又保持低冲突概率是很困难的，重新设计一个低冲突的随机发生器可能比它更容易。如果一定要这样做，你可以试试用DES：DES( DES(GUID[1]) xor GUID[2] )
    GUID[1]和GUID[2]分别代表它的高64位和低64位。
    如果数据库中有128位整数就好了，我们后来的数据表主键很多都是char(22)，就是把GUID进行64进制编译后再写进数据库。
      

  18.   

    guid转64位，估计就很难撞车了。
    只是bigint还是大了一点，char(22)就更大了
    因为这类记录（各地的系统生成的流程模板里面的节点）的数据量总体都不会很大，希望int32能唯一就最好了