上山打老虎 发表于 2021-6-27 13:03:17

DJB Hash Function,也称times33算法, php的实现与分析-算法

  DJBX33A又叫Times33哈希算法的实现与分析
算法:对字符串的每个字符,迭代的乘以33,目的把字符串转换成整数
  公式:   hash(i) = hash(i-1)*33 + str ;
  乘于33是为了减少碰撞重复,简单点理解就是1+2和2+1是一样的,那1*33+2和2*33+1就不一样了。
为什么要用33,因为33是一个素数,能更好的散列,PHP内置的Hash函数用的素数是5381
 
  OK,那我们用php来试一下他的实现
<?php
/*
* DJBX33A又叫Times33哈希算法的实现与分析
* Author: lms <php7在qq.com> QQ:二一九二4238
*转发请注明来源网址http://www.thinkunion.net
*https://blog.csdn.net/weixin_43932088
*/
function hash0($str){
    $hash&#61;0;
    for($i&#61;0;$i<strlen($str);$i&#43;&#43;){
      $hash&#61;$hash*33 &#43;ord($str{$i});
    }
    return $hash;
}
/*上面这个函数中&#xff0c;字符串可以有各种语言字符&#xff0c;长度可以很长&#xff0c;并不利于计算&#xff0c;我们可以用md5转换成32位*/
function hash1($str){
    $hash&#61;0;
    $str&#61;md5($str);
    for($i&#61;0;$i<32;$i&#43;&#43;){
      $hash&#61;$hash*33 &#43;ord($str{$i});
      var_dump($hash);
    }
    return $hash;
}
/*
结果&#xff1a;
int(54)
int(1833)
int(60543)
int(1998021)
int(65934790)
float(2175848122)
float(71802988124)
float(2369498608189)
float(78193454070337)
float(2.5803839843212E&#43;15)
float(8.5152671482599E&#43;16)
float(2.8100381589258E&#43;18)
float(9.273125924455E&#43;19)
float(3.0601315550702E&#43;21)
float(1.0098434131732E&#43;23)
float(3.3324832634714E&#43;24)
float(1.0997194769456E&#43;26)
float(3.6290742739204E&#43;27)
float(1.1975945103937E&#43;29)
float(3.9520618842993E&#43;30)
float(1.3041804218188E&#43;32)
float(4.3037953920019E&#43;33)
float(1.4202524793606E&#43;35)
float(4.6868331818901E&#43;36)
float(1.5466549500237E&#43;38)
float(5.1039613350783E&#43;39)
float(1.6843072405758E&#43;41)
float(5.5582138939002E&#43;42)
float(1.8342105849871E&#43;44)
float(6.0528949304574E&#43;45)
float(1.9974553270509E&#43;47)
float(6.5916025792681E&#43;48)

从结果可以看出&#xff0c;php由于是弱类型的语言&#xff0c;不必声明自动转换类型。
到计算的第六次时int已经不够位数直接变在float型。
*/

function hash2($str){
    $hash&#61;0;
    $str&#61;md5($str);
    for($i&#61;0;$i<32;$i&#43;&#43;){
      $hash&#61;($hash<<5)&#43;$hash&#43;ord($str{$i});
      var_dump($hash);
    }
    return $hash;
}
/*(hash << 5) &#43; hash 相当于 hash * 33,位移的操作比乘法更高效*/
/*
结果&#xff1a;
int(54)
int(1833)
int(60543)
int(1998021)
int(65934790)
float(2175848122)
float(3083511388)
float(2971628093)
float(3574446657)
float(1992622742)
float(1332041144)
float(1007684894)
float(-1106136809)
float(-2142776279)
float(-1992140422)
float(-1316124435)
float(-482433340)
float(1259569015)
float(2911071886)
float(1576091778)
float(471421223)
float(-1622968768)
float(-2018361740)
float(-2181427925)
float(-3267644691)
float(-4753059648)
float(-6527112925)
float(-4941328969)
float(-4150065975)
float(-3808190947)
float(-5411216861)
float(-6771464525)
*/
/*
上面函数可以看到&#xff0c;跟float类型按位与得到了负数&#xff0c;与float类型按位与&#xff1f;这样的操作对么&#xff1f;
php并没有长整形&#xff0c;而计算中int一下就溢出了。
那么得到的以上所有函数得到的值是不是我们想要的。未完待续。
*/                           
页: [1]
查看完整版本: DJB Hash Function,也称times33算法, php的实现与分析-算法