PHP：数组结构的演变
一. PHP数组结构的演变
这个地方主要讲PHP5.6=>PHP7.0=>PHP7.1的演变过程
image
我们可以看到，数组本质就是一个hashtable结构，左侧的0~nTablemask便是hash下标，而后面有一个双向链表，便是我们通常所说的hash冲突的链地址法。
而绿色的双向链表，则是foreach遍历用的，这个地方用双向链表，主要是为了逆序访问来用的，遍历的时候，就是从pListHead开始不断的next便可以遍历所有的元素。这样要比下标遍历hashtable快得多。
但是这个结构有很明显的缺点：
①. 每次插入/删除元素都要申请/释放内存，这样会严重的导致内存碎片化，降低内存的使用率。
②. 再者，每次插入元素的时候都要去申请内存，会有一次寻址的过程，时间效率低。
③. 指针结构很复杂，有大量的指针操作。
image
针对上面5.6所有的问题，提出了如上的结构。arData结构便是我们插入数据的结构，是一段连续的内存，在初始化/数组扩充时一次性内存申请好，这样内存便不会产生碎片化问题，并且我们看，hash冲突的时候是单链表，并且没有插入元素时候的双向链表，因为我们可以直接扫描数组便可以顺序/逆序访问插入的数据。
image
如上是最新的数据结构，最主要的区别是把7.0的两段内存转化为一段内存，算是在内存上的继续优化。他的内存申请是从下标-8位置申请的，然后移动指针到key1位置。
三. PHP7.0数组源码实现
3.1 PHP7.0数组的主要数据结构
image
Bucket结构便是我们所说的保存插入数据的结构。主要包括：key(字符串，如果是数字下标，转化位字符串), value, h(只会计算一次，如果是数组下标，直接把key作为h)。
image
这便是PHP7.0的数组结构，我后面讲全部是用7.0结构讲，比较清晰。nNextFreeElement是无key值存储时使用的数据，用来分配key值。
3.2 PHP数组的hash方法
image
如上是php的hash源码，看一眼容易把人瞎蒙，然而把它简化一下便是：
image
简单讲一下。其中源码中把 hash*33 转化为 (hash<<5) + hash
在一个就是，使用了循环展开策略，减少不必要的循环判断，在一个是连续的执行相同的指令，提高指令的cache命中率。可以看着：https://en.wikipedia.org/wiki/Loop_unrolling
那么计算出hash值来之后，并不是我们想要的下标，因为很有可能超过了hashmask值，所以需要一步计算来得到index。
•7.0：
hashmask = tablesize – 1; //tablesize一定是2的指数倍，和申请内存有关系，后面讲
h = hashcode & hashmask; //计算index
hashmask=7(10)=111(2) //十进制下的7转为二进制下的111
0<=h<8 //所有值 & hashmask 一定在0~7之间
•7.1：
hashmask = -tablesize;
h = hashcode | hashmask;
hashmask=-8(10)=11111000(2补码)
-8<=h<=-1
7.1的结构因为是hash负下标，所以用的另一种计算策略，大同小异。
3.3 PHP数组插入数据
image
大致流程如上，看一下就好。讲一下插入数据的结构变化。
image
在我们插入key6这个key值之后，在arData数据往后排，我们假设他与key1的hash冲突，所以使用链地址法，直接插入到链表首部。
3.4 PHP数组删除数据
在上面的结构，假如我们删除key1，会有两种考虑。
①. 删除该元素之后，我们是否要保证空间的利用率，把后面的数据移动，覆盖当前位置。
②. 删除元素之后，直接把该位置空出。
其实第一种策略是不可接受，因为这样会导致时间复杂度退化为O(n)，而第二种策略，我们控制当前位置之后，我们可以在内存扩充时，把这些空位置给删除掉即可。
image
3.4 PHP数组内存申请及rehash
假设我们要在如下结构中插入key9
image
发现当前arData已经满了，所以我们申请新内存(初始大小位2，以2的倍数不断扩充)，把所有数据以内存的形式copy过去，然后扫描数组，把无用的数据给删除掉(用移动后面元素的策略)。因为nTableMask数值改变了然后进行rehash。
这里有一个点值得提一下：把原数据copy过去的时候，我们可以选择遍历原先的数组，把有用的数据copy过去，也可以先把原内存的数据复制到新内存的位置，然后去遍历数组去移动数据。PHP实现选择了第二种，这样考虑应该是我们删除元素的次数比较少，直接以内存的形式copy数据要比遍历copy的速度快，在权衡之下选择了第二种。
image
结构变化如上图。
四. PHP数组的可优化点
4.1 PHP数组的退化案例
本案例参考的鸟哥的博客。
image
大概测了一下
image
我们可以看到，时间效率差别很大。我们来分析一下为什么会这样。
•插入元素:key=0,165536,265536,….,65535*65536
•插入元素特点:h=key&65535=0,生成绝对的hash冲突导致退化1*****00000000&0****011111111=0
•大致的插入计算次数：1+2+3+4+5+…+65536(每次插入都会冲突，从而会去查询是否有相同的key值，所以会有扫描的次数总和如此)
•导致插入元素时间复杂度退化为O(n*(1+n)/2)=O(n^2)
那么655362在计算机1s处理108运算的情况下，大概36s以上，所以运行结果算是可预期的。
image
4.2 可进行优化的策略
我们参考Java中hashtable的实现来使用红黑树解决这个问题。
•①.设定链表冲突长度的阀值
•②.当链表长度超过阀值的时候，以key值为键值进行红黑树的转化，key全是字符串，所以我们可以以key的字典序进行排序
•③.Hashtable的指针指向树根
•④.增删查改，不断对红黑树结构进行调整
•⑤.使增删查改时间复杂度达到最差为O(logn)
我们来看下结构的变化为：
image
如果不了解红黑树，可以去参考一下《算法导论》中的详解
