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

1. <?php 
2. //所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。 
3.  
4. /* 
5.  
6. 若 N =1 ; 申請內存空間為 int a[2] ;  
7. 假設需要排序或者查找的總數N=10000000，那么我們需要申請內存空間的大小為int a[1 + N/32]，其中：a[0]在內存中占32為可以對應十進制數0-31，依次類推：  
8.  
9. 1.求十進制0-N對應在數組a中的下標： n/32  
10.  
11. 2.求0-N對應0-31中的數： N%32=M 
12.  
13. 3.利用移位0-31使得對應32bit位為1: 1<<M，并置1; 
14.  
15. 舉例 :  
16.  
17. 如果想存儲 3  
18. (1) a下標 30/ 32 = 0 ; 放在a[0] 中;  
19. (2) 3% 32 = 30;  
20. (3) 左移 30 位 01000000 00000000 00000000 00000000 這個對應的值$a[0] = 1073741824 ;  
21.  
22.  
23. 1.求十進制0-N對應在數組a中的下標：  
24. 十進制0-31，對應在a[0]中，先由十進制數n轉換為與32的余可轉化為對應在數組a中的下標。比如n=24,那么 n/32=0，則24對應在數組a中的下標為0。又比如n=60,那么n/32=1，則60對應在數組a中的下標為1，同理可以計算0-N在數組a中的下標。  
25.  
26. 2.求0-N對應0-31中的數：  
27.  
28. 十進制0-31就對應0-31，而32-63則對應也是0-31，即給定一個數n可以通過模32求得對應0-31中的數。  
29.  
30. 3.利用移位0-31使得對應32bit位為1.  
31.  
32. 找到對應0-31的數為M, 左移M位：即2^M. 然后置1. 
33.  
34. 由此我們計算10000000個bit占用的空間： 
35.  
36. 1byte = 8bit 
37.  
38. 1kb = 1024byte 
39.  
40. 1mb = 1024kb 
41. 占用的空間為：10000000/8/1024/1024mb。 
42.  
43. 大概為1mb多一些。 
44.  
45. */ 
46.  
47. class bigMap { 
48. //使用兩個字節保存  
49. private $mask = 0x1f ; 
50. private $bitsperword = 32 ; 
51. // 移位的位數為5 pow(2,5) = 32  
52. private $shift = 5 ; 
53. // 存儲數據的數組  
54. public $bitArray = array();  
55.  
56. /** 
57. $i 對應的數歸零  
58. */ 
59. function clearbit($i){ 
60. ////則將當前byte中的指定bit位取0，&后其他對方數組bit位必然不變，這就是 1 的妙用 
61. // $i>>SHIFT 這里相當于 intval($i /32) ; 
62. // $i & $this->mask 這里相當于 $i % $this->mask ,取余 
63. @$this->bitArray[$i >> $this->shift] &= ~(1<<($i & $this->mask));  
64. } 
65.  
66. /** 
67. $i 對應的數致1  
68. */ 
69. function setbit($i){ 
70. @$this->bitArray[$i >> $this->shift] |= (1<<($i & $this->mask));  
71. } 
72.  
73. //test 測試所在的bit為是否為1  
74. function testbit($i){  
75. return $this->bitArray[$i >> $this->shift] & (1<<($i & $this->mask));  
76. }  
77. } 
78.  
79.  
80. $oBig = new bigMap() ;  
81.  
82. $oBig->setbit(30) ;  
83.  
84. var_dump($oBig->testbit(2)) ;  
85. var_dump($oBig->bitArray) ;  
86.  
87. echo decbin($oBig->bitArray[0]),"<br>";