PHP-trait
自 PHP 5.4.0 起，PHP 实现了一种代码复用的方法，称为 trait。
Trait 是为类似 PHP 的单继承语言而准备的一种代码复用机制。Trait 为了减少单继承语言的限制，使开发人员能够自由地在不同层次结构内独立的类中复用 method。Trait 和 Class 组合的语义定义了一种减少复杂性的方式，避免传统多继承和 Mixin 类相关典型问题。
Trait 和 Class 相似，但仅仅旨在用细粒度和一致的方式来组合功能。 无法通过 trait 自身来实例化。它为传统继承增加了水平特性的组合；也就是说，应用的几个 Class 之间不需要继承。
Example #1 Trait 示例
12345678910111213141516<?phptrait ezcReflectionReturnInfo { function getReturnType() { /*1*/ } function getReturnDescription() { /*2*/ } ...
PHP精度问题
问题intval(0.58 * 100)输出结果为57
分析要搞明白这个原因, 首先我们要知道浮点数的表示(IEEE 754):
浮点数, 以64位的长度(双精度)为例， 会采用1位符号位(E)， 11指数位(Q)，52位尾数(M)表示(一共64位)。
符号位：最高位表示数据的正负，0表示正数，1表示负数。
指数位：表示数据以2为底的幂，指数采用偏移码表示。
尾数：表示数据小数点后的有效数字。
这里的关键点就在于，小数在二进制的表示，关于小数如何用二进制表示，大家可以百度一下,，我这里就不再赘述, 我们关键的要了解，0.58 对于二进制表示来说，是无限长的值(下面的数字省掉了隐含的1)。
120.58的二进制表示基本上(52位)是: 00101000111101011100001010001111010111000010100011110.57的二进制表示基本上(52位)是: 0010001111010111000010100011110101110000101000111101
而两者的二进制，如果只是通过这52位计算的话，分别是：
120.58 -> 0.57999999 ...
PHP的运行模式
如何获取当前运行模式
1php_sapi_name()
CLI:（command-line interface）命令行接口
可以在控制台或者是shell中键入命令。如：
1php index.php
CGI ：(Common Gateway Interface)公共网关接口
CGI实际上是一种程序之间的交互协议，通常作为HTTP Server和“程序”进行“交谈”的一种工具。这里的“程序”即实现了CGI协议的程序，我们可以称之为CGI程序，CGI程序的实现语言并没有要求。例如PHP-CGI就是实现了CGI协议的CGI程序，而HTTP Server本身也要实现CGI协议才能和PHP-CGI交互。
通过CGI协议，保证了HTTP Server传递过来的数据是标准格式的，以方便CGI程序的编写者。服务器要支持CGI就要提供CGI中要求的环境变量。该协议要求HTTP Server把HTTP Request的Header设置成CGI程序的环境变量，HTTP Request的正文设置成CGI程序的标准输入，而CGI程序的标准输出就是HTTP Response，包括Header和正文。
再进一步具 ...
散列表（下）
带着问题学习
为什么散列表和链表经常放在一起使用？
散列表和链表如何组合起来使用？
一、为什么散列表和链表经常放在一起使用？
散列表的优点：支持高效的数据插入、删除和查找操作
散列表的缺点：不支持快速顺序遍历散列表中的数据
如何按照顺序快速遍历散列表的数据？只能将数据转移到数组，然后排序，最后再遍历数据。
我们知道散列表是动态的数据结构，需要频繁的插入和删除数据，那么每次顺序遍历之前都需要先排序，这势必会造成效率非常低下。
如何解决上面的问题呢？就是将散列表和链表（或跳表）结合起来使用。
二、散列表和链表如何组合起来使用？
LRU（Least Recently Used）缓存淘汰算法
LRU缓存淘汰算法主要操作有哪些？主要包含3个操作：
往缓存中添加一个数据；
从缓存中删除一个数据；
在缓存中查找一个数据；
总结：上面3个都涉及到查找。
如何用链表实现LRU缓存淘汰算法？
需要维护一个按照访问时间从大到小的有序排列的链表结构。
缓冲空间有限，当空间不足需要淘汰一个数据时直接删除链表头部的节点。
当要缓存某个数据时，先在链表中查找这个数据。若未找到，则直接将数据放到链表的尾部。若 ...
散列表（中）
面试题目：如何设计一个工业级的散列函数？思路：何为一个工业级的散列表？工业级的散列表应该具有哪些特性？结合学过的知识，我觉的应该有这样的要求：
支持快速的查询、插入、删除操作；
内存占用合理，不能浪费过多空间；
性能稳定，在极端情况下，散列表的性能也不会退化到无法接受的情况。
方案：如何设计这样一个散列表呢？根据前面讲到的知识，从3个方面来考虑设计思路：
设计一个合适的散列函数；
定义装载因子阈值，并且设计动态扩容策略；
选择合适的散列冲突解决方法。
知识总结：一、如何设计散列函数？
要尽可能让散列后的值随机且均匀分布，这样会尽可能减少散列冲突，即便冲突之后，分配到每个槽内的数据也比较均匀。
除此之外，散列函数的设计也不能太复杂，太复杂就会太耗时间，也会影响到散列表的性能。
常见的散列函数设计方法：直接寻址法、平方取中法、折叠法、随机数法等。
二、如何根据装载因子动态扩容？
如何设置装载因子阈值？
可以通过设置装载因子的阈值来控制是扩容还是缩容，支持动态扩容的散列表，插入数据的时间复杂度使用摊还分析法。
装载因子的阈值设置需要权衡时间复杂度和空间复杂度。如何权衡？如果内存空间 ...
散列表（上）
一、散列表的由来？1.散列表来源于数组，它借助散列函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性。2.需要存储在散列表中的数据我们称为键，将键转化为数组下标的方法称为散列函数，散列函数的计算结果称为散列值。3.将数据存储在散列值对应的数组下标位置。
二、如何设计散列函数？总结3点设计散列函数的基本要求1.散列函数计算得到的散列值是一个非负整数。2.若key1=key2，则hash(key1)=hash(key2)3.若key≠key2，则hash(key1)≠hash(key2)正是由于第3点要求，所以产生了几乎无法避免的散列冲突问题。
三、散列冲突的解放方法？
常用的散列冲突解决方法有2类：开放寻址法（open addressing）和链表法（chaining）
开放寻址法
核心思想：如果出现散列冲突，就重新探测一个空闲位置，将其插入。
线性探测法（Linear Probing）：
插入数据：当我们往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
查找数据：我们 ...
数据库与缓存双写一致性方案解析
先更新数据库，再更新缓存这套方案，大家是普遍反对的。为什么呢？有如下两点原因。
原因一（线程安全角度）同时有请求A和请求B进行更新操作，那么会出现
线程A更新了数据库；
线程B更新了数据库；
线程B更新了缓存；
线程A更新了缓存；
这就出现请求A更新缓存应该比请求B更新缓存早才对，但是因为网络等原因，B却比A更早更新了缓存。这就导致了脏数据，因此不考虑。
原因二（业务场景角度）有如下两点：
如果是一个写数据库场景比较多，而读数据场景比较少的业务需求，采用这种方案就会导致，数据压根还没读，缓存就被频繁的更新，浪费性能。
如果写入数据库的值，并不是直接写入缓存的，而是要经过一系列复杂的计算再写入缓存。那么，每次写入数据库后，都再次计算写入缓存的值，无疑是浪费性能的。显然，删除缓存更为适合。
先删除缓存，再更新数据库该方案会导致不一致的原因是。同时有一个请求A进行更新操作，另一个请求B进行查询操作。那么会出现如下情形:
请求A进行写操作，删除缓存；
请求B查询发现缓存不存在；
请求B去数据库查询得到旧值；
请求B将旧值写入缓存；
请求A将新值写入数据库。
上述情况就会导致不一致的 ...
二分查找
一、什么是二分查找？二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。
二、时间复杂度分析？
时间复杂度假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2^k)，…，这是一个等比数列。当n/(2^k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。
认识O(logn)
这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？
因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。
由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。
三、如何实现二分查找？循环实现代码实现：
1234567891011 ...
二叉树遍历-php实现
经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
代码实现定义一个树节点类12345678910111213141516171819202122232425262728293031323334<?phpclass TreeNode{ /** * 节点中的数据 * @var null */ public $data; /** * 左节点 * @var null */ public $left; /** * 右节点 * @var null */ public $right; ...
跳表
一、什么是跳表？为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。
二、跳表的时间复杂度？
计算跳表的高度如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2^k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。
计算跳表的时间复杂度假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？如下图所示，假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级 ...