php数据结构哈希结构 数据结构 哈希表

php底层原理 php是如何运行的

1、PHP动态语言执行过程：拿到一段代码后，经过词法解析、语法解析等阶段后，源程序会被翻译成一个个指令（opcodes）,然后ZEND虚拟机顺次执行这些指令完成操作。PHP本身是用C实现的，因此最终调用的也是C的函数，实际上，我们可以把PHP看做一个C开发的软件。

创新互联主要从事成都网站制作、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务武威,十年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

2、PHP的4层运行体系：

（1）Zend引擎：Zend整体用纯C实现，是PHP的内核部分，他将PHP代码翻译（词法、语法解析等一系列编译过程）为可执行opcode的处理并实现相应的处理方法、实现了基本的数据结构（如：hashtable、OO）、内存分配机制及管理、提供了相应的api方法供外部调用，是一切的核心，所有的外围功能均围绕Zend实现。

（2）Extensions：围绕着Zend引擎，extensions通过组件式的方式提供各种基础服务，我们常见的各种内置函数（array系列）、标准库等都是通过extension来实现，用户也可以根据需要实现自己的extension的典型应用）。

（3）Sapi：Sapi全称ServerApplicationProgrammingInterface，也就是服务端应用编程接口，Sapi通过一系列钩子函数，使得PHP可以和外围交互数据，这是PHP非常优雅和成功的设计，通过sapi成功的将PHP本身和上层应用解耦隔离，PHP可以不再考虑如何针对不同应用进行兼容，而应用本身也可以针对自己的特点实现不同的处理方式。

（4）上层应用：这就是我们平时编写的PHP程序，通过不同的spai方式得到各种各样的应用模式，如何通过webserver实现web应用、在命令行下已脚本方式运行等等。

php hashtable 是什么东西具体怎么用,求详解???

hashtable 中文应该是翻译为：哈希表。散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

具体进一步的了解，建议你看计算机专业的数据结构方面的教程。

PHP 使用HashTable来保存数组信息，md5/sha1都是哈希表的算法，具体的应用比如：文件校验、数字签名等。

数据结构-Hash

先看一下hash表的结构图：

哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

白话一点的说就是通过把Key通过一个固定的算法函数（hash函数）转换成一个整型数字，然后就对该数字对数组的长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

先了解一下下面几个常说的几个关键字是什么：

key ：我们输入待查找的值

value ：我们想要获取的内容

hash值 ：key通过hash函数算出的值（对数组长度取模，便可得到数组下标）

hash函数（散列函数） ：存在一种函数F，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个遍历比较。这样就预先知道key在的位置，直接找到数据，提升效率。

即

地址index=F(key)

hash函数就是根据key计算出该存储地址的位置，hash表就是基于hash函数建立的一种查找表。

方法有很多种，比如直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等，网上相关介绍有很多，这里就不重点说这个了

对不同的关键字可能得到同一散列地址， 即k1≠k2，而f(k1)=f(k2)，或f(k1) MOD 容量 =f(k2) MOD 容量 ，这种现象称为 碰撞 ，亦称 冲突 。

通过构造性能良好的hash函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是hash表的另一个关键问题。

创建和查找hash表都会遇到冲突，两种情况下解决冲突的方法应该一致。

这里要提到两个参数： 初始容量 ， 加载因子 ，这两个参数是影响hash表性能的重要参数。

容量 ： 表示hash表中数组的长度，初始容量是创建hash表时的容量。

加载因子 ： 是hash表在其容量自动增加之前可以达到多满的一种尺度（存储元素的个数），它衡量的是一个散列表的空间的使用程度。

loadFactor = 加载因子 / 容量

一般情况下，当loadFactor = 1时，hash表查找的期望复杂度为O(1).

对使用链表法的散列表来说， 负载因子越大，对空间的利用更充分，然后后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费 。系统默认负载因子为0.75。

当hash表中元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对数组进行扩容。而在数组扩容之后，最消耗性能的点就出现了，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是 扩容 。

什么时候进行扩容呢？当表中 元素个数超过了容量 * loadFactor 时，就会进行数组扩容。

Foundation框架下提供了很多高级数据结构，很多都是和Core Foundation下的相对应，例如NSSet就是和_CFSet相对应，NSDictionary就是和_CFDictionary相对应。 源码

这里说的hash并不是之前说的hash表，而是一个方法。为什么要有hash方法？

这个问题需要从hash表数据结构说起，首先看下如何在数组中查找某个成员

在数组未排序的情况下，查找的时间复杂度是O(n)（n为数组长度）。hash表的出现，提高了查找速度，当成员被加入到hash表中时，会计算出一个hash值，hash值对数组长度取模，会得到该成员在数组中的位置。

通过这个位置可以将查找的时间复杂度优化到O(1)，前提是在不发生冲突的情况下。

这里的hash值是通过hash方法计算出来的，且hash方法返回的hash值最好唯一

和数组相比，基于hash值索引的hash表查找某个成员的过程：

可以看出优势比较明显，最坏的情况和数组也相差无几。

重写person的hash方法和copyWithZone方法，方便查看hash方法是否被调用：

打印结果：

可以了解到： hash方法只在对象被添加到NSSet和设置为NSDictionary的key时被调用

NSSet添加新成员时，需要根据hash值来快速查找成员，以保证集合中是否已经存在该成员。

NSDictionary在查找key时，也是利用了key的hash值来提高查找的效率。

这里可以得到这个结论：

相等变量的hash结果总是相同的，不相等变量的hash结果有可能相同

根据数据结构可以发现set内部使用了指针数组来保存keys，可以从 源码 中了解到采用的是连续存储的方式存储。

NSSet添加key，key值会根据特定的hash函数算出hash值，然后存储数据的时候，会根据hash函数算出来的值，找到对应的下标，如果该下标下已有数据，开放定址法后移动插入，如果数组到达阈值，这个时候就会进行扩容，然后重新hash插入。查询速度就可以和连续性存储的数据一样接近O(1)了。

和上面的集合NSSet相比较，多了一个指针数组values。

通过比较集合NSSet和字典NSDictionary的 源码 可以知道两者实现的原理差不多，而字典则用了两个数组keys和values，说明这两个数据是被分开存储的。

通过源码可以看到，当有重复的key插入到字典NSDictionary时，会覆盖旧值，而集合NSSet则什么都不做，保证了里面的元素不会重复。

大家都知道，字典里的键值对key-value是一一对应的关系，从数据结构可以看出，key和value是分别存储在两个不同的数组里，这里面是如何对key、value进行绑定的呢？

首先 key利用hash函数算出hash值，然后对数组的长度取模，得到数组下标的位置，同样将这个地址对应到values数组的下标，就匹配到相应的value。 注意到上面的这句话，要保证一点， 就是keys和values这两个数组的长度要一致 。所以扩容的时候，需要对keys和values两个数组一起扩容。

对于字典NSDictionary设置的key和value，key值会根据特定的hash函数算出hash值，keys和values同样多，利用hash值对数组长度取模，得到其对应的下标index，如果下标已有数据，开放定址法后移插入，如果数组达到阈值，就扩容，然后重新hash插入。这样的机制就把一些不连续的key-value值插入到能建立起关系的hash表中。

查找的时候，key根据hash函数以及数组长度，得到下标，然后根据下标直接访问hash表的keys和values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了。

参考文章： 笔记-数据结构之 Hash（OC的粗略实现）

数据结构问题：哈希表的存储结构是什么？

哈希表的存储结构为散列函数。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。

这里把这种对应关系f称为散列函数，又称为哈希（Hash）函数。按这个思想，采用散列技术将记录存在在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。那么，关键字对应的记录存储位置称为散列地址。

散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率会大大 提高。但是，散列技术部具备很多常规数据结构的能力，如比较同样的关键字，对应很多记录的情况，不适合用散列技术；散列表也不适合范围查找等等。

在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。市场会碰到两个关键字key1 != key2，但是却有f(key1) = f(key2)，这种现象称为冲突。出现冲突将会造成查找错误，因此可以通过精心设计散列函数让冲突尽可能的少，但是不能完全避免。