工作中、面试中经常被问到上万条数据如何利用最小的空间存储，如何快速检索出数据？
经过多方面的资料收集，我们来看看 php实现位图法 是怎么做的。
1、我们知道 1G=1024M 1M=1024KB 1KB=1024byte 1byte=8bit 也就是一个字节等于8bit 也就是8个二进制位，位图法的概念是用一个位来标记某个数的存放状态，所以节省了大量的空间。
2、数据结构
unsigned int bit[N] 这个数组里面，可以储存 N * PHP_INT_SIZE *8 个数据，但最大的数是 N * PHP_INT_SIZE *8-1。 例如我们要存储的数据范围为0-63，则我们只需要将 N=1 ，这样就可以把数据存进去。
例外： 操作系统分32位 和 64位 32位 PHP_INT_SIZE =4 64位 PHP_INT_SIZE =8
如果是32位系统 ，则 N=2
如果是64位系统 ，则 N=1
数据为[5,1,7,15,0,4,6,10,14]，将这些数据存入这个结构中为
下面我们来研究研究算法：
在说算法之前，先普及一下位移知识
| 符号 | 名称 | 说明 (转移完成后是二进制数) | 示例 | 总结 |
| << | 左移 | 把左边的数 向左移动 多少位，不够 以0补全 | 1<<0 等同于 1 等于 1 1<<1 等同于 10 等于 2 1<<2 等同于 100 等于 4 1<<3 等同于 1000 等于 8 | - |
| | | 按位或 | 两个数有一个是1 就等于1 不进位加法 | 3｜2 换成二进制 11 ｜ 10 =11 等于3 | 多位二进制也是一样，遵循规则， 11 和 10 ，我们转换成十进制来说 十位上都一样，是1 ，个位是只要有一个数是 1 就是1 ，则 等到11 ，11换算成二进制就是3 |
| & | 按位与 | 只有两个数都为1时 等于1 不进位加法 | 3&2 换成二进制 11 & 10 =10 等于2 | |
| ^ | 按位异或 | 两个数不相等则等于1 ，相等则等于0 | ||
| ~ | 取反 | |||
用途：
使用上面介绍的运算符可以很轻松地实现权限管理
//定义权限 $create = 1; $update = 2; $read = 4; $delete = 8; $all = $create | $update | $read | $delete; //定义用户组权限$admin = $all; //管理员拥有所有权限$guest = $create | $read; //访客只有添加和读权限$user = $all & ~$delete; //用户拥有除了删除以外的所有权限 //判断某个组是否拥有某个权限var_dump($user & $update, $user & $delete, $guest & $update);#=>int(2) int(0) int(0)
bitMap 方法 把数组位图化，并以数组的形式返回：
function bitmap($data, $int = 10) {
$bitmap = array_fill(0, $int, 0);
$int_bit_size = PHP_INT_SIZE * 8;
foreach ($data as $item) {
//字节位置
$bytePos = $item / $int_bit_size;
$bitPos = $item % $int_bit_size;
$position = 1 << $bitPos;
isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0;
// printf("item:%d position:%d 格子:%d 表达式:%d|%d=%d\n", $item, $position, $bytePos, $bitmap[$bytePos], $position, $bitmap[$bytePos] | $position);
$bitmap[$bytePos] = $bitmap[$bytePos] | $position;
}
return $bitmap;
}调用方法：
$arr = [5, 1, 7, 15, 0, 4, 6, 10, 14, 88]; $bitmap = bitmap($arr);
===================简单对bitmap做个介绍===========================
$arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31];
$bit_int_size=PHP_INT_SIZE*8; 这个结果是32 按理说，可以存储32个数据，
PHP_INT_MAX php最大值是 2147483647
当储存大于这个数字的时候，位移 会现出 -1 的情况
为了避免这个问题， 我们把bit_int_size=PHP_INT_SIZE*8-1 少保存一个，这样最大保存 2147483647 就不会出现负数。
这里的一个改动，其他地方也要 跟着进行修改。
===================简单对bitmap做个介绍===========================
位图化的转成原始数组：
function getdata($bitmap) {
$int_bit_size = PHP_INT_SIZE * 8;
$result = array();
// $num = 0;
foreach ($bitmap as $key => $value) {
for ($i = 0; $i < $int_bit_size; $i++) {
$temp = 1 << $i;
$flag = $temp & $value;
if ($flag) {
$result[] = $key * $int_bit_size + $i;
//printf("value:%d i:%d temp 1<<%d=%d temp:%d flag:%d result:%d \n", $value, $i, $i, $temp, $temp, $flag, $key * $int_bit_size + $i);
}
//$num++;
}
}
return $result;
}使用方法：
$data=getdata($bitmap);
判断数据是否存在：
function checkExists($bitmap, $val) {
$int_bit_size = PHP_INT_SIZE * 8;
$key = floor($val / $int_bit_size);
$result = null;
if (isset($bitmap[$key])) {
for ($b = 0; $b < $int_bit_size; $b++) {
$temp = 1 << $b;
$flag = $temp & $bitmap[$key];
if ($flag && ($val == (($key * $int_bit_size) + $b))) {
$result = $val;
break;
}
// printf("value:%d b:%d key:%d temp:%d flag:%d\n", (($key * $int_bit_size) + $b), $b, $key, $temp, $flag);
}
}
return $result;
}使用方法：
checkExists($bitmap, 999145);
动态添加：
function addData(&$bitmap, $val) {
$int_bit_size = PHP_INT_SIZE * 8;
$bytePos = floor($val / $int_bit_size);
isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0;
$bitPos = $val % $int_bit_size;
$position = 1 << $bitPos;
$bitmap[$bytePos] = $bitmap[$bytePos] | $position;
return $bitmap;
}addData($bitmap,100); 向数组中添加一个100的数据
备注：
存储的数组中，数据不能重复，会替换。
例如说：
$arr = [5, 1, 7, 15, 0, 4, 6, 10, 14, 88, 15];
数组中有两个 15 ，只会保留一个 15，
且 getdata($bitmap)后，数据会从小到大依次排序
Array
(
[0] => 0
[1] => 1
[2] => 4
[3] => 5
[4] => 6
[5] => 7
[6] => 10
[7] => 14
[8] => 15
[9] => 88
)
只保留了一个15 ，且 顺序是从小到的 依次排序的。
这里还有一个功能就是可以做排序噢！
下面进行封装了一个类：
Bitmap.php
class Bitmap {
public static $_instance = NULL;
public $int_bit_size = NULL;
private $_bitmap = [];
public function __construct() {
$this->int_bit_size = PHP_INT_SIZE * 8 - 1;
}
/**
* 根据数组创建一个bitmap
* @param $data
* @param int $int
*/
public function createBitMap(array $data, $int = 10) {
//创建一个指定长度以0填充的数组
$bitmap = array_fill(0, $int, 0);
foreach ($data as $item) {
//字节位置
$bytePos = $item / $this->int_bit_size;
$bitPos = $item % $this->int_bit_size;
$position = 1 << $bitPos;
isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0;
$bitmap[$bytePos] = $bitmap[$bytePos] | $position;
}
$this->_bitmap = $bitmap;
return $this;
}
/**
* 从小到大排序数组
* @param array $data
* @return array
*/
public static function bitSort(array $data) {
return (new self())->createBitMap($data)->getData();
}
/**
* 获取bitmap的原始数据
* @param $bitmap
* @return array
*/
public function getData(array $bitmap = NULL) {
$int_bit_size = $this->int_bit_size;
$result = array();
$bitmap = is_null($bitmap) ? $this->_bitmap : $bitmap;
foreach ($bitmap as $key => $value) {
for ($i = 0; $i < $int_bit_size; $i++) {
$temp = 1 << $i;
$flag = $temp & $value;
if ($flag) {
$result[] = $key * $int_bit_size + $i;
}
}
}
return $result;
}
/**
* 判断bitmap中是否存在这个数据
* @param $val
* @return null
*/
public function checkExists($val) {
if (!is_int($val)) return NULL;
$int_bit_size = $this->int_bit_size;
$key = floor($val / $int_bit_size);
$result = NULL;
if (isset(($this->_bitmap)[$key])) {
for ($b = 0; $b < $int_bit_size; $b++) {
$temp = 1 << $b;
$flag = $temp & ($this->_bitmap)[$key];
if ($flag && ($val == (($key * $int_bit_size) + $b))) {
$result = $val;
break;
}
}
}
return $result;
}
/**
* 在bitmap中添加数据
* @param $val
* @return $this
*/
public function addData($val) {
if (!is_int($val)) return $this;
$int_bit_size = $this->int_bit_size;
$bitmap = $this->_bitmap;
$bytePos = floor($val / $int_bit_size);
isset($bitmap[$bytePos]) || $bitmap[$bytePos] = 0;
$bitPos = $val % $int_bit_size;
$position = 1 << $bitPos;
$bitmap[$bytePos] = $bitmap[$bytePos] | $position;
$this->_bitmap = $bitmap;
return $this;
}
/**
* 在bitmap中删除一个数据
* @param $val
* @return $this
*/
public function delData($val) {
if (!is_int($val)) return $this;
if ($this->checkExists($val)) {
$int_bit_size = $this->int_bit_size;
$key = floor($val / $int_bit_size);
$bitPos = $val % $int_bit_size;
$position = 1 << $bitPos;
$new = $this->_bitmap[$key] & ~$position;
$this->_bitmap[$key] = $new;
}
return $this;
}
/**
* 获取bitmap的值
* @return array
*/
public function getBitmap() {
return $this->_bitmap;
}
public function __get($name) {
return $this->$name;
}
public function __set($name, $value) {
$this->$name = $value;
}
}//调用方法：
public function testAction() {
$arr = [5, 1, 7, 15, 0, 4, 6, 10, 14, 88];
//$arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 99, 9, 10, 11, 12, 90, 13, 14, 15, 16, 17, 100, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 40, 50, 60];
$bitMap = new Bitmap();
$bitdata = $bitMap->createBitMap($arr)->getBitmap();
$ishave = $bitMap->checkExists(88);
printf('数组中%s是否含有88 ::::: %s<br>', var_export($arr, TRUE), is_null($ishave) ? '无' : '有');
P($bitdata);
printf('数组中%s是否含有77 ::::: %s<br>', var_export($arr, TRUE), is_null($bitMap->checkExists(77)) ? '无' : '有');
$bitMap->addData(77);
printf('添加一个77<br>');
printf('数组中%s是否含有77 ::::: %s<br>', var_export($arr, TRUE), is_null($bitMap->checkExists(77)) ? '无' : '有');
printf('删除88<br>');
$bitMap->delData(88);
printf('数组中%s是否含有88 ::::: %s<br>', var_export($arr, TRUE), is_null($bitMap->checkExists(88)) ? '无' : '有');
printf('获取原始数组<br>');
P($bitMap->getData());
//排序功能
//$sortData = Bitmap::bitSort($arr);
//P($sortData);
}页面显示：
数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有88 ::::: 有 Array ( [0] => 50419 [1] => 0 [2] => 67108864 [3] => 0 [4] => 0 [5] => 0 [6] => 0 [7] => 0 [8] => 0 [9] => 0 ) 数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有77 ::::: 无 添加一个77 数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有77 ::::: 有 删除88 数组中array ( 0 => 5, 1 => 1, 2 => 7, 3 => 15, 4 => 0, 5 => 4, 6 => 6, 7 => 10, 8 => 14, 9 => 88, )是否含有88 ::::: 无 获取原始数组 Array ( [0] => 0 [1] => 1 [2] => 4 [3] => 5 [4] => 6 [5] => 7 [6] => 10 [7] => 14 [8] => 15 [9] => 77 )
