這篇文章主要介紹了PHP中使用BigMap實(shí)例,本文直接給出實(shí)現(xiàn)代碼,代碼中包含詳細(xì)注釋,需要的朋友可以參考下

<?php

//所謂的Bit-map就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。

/*

若 N =1 ; 申請(qǐng)內(nèi)存空間為 int a[2] ;

假設(shè)需要排序或者查找的總數(shù)N=10000000，那么我們需要申請(qǐng)內(nèi)存空間的大小為int a[1 + N/32]，其中：a[0]在內(nèi)存中占32為可以對(duì)應(yīng)十進(jìn)制數(shù)0-31，依次類(lèi)推：

1.求十進(jìn)制0-N對(duì)應(yīng)在數(shù)組a中的下標(biāo)： n/32

2.求0-N對(duì)應(yīng)0-31中的數(shù)： N%32=M

3.利用移位0-31使得對(duì)應(yīng)32bit位為1: 1<<M，并置1;

舉例 :

如果想存儲(chǔ) 3

(1) a下標(biāo) 30/ 32 = 0 ; 放在a[0] 中;

(2) 3% 32 = 30;

(3) 左移 30 位 01000000 00000000 00000000 00000000 這個(gè)對(duì)應(yīng)的值$a[0] = 1073741824 ;

1.求十進(jìn)制0-N對(duì)應(yīng)在數(shù)組a中的下標(biāo)：

十進(jìn)制0-31，對(duì)應(yīng)在a[0]中，先由十進(jìn)制數(shù)n轉(zhuǎn)換為與32的余可轉(zhuǎn)化為對(duì)應(yīng)在數(shù)組a中的下標(biāo)。比如n=24,那么 n/32=0，則24對(duì)應(yīng)在數(shù)組a中的下標(biāo)為0。又比如n=60,那么n/32=1，則60對(duì)應(yīng)在數(shù)組a中的下標(biāo)為1，同理可以計(jì)算0-N在數(shù)組a中的下標(biāo)。

2.求0-N對(duì)應(yīng)0-31中的數(shù)：

十進(jìn)制0-31就對(duì)應(yīng)0-31，而32-63則對(duì)應(yīng)也是0-31，即給定一個(gè)數(shù)n可以通過(guò)模32求得對(duì)應(yīng)0-31中的數(shù)。

3.利用移位0-31使得對(duì)應(yīng)32bit位為1.

找到對(duì)應(yīng)0-31的數(shù)為M, 左移M位：即2^M. 然后置1.

由此我們計(jì)算10000000個(gè)bit占用的空間：

1byte = 8bit

1kb = 1024byte

1mb = 1024kb

占用的空間為：10000000/8/1024/1024mb。

大概為1mb多一些。

*/

class bigMap {

//使用兩個(gè)字節(jié)保存

private $mask = 0x1f ;

private $bitsperword = 32 ;

// 移位的位數(shù)為5 pow(2,5) = 32

private $shift = 5 ;

// 存儲(chǔ)數(shù)據(jù)的數(shù)組

public $bitArray = array();

/**

$i 對(duì)應(yīng)的數(shù)歸零

*/

function clearbit($i){

////則將當(dāng)前byte中的指定bit位取0，&后其他對(duì)方數(shù)組bit位必然不變，這就是 1 的妙用

// $i>>SHIFT 這里相當(dāng)于 intval($i /32) ;

// $i & $this->mask 這里相當(dāng)于 $i % $this->mask ,取余

@$this->bitArray[$i >> $this->shift] &= ~(1<<($i & $this->mask));

}

/**

$i 對(duì)應(yīng)的數(shù)致1

*/

function setbit($i){

@$this->bitArray[$i >> $this->shift] |= (1<<($i & $this->mask));

}

//test 測(cè)試所在的bit為是否為1

function testbit($i){

return $this->bitArray[$i >> $this->shift] & (1<<($i & $this->mask));

}

}

$oBig = new bigMap() ;

$oBig->setbit(30) ;

var_dump($oBig->testbit(2)) ;

var_dump($oBig->bitArray) ;

更多信息請(qǐng)查看IT技術(shù)專(zhuān)欄