-
极资源官方
- 热度7490℃
数组
定义一个数组，需要给定一个长度，每个位置都有一个下标，也就是这个位置的地址(存储地址，0x00000001之类的)。每个数组定义完成，第一个元素的索引都是从0开始。这里的0不是指存储地址。
定义了长度的数组假如要扩容，那么只能跟存储空间申请一个更大的连续的存储空间，将这些值复制过去，然后再将原本的数组删除。
查询的时候，数组查询非常的方便，因为我们已经知道了地址，所以查询数组任何一项的时间复杂度都是O(1)
但是想要插入数据和删除数据，时间复杂度却是O(n)，这是数组这个数据结构的劣势。
删除数据是要将该数据删除之后，将后面的元素往前靠拢。
链表
链表跟数组是完全不同的两种数据结构。数组需要定义一个长度，但是链表不需要。链表位置由操作系统随机分配，不过不用担心，链表的每个元素都记录了下一个元素的位置信息。像是一个挖宝游戏，你通过藏宝图的信息一步步找到最后的宝藏一样。
链表的插入与删除是非常方便的，只要将他们对于下一个元素的地址进行修改一番就能完成。时间复杂度也是O(1)
而链表的查询是这个数据结构的劣势，需要从头开始一个个查询过去，时间复杂度是O(n)
散列表(哈希表)
散列表也可以叫哈希表，这是一种数据内容和数据存放地址之间的映射关系。常用的字典就是这种数据结构。键值对是接触且使用的最为广泛的一种数据结构了。比如说他把apple映射成数组的索引0。每次查询apple的时候，就是查询索引0的值。
| 散列表(平均) | 散列表(最糟) | 数组 | 链表 | |
|---|---|---|---|---|
| 查找 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(1) | O(n) | O(n) | O(1) |
| 删除 | O(1) | O(n) | O(n) | O(1) |
数组和链表两个数据结构相结合，能够实现一个哈希表。也是最常用的一种方法——拉链法。
根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
哈希应用的地方有加密算法，和散列表。所以看到加密有hash方法，不用迷糊，只是不同应用而已。
上一篇:
PHP快速排序
下一篇:
PHP排序后进行二分查找
友情提示：垃圾评论一律封号...