作为一个PHP程序员，常用的数据结构是数组，基本上数组可以解决大部分问题，但是作为人，我们总是需要知道一些别的东西。数据结构大致分为三类：线性结构（数组、链表、栈、队列）、树、图~~~~了解几种简单数据结构的复杂性。数组：一种线性结构，使用连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；查找给定的值，需要遍历数组，将给定的关键字和数组元素一一比较，时间复杂度为O(n)，当然也可以使用算法进行优化，例如，对于有序数组，可以使用二分查找、插值查找、斐波那契查找等，可以将查找复杂度提高到O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，平均复杂度也是O(n)。线性链表：是一种线性结构。对于链表的增删改查等操作（找到指定操作位置后），只需要处理节点间的引用，时间复杂度为O(1)；查找操作需要遍历链表进行逐一比较，复杂度为O(n)。二叉树：属于树的一种。对于一个相对平衡的有序二叉树，进行插入、查找、删除等操作，平均复杂度为O(logn)。哈希表：与上述数据结构相比，哈希表中的增、删、查等操作具有非常高的性能。在不考虑hash冲突的情况下，只需要一次定位就可以完成，时间复杂度为O(1)。接下来，让我们看看哈希表是如何实现惊人的常数阶O(1)的。哈希表概述数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈、队列、树、图等都是从逻辑结构中抽象出来映射到内存中，这两种物理组织形式），数组是顺序存储结构，哈希表的骨干是数组。先标准化几个概念，接下来会用到。哈希表的本质是一个数组，数组中的每个元素称为一个框（bin），键值对存储在框内。f是哈希函数。哈希表的存储过程如下：根据key，用哈希函数计算出它的哈希值h(整数)=f(关键字)。假设盒子的个数为n，那么这个键值对应该放在第(h%n)个盒子里。如果盒子中已经存在键值对，则使用开放寻址方式或拉链方式解决冲突。哈希碰撞如果两个不同的键哈希函数得到的实际哈希值相同怎么办？也就是说，当我们对一个key进行hash运算，得到相同的hash值，再插入时，发现已经被其他元素占用了。其实这就是所谓的hashconflict，也叫h??ashcollision。哈希函数的设计非常重要。一个好的散列函数会保证计算尽可能简单，散列地址分布均匀。但是，我们需要明确一点，数组是一个连续的定长内存空间，再好的哈希函数也不能保证获取到的存储地址永远不会冲突。那么hash碰撞如何解决呢？hash冲突的解决方法有很多：open寻址法（发生冲突时，继续寻找下一个未被占用的存储地址）、zipper法。拉链法（借用其他图片）：负载因子（loadfactor）用来衡量哈希表的空/满程度，在一定程度上也可以反映查询的效率。计算公式为：loadfactor=totalkeyvaluelogarithm/box的个数loadfactor越大，哈希表越满，越容易产生碰撞，性能越低。所以，一般来说，当负载因子大于某个常数（可能是1，或者0.75等）时，哈希表会自动扩容。哈希表自动扩容时，一般会创建两倍于原来数量的箱子。因此，即使key的hash值不变，取箱数余数的结果也会发生变化。因此，所有键值对的存储位置都可能发生变化，这个过程也称为重新散列（rehash）。然而，哈希表的扩展并不总是能够有效解决负载因子过大的问题。假设所有key的hash值都一样，即使扩容后它们的位置也不会改变。虽然负载因子会降低，但是每个盒子实际存储的链表长度不会改变，所以哈希表的查询性能不会提高。所以你会发现哈希表有两个问题：如果哈希表中的框很多，扩容时需要重新哈希和移动数据，对性能影响很大。如果哈希函数设计不当，哈希表在极端情况下会变成线性表，其性能会极低。哈希函数的合理性极其重要。tip：不同的语言有不同的解决重哈希的方法。
