欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

PHP关联数组与哈希表(hashtable)不指定

程序员文章站 2024-01-26 16:17:40
...

PHP中有一种数据类型非常重要,它就是关联数组,又称为哈希表(hash table),是一种非常好用的数据结构。 在程序中,我们可能会遇到需要消重的问题,举一个最简单的模型: 有一份用户名列表,存储了 10000 个用户名,没有重复项; 还有一份黑名单列表,存储

PHP中有一种数据类型非常重要,它就是关联数组,又称为哈希表(hash table),是一种非常好用的数据结构。

在程序中,我们可能会遇到需要消重的问题,举一个最简单的模型:

有一份用户名列表,存储了 10000 个用户名,没有重复项;
还有一份黑名单列表,存储了 2000 个用户名,格式与用户名列表相同;
现在需要从用户名列表中删除处在黑名单里的用户名,要求用尽量快的时间处理。

这个问题是一个小规模的处理量,如果实际一点,2 个表都可能很大,比如有 2 亿条记录。

我最开始想到的方法,就是做一个嵌套的循环,设用户名表有 M 条记录,黑名单列表有 N 条记录,那么,循环的次数是 M * N 次!
PHP 版代码:


01 02 foreach($arrayM as $keyM => $nameM) {
03 foreach($arrayN as $nameN) {
04 if ($nameM == $nameN) {
05 // 本行执行了 M * N 次!
06 unset($arrayM[$keyM]);
07 }
08 }
09 }
10 return $arrayM;
11 ?>
另一种方式,利用数组索引。

PHP 是一种弱类型的语言,不像 C 语言那样有严格的变量类型限制。C 语言的数组,每一个元素的类型必须一致,而且索引都是从 0 开始。
PHP 的数组,可以用字符串作为索引,也称为关联数组。
数组索引,有一个天然的限制就是不会重复,而且访问的时候不需要查找,可以直接定位。

还是刚才的那个问题,我们采用另一种办法。

把黑名单列表的用户名组织到一个数组里,数组的索引就是用户名。

然后,遍历用户列表的时候,只需直接用 isset 查询那个用户名是否存在即可。

PHP 版代码:


01 02 $arrayHash = array();
03 foreach($arrayN as $nameN) {
04 // 本行执行了 N 次。
05 $arrayHash[$nameN] = 1;
06 }
07
08 foreach($arrayM as $keyM => $nameM) {
09 if (isset($arrayHash[$nameM])) {
10 // 本行执行了 M 次!
11 unset($arrayM[$keyM]);
12 }
13 }
14 return $arrayM;
15 ?>
可以看到,优化过的代码,循环次数是 M + N 次。

假如 M 和 N 都是 10000,优化前,循环了 1 亿次;优化后,只循环了 20000 次,差了 5000 倍!
如果第二个程序耗时 1 秒,则第一个程序需要将近一个半小时!

=========================================================================
hash一个貌似比较复杂的东西,实际上理解起来并不那么夸张,这里做个笔记。

hash,中文翻译成杂乱的东西,有人也叫它杂凑,或者翻译成什么都不是的音译“哈希”。

简单说来,hash就是为了把一个复杂的字串,通过一定的转换,得到一个简单的数字(通常是数字)。
如"abcd" 用各个字符的值直接相加,再取对10的余数,既(a+b+c+d),来得到一个数字,比方说结果为5,那么这个5就能在一定意义上代表这个字串 abcd了。或者说这个5也可以说是这个字串的一个标记性的东西,而且是简化了的标记,所以又有人叫这个5为字串的摘要,或指纹。
这个5,有一个好的用处就是可以作为一个数组的下标来用,如我自己构造一个指针数组void* hash_array[10],那么我就可以把5那个位置上填上一个指针,如指向abcd字串。
这样的话,我如果要去查询一个字串是否存在,就不需要对一个数组使用字符串循环对比这样的慢操作,而直接先得到某个字串的hash值,再用这个hash值,在数组下标里直接找,这样速度要快上很多,特别是数据比较多的时候。

可以看到上面计算hash值时,出来的结果,可能并不是从0开始的,如我们算出的就是5。也就是说,这个5是在数组中的某个不确定的位置,或者可以叫做是一个杂凑出来的位置。其他位置可能一直就空着在。这就是这个数组或表格叫hash表的原因了。

但有个问题,上面的转换方法,直接相加,再取个余数,在字符串变为abdc时,结果得到的还是数字5。这个就是上面这个算法的一个问题了,即它不能保证一个唯一性。所以就出现了很多hash算法的研究,如MD4,MD5,SHA-1等,来保证唯一性。
但上面这个算法还是可以使用的,做法就是在abdc经过hash得到5后,去检查5是否被占用,如果占用了,那么就把数字加1,即为6,如果6没被占用,就填上值。如果后面某个字串算出一个值是6,但6已经被占用了,那么就再加1,再存。
取数据的时候,可以先算出hash值后,再看里面的内容是不是你想要的,如果不是,就加1去看,最后得到一个。

所以这里hash表的内容并不是象一般的数组最开始就组织好了的,而是后续慢慢往里增加的。
hash表里存的内容一般可以是一个指针,这个指针可以指向一个大的结构也是可以的。这个结构里可以有key, value信息。
hash表也可以不是数组,你可以把它组织成一个链表,链表里的node的结构中可以有一个参数就是那个数字的hash_value,用来快速查找用。

虽然在很多时候hash被用在加密等场合,但在一般的应用程序代码中,也可以用它来存贮简单的数据,这样代码的效率会高很多。