参考链接#PHP.NET

HashTable 是一种数据结构 ,是哈希函数

- <<PHP内核原理>> 摘
1
2
3
4
5
6
7
8
9
10
11
12
哈希表通常提供查找(Search),插入(Insert),删除(Delete)等操作,
这些操作在最坏的情况下和链表的性能一样为O(n)。
不过通常并不会这么坏,
合理设计的哈希算法能有效的避免这类情况,通常哈希表的这些操作时间复杂度为O(1)。
这也是它被钟爱的原因。

正是因为哈希表在使用上的便利性及效率上的表现,
目前大部分动态语言的实现中都使用了哈希表

PHP内核中的哈希表是十分重要的数据结构,
PHP的大部分的语言特性都是基于哈希表实现的,
例如:变量的作用域、函数表、类的属性、方法等,Zend引擎内部的很多数据都是保存在哈希表中的。
 1. 特定键值的映射的一种数据结构,键值的一一对应关系
 2. 键(key):用于操作数据的标示,例如PHP数组中的索引,或者字符串键等等
 3. 槽(slot/bucket):哈希表中用于保存数据的一个单元,也就是数据真正存放的容器
 4. 哈希函数(hash function):将key映射(map)到数据应该存放的slot所在位置的函数。 
 5. 哈希冲突(hash collision):哈希函数将两个不同的key映射到同一个索引的情况。目前解决hash冲突的方法主要有两种:链接法和开放寻址法 (hash 碰撞解决方案(移位或二次hash)  google吧 )
 6. h(key) -> index 这样理解 数组(键值可以是数字或其他字符甚至中文 hash可以节约空间)
 7. PHP中HashTable的哈希冲突解决方法就是链接法
 8. 链接法通过使用一个链表来保存slot值的方式来解决冲突,也就是当不同的key映射到一个槽中的时候使用链表来保存这些值。所以使用链接法是在最坏的情况下,也就是所有的key都映射到同一个槽中了,这样哈希表就退化成了一个链表,这样的话操作链表的时间复杂度则成了O(n),这样哈希表的性能优势就没有了,所以选择一个合适的哈希函数是最为关键的
 9. 开放寻址法。使用开放寻址法是槽本身直接存放数据,在插入数据时如果key所映射到的索引已经有数据了,这说明发生了冲突,这是会寻找下一个槽,如果该槽也被占用了则继续寻找下一个槽,直到寻找到没有被占用的槽,在查找时也使用同样的策略来进行。
    由于开放寻址法处理冲突的时候占用的是其他槽位的空间,这可能会导致后续的key在插入的时候更加容易出现哈希冲突,所以采用开放寻址法的哈希表的装载因子不能太高,否则容易出现性能下降

10. Zend引擎中的链表是双链表,通过双链表的任意节点都能方便的对链表进行遍历。
    Zend引擎的哈希表实现是哈希表和双链表的混合实现,这也是为了方便哈希表的遍历

SplFixedArray

数组是以连续方式存储数据的结构, 可通过索引进行访问。不要将它们与 php 数组混淆: php 数组实际上是按照有序的列表实现的

  • 区别

The main differences between a SplFixedArray and a normal PHP array is that the SplFixedArray is of fixed length and allows only integers within the range as indexes. The advantage is that it allows a faster array implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SplFixedArray implements Iterator , ArrayAccess , Countable {
/* 方法 */
public __construct ([ int $size = 0 ] )
public int count ( void )
public mixed current ( void )
public static SplFixedArray fromArray ( array $array [, bool $save_indexes = TRUE ] )
public int getSize ( void )
public int key ( void )
public void next ( void )
public bool offsetExists ( int $index )
public mixed offsetGet ( int $index )
public void offsetSet ( int $index , mixed $newval )
public void offsetUnset ( int $index )
public void rewind ( void )
public bool setSize ( int $size )
public array toArray ( void )
public bool valid ( void )
public void __wakeup ( void )
}

对比 Array SplFixedArray

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

$a = array();
for ($i = 0; $i < 50000; $i++) {
$a[$i] = $i;
}
var_dump($a);

/**

php -dvld.active=1 -dvld.execute=0 spl_array3.php
Finding entry points
Branch analysis from position: 0
Jump found. (Code = 45) Position 1 = 15, Position 2 = 11
Branch analysis from position: 15
Jump found. (Code = 62) Position 1 = -2
Branch analysis from position: 11
Jump found. (Code = 42) Position 1 = 8
Branch analysis from position: 8
Jump found. (Code = 42) Position 1 = 5
Branch analysis from position: 5
filename: \spl_array3.php
function name: (null)
number of ops: 21
compiled vars: !0 = $a, !1 = $i
line #* E I O op fetch ext return operands
-------------------------------------------------------------------------------------
11 0 E > EXT_STMT
1 INIT_ARRAY ~0
2 ASSIGN !0, ~0
12 3 EXT_STMT
4 ASSIGN !1, 0
5 > IS_SMALLER ~3 !1, 5
6 EXT_STMT
7 > JMPZNZ 11 ~3, ->15
8 > POST_INC ~4 !1
9 FREE ~4
10 > JMP ->5
13 11 > EXT_STMT
12 ASSIGN_DIM !0, !1
13 OP_DATA !1, $6
14 14 > JMP ->8
15 15 > EXT_STMT
16 EXT_FCALL_BEGIN
17 SEND_VAR !0
18 DO_FCALL 1 'var_dump'
19 EXT_FCALL_END
16 20 > RETURN 1

branch: # 0; line: 11- 12; sop: 0; eop: 4; out1: 5
branch: # 5; line: 12- 12; sop: 5; eop: 7; out1: 15; out2: 11
branch: # 8; line: 12- 12; sop: 8; eop: 10; out1: 5
branch: # 11; line: 13- 14; sop: 11; eop: 14; out1: 8
branch: # 15; line: 15- 16; sop: 15; eop: 20; out1: -2
path #1: 0, 5, 15,
path #2: 0, 5, 11, 8, 5, 15,


*/
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
<?php

$spl_a = new SplFixedArray(50000);
for ($i = 0; $i < 50000; $i++) {
$spl_a[$i] = $i;
}

var_dump($spl_a);

/**


php -dvld.active=1 -dvld.execute=0 spl_array4.php
Finding entry points
Branch analysis from position: 0
Jump found. (Code = 45) Position 1 = 20, Position 2 = 16
Branch analysis from position: 20
Jump found. (Code = 62) Position 1 = -2
Branch analysis from position: 16
Jump found. (Code = 42) Position 1 = 13
Branch analysis from position: 13
Jump found. (Code = 42) Position 1 = 10
Branch analysis from position: 10
filename: spl\spl_array4.php
function name: (null)
number of ops: 26
compiled vars: !0 = $spl_a, !1 = $i
line #* E I O op fetch ext return operands
-------------------------------------------------------------------------------------
11 0 E > EXT_STMT
1 FETCH_CLASS 0 :0 'SplFixedArray'
2 EXT_FCALL_BEGIN
3 NEW $1 :0
4 SEND_VAL 5
5 DO_FCALL_BY_NAME 1
6 EXT_FCALL_END
7 ASSIGN !0, $1
12 8 EXT_STMT
9 ASSIGN !1, 0
10 > IS_SMALLER ~5 !1, 5
11 EXT_STMT
12 > JMPZNZ 16 ~5, ->20
13 > POST_INC ~6 !1
14 FREE ~6
15 > JMP ->10
13 16 > EXT_STMT
17 ASSIGN_DIM !0, !1
18 OP_DATA !1, $8
14 19 > JMP ->13
16 20 > EXT_STMT
21 EXT_FCALL_BEGIN
22 SEND_VAR !0
23 DO_FCALL 1 'var_dump'
24 EXT_FCALL_END
17 25 > RETURN 1

branch: # 0; line: 11- 12; sop: 0; eop: 9; out1: 10
branch: # 10; line: 12- 12; sop: 10; eop: 12; out1: 20; out2: 16
branch: # 13; line: 12- 12; sop: 13; eop: 15; out1: 10
branch: # 16; line: 13- 14; sop: 16; eop: 19; out1: 13
branch: # 20; line: 16- 17; sop: 20; eop: 25; out1: -2
path #1: 0, 10, 20,
path #2: 0, 10, 16, 13, 10, 20,



*/

结果

1
2
3
4
5
6
7
8
9
10
11
12
 1. 刚开始在同一个文件测试,始终是array 然后测试值比较小 出乎意料  array 比 SplFixedArray 少  无论从生成的操作数和生成的中间代码的变量列表 说明 Array较快或者差不多

2. 调整参数之后 随着参数越来越大 ,SplFixedArray 比array 优势明显

生成的操作数 SplFixedArray 保持不变 Array 增加明显
生成的中间代码的变量列表 SplFixedArray 保持不变 Array 增加明显

3. 普通数组实现是链表加hashtable混合实现 在较小数是 完全退化为链表 hashtable 优势没有发挥出来,尽管这样在处理 小数量级时还是比SplFixedArray 有微弱优势

4. 之所以说微弱 是因为 SplFixedArray 的键值只能是数字型 并且有固定size大小,相较于SplFixedArray 一次分配内存 和Array动态分配内存而言 肯定SplFixedArray 更有优势

5. 在大数量级时 SplFixedArray 处理比 Array 优势明显 (比array更高效 开篇已说明 见(区别))

SplObjectStorage

映射是一个数据拥有键值对。PHP 数组可以被看作是从整数/字符串到值的映射。SPL 提供了从对象到数据的映射。此映射也可用作对象集

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

SplObjectStorage implements Countable , Iterator , Serializable , ArrayAccess {
/* 方法 */
public void addAll ( SplObjectStorage $storage )
public void attach ( object $object [, mixed $data = NULL ] )
public bool contains ( object $object )
public int count ( void )
public object current ( void )
public void detach ( object $object )
public string getHash ( object $object )
public mixed getInfo ( void )
public int key ( void )
public void next ( void )
public bool offsetExists ( object $object )
public mixed offsetGet ( object $object )
public void offsetSet ( object $object [, mixed $data = NULL ] )
public void offsetUnset ( object $object )
public void removeAll ( SplObjectStorage $storage )
public void removeAllExcept ( SplObjectStorage $storage )
public void rewind ( void )
public string serialize ( void )
public void setInfo ( mixed $data )
public void unserialize ( string $serialized )
public bool valid ( void )
}
  • 从实现可以知道,实现对象存储最重要的一个接口实现 序列化功能 ,能用于stream传递
  • 两个重要函数 attach / detach
  • 经常在框架源码中发现 SplSubject 和 SplObserver 联合使用
  • 典型应用场景 比如(反射 或者设计模式相关 用于存放对象信息map)

Demo

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

<?php


interface Car{
function money();
}

class BMW implements Car{

private $_name;
private $_seri;

function __construct($name,$seri){
$this->_name = $name;
$this->_seri = $seri;
}

function money() {
return 0;
}
public function getInfo(){
return sprintf("名字:%s 系列:%s 值钱:%s ".PHP_EOL,$this->_name,$this->_seri,$this->money());
}


}

$x1 = new BMW("宝马X1",'X');
$x3 = new BMW("宝马X3",'X');
$x4 = new BMW("宝马X4",'X');
$x5 = new BMW("宝马X5",'X');

$container = new SplObjectStorage();
$container->attach($x1);
$container->attach($x3);
$container->attach($x4);
$container->attach($x5);

// 查看容器对象数量
var_dump($container->count());
// 干掉x5
$container->detach($x5);
// 重置指针
$container->rewind();

// 遍历对象
while ($container->valid()){
echo $container->current()->getInfo();
$container->next();
}
/** output
int(4)
名字:宝马X1 系列:X 值钱:0
名字:宝马X3 系列:X 值钱:0
名字:宝马X4 系列:X 值钱:0

*/