第八章：第11节 PHP数据结构与算法——简单了解哈希表

回顾链表的优缺点：它对数据的插入和删除非常容易，但查询却会随着数据量的增大而增大。它是这样的思路：查找的关键字与链表的每个节点元素一一比对，如果相等，查找到，假如数据不是唯一的，还会继续往下查找，直到结尾。这种做法的时间复杂度为O(n)。

在程序中，对数据的查找要远远大于对数据的其他操作（添加、删除、修改），链表显然不适合做这种需求的数据结构。有一种数据结构对数据查找非常快，那就是哈希表。

哈希表（Hash table，也叫散列表）为什么会查找数据快呢？

它不像链表一样一一比对，而是另外一种思路：把查找的关键字（key）通过某种算法直接计算出数据的存储位置。像这样的查找方式，根本不会随着数据的增多而查找速度变慢，几乎是O(1)的时间复杂度。

记录的存储位置=f(关键字)

这种算法称之为散列函数（hash function），存储位置称为散列值（hash 地址）。

哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的散列函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

或者：把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的内存占用空间通常远小于输入数据的内存占用空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

数组：

说到数组，这里做下介绍。这里的数组指的是C语言里的数组，而不是PHP里的数组。C语言的数组有固定长度和固定类型的特点，就是数组里的每个元素数据类型是一样的，占用的内存空间是一样的。每个元素不会像链表那样分散存储，而是紧挨着的。

C：int a[10] = {32,45,21,67,32,68,41,99,13,71};

JAVA：String[] strArray = {"星期一","星期二","星期三","星期四","星期五","星期六","星期日"};

完全不是PHP数组那种大杂烩，所以只要知道了数组第一个元素的内存地址和元素大小，通过数组的下标就能获取指定元素的内存地址。

散列函数的算法：

哈希表都有哪些构造散列函数的算法？算法绝不是固定的几个，每个人都可以写一个自己算法的散列函数。常见的散列函数的算法：

1)直接定址法

取关键字或者关键字的某个线性函数为Hash地址，即address(key)=a*key+b;如知道学生的学号从2000开始，最大为4000，则可以将address(key)=key-2000作为Hash地址。

2)平方取中法

对关键字进行平方运算，然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取{72，89，00}作为Hash地址。

3)折叠法

将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。

4)除留取余法

如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。

在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。

哈希表的缺点：

查找速度快是哈希表的优点，同样它也有自己的缺点，或者说是设计的难度。

1、它是基与数组的，数组创建后难于扩展（一般系统会重新申请更大空间，把原先的数据复制过去，这就增加了消耗）。某些哈希表被基本填满时，性能下降得非常严重，所以程序必须要清楚表中将要存储多少数据。

2、数组创建很大，数据却很少，造成空间浪费。在构造Hash函数时应尽量考虑关键字的分布特点来设计散列函数，使得Hash地址随机均匀地分布在整个地址空间当中。

3、不同的关键字经过散列函数的计算得到了相同的散列地址，这会造成散列冲突。

冲突的解决：

方法有很多种，这里介绍一个常用的方法——拉链法，我们可以理解为“链表的数组”，如图：

数组的元素是链表，有相同散列值的用链表串联。

从哈希结构去理解PHP数组的特性

了解哈希表对我们编程和理解一些其他知识是很有帮助的。比如我们PHP数组是个哈希表数据结构，类似于这样：

采用的也是拉链法，它附加了一个双向链表，提供了正向、反向遍历数组的功能。

Bucket数据结构

php采用的是链接法解决冲突，所以每个Bucket数据结构中除了指向实际数据的指针，还需要指向链表下一个元素的指针，为了加快查找时间，php的bucket实现中采用双向链表，具体结构如下：（C语言里的结构体）

typedef struct bucket {

ulong h; // 对char *key进行hash后的值，或者是数字的索引值

uint nKeyLength; // hash关键字长度，如果索引为数字，那么这个值为0

void *pData; // 指向用户数据(其实是数据副本，在做UPDATE_DATA或者INIT_DATA时分配了新的空间，将用户数据拷贝了一份)，如果是一个指针，那么指向下面的pDataPtr

void *pDataPtr; // 如果是指针数据，那么这个值指向真正的用户数据(同上一个，也是用户数据的副本)，同时上面的pData指向该值。

struct bucket *pListNext; // 指向整个hash表的下一个元素

struct bucket *pListLast; // 指向整个hash表的上一个元素

struct bucket *pNext; // 指向同一个Bucket内的下一个元素

struct bucket *pLast; // 指向同一个Bucket内的上一个元素

char arKey[1];

} Bucket;

这个结构中有两套双向链表指针：pListNext&pListLast，pNext&pLast。其中，pListNext和pListLast用于构成整个哈希表的链表，这个链表中包括哈希表中的所有元素，按插入顺序构成链表。而pNext和pLast则构成同一个槽位内的Bucket链表，用于解决冲突。

可以看到，在hash table中既有key->value形式的散列结构，也有双向链表模式，使得它能够非常方便的支持快速查找和线性遍历。如果想再深入地理解哈希表，可以参看这个：PHP哈希表结构的深入剖析 。

散列结构：Zend的散列结构（Zend是PHP的引擎）是典型的hash表模型，通过链表的方式来解决冲突。需要注意的是zend的hash table是一个自增长的数据结构，当hash表数目满了之后，其本身会动态以2倍的方式扩容并重新元素位置。初始大小均为8。另外，在进行key->value快速查找时候，zend本身还做了一些优化，通过空间换时间的方式加快速度。比如在每个元素中都会用一个变量nKeyLength标识key的长度以作快速判定。

双向链表：Zend hash table通过一个链表结构，实现了元素的线性遍历。理论上，做遍历使用单向链表就够了，之所以使用双向链表，主要目的是为了快速删除，避免遍历。Zend hash table是一种复合型的结构，作为数组使用时，即支持常见的关联数组也能够作为顺序索引数字来使用，甚至允许2者的混合。

PHP关联数组：关联数组是典型的hash_table应用。一次查询过程经过如下几步（从代码可以看出，这是一个常见的hash查询过程并增加一些快速判定加速查找。）：

（C代码）

PHP索引数组：索引数组就是我们常见的数组，通过下标访问。例如 $arr[0]，Zend HashTable内部进行了归一化处理，对于index类型key同样分配了hash值和nKeyLength(为0)。内部成员变量nNextFreeElement就是当前分配到的最大id，每次push后自动加一。正是这种归一化处理，PHP才能够实现关联和非关联的混合。由于push操作的特殊性，索引key在PHP数组中先后顺序并不是通过下标大小来决定，而是由push的先后决定。例如 $arr[1] = 2; $arr[2] = 3;对于double类型的key，Zend HashTable会将他当做索引key处理。