這篇文章主要介紹了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) ;