前言:
现在安卓面试, 对于数据结构的问题也越来越多了, 要求也越来越多, 所以我对于数据结构只能慢慢补起来了.(灬 灬)
Android 技能书系列:
Android 技能树 - 动画小结
Android 技能树 - View 小结
Android 技能树 - Activity 小结
Android 技能树 - View 事件体系小结
Android 技能树 - Android 存储路径及 IO 操作小结
Android 技能树 - 多进程相关小结
Android 技能树 - Drawable 小结
本文主要讲 数组, 链表, 散列表(哈希表).
当我们去看电影的时候, 我们知道电影院门口会有一个储物柜,
上面还会有连续的数字, 一个抽屉连着一个抽屉. 然后你就会把你的东西放在相应号码的小抽屉中, 然后进去看电影了.
我们在将数据存储到内存时候, 你请求计算机提供存储空间, 计算机会给你一个存储地址, 然后你把内容存进去. 就类似上面的储物柜.
线性表
线性表: 零个或多个数据元素的有限序列.
线性表顺序存储(数组):
如果你有三袋东西, 你一个抽屉只能存一袋东西, 这时候你就可以使用了连续三个柜子. 比如你使用了 01,02,03 号抽屉.
线性表的顺序存储结构: 用一段地址连续的存储单元依次存储线性表的数据元素.
然后别人来使用了 04 号抽屉, 这时候你朋友又给你一袋东西, 说帮忙也去存一下, 但是这时候因为 04 号抽屉已经被别人使用了, 而你们又因为要求大家的东西都按照顺序放在一起, 所以这时候你们只能重新找连续在一起的抽屉, 比如 08,09,10,11. 万一 12 号被人使用了, 然后你们又要再多存一袋物品呢??
这里我们看出数组的特点:
如果我们有四袋物品, 我们已经知道了第一袋物品在 N 号码的抽屉, 那么其他三个肯定在 N+1,N+2,N+3 号, 所以在查询的时候十分方便, 因为我们只需要知道一个的位置, 其他的位置都知道了.(所以查询起来很方便, 因为所有的位置都知道具体在哪个)
如果我们把 A 放在 01,B 放在 02,C 放在 03, 这时候我们说在 A 和 B 之间插入一个 D, 这时候我们需要把 B 和 C 都往后移动. 同理删除一个也是一样, 比如我们删除了 A,B 和 C 都要往前移动.(所以插入删除比较麻烦, 需要移动所有后面位置的数据)
如果你突然多了一个需要存储的物品, 而且已经不够放了, 那么需要全部重新移动到新的连续的存储地方.
类似我们在排队买车票, 突然半路有个人插队, 你们所有人都需要往后退后了一位; 最前面的人买好票走了一个, 你们所有人都可以往前前进一位.
数组 | 时间复杂度 |
---|---|
读取 | O(1) |
插入 / 删除 | O(n) |
线性表顺序存储(链表):
单链表:
不知道大家有没有看过类似古墓丽影类似的探宝电影.
它们的步骤就是先知道到了一个地点, 然后到了第一个目的地 A, 到了 A 之后根据线索才知道下一个目的地 B 在哪里, 然后再去 B, 然后这样下去 A-- B-- C --..... 这样, 一直到最终的藏宝地方. 没错, 我们的链表就是类似这种, 比如我们知道一共有四袋物品, 但是你不能直接知道最后一个物品在哪里, 你只能从第一个开始, 一个个找下去.
比如我们第一个存在了 01 号抽屉, 存储内容为 A, 同时告诉大家, 下一个物品在 05 号抽屉, 里面内容为 B, 同时再下一个在 08 号.
由上面的图我们可以知道, 结点由存放数据元素的数据域和存放后继节点地址的指针域组成.
由上面我们举例的古墓丽影的剧情可知, 我们不能直接知道最后一个线索在哪里, 只能一个个从头到尾查过去, 所以链表的读取会很慢; 但是我们如果想要插入和删除就很方便.
比如我们要插入一个新的结点:
比如我们要删除其中一个结点:
链表 | 时间复杂度 |
---|---|
读取 | O(n) |
插入 / 删除 | O(1) |
循环链表:
将单链表中终端结点的指针端改为指向头结点, 就使整个单链表形成一个环, 这种头尾相接的单链表称为单循环链表, 简称循环链表.
双向链表:
双向链表是在单链表的每个结点中, 再设置一个指向其前驱结点的指针域.
静态链表:
静态链表是为了让没有指针的高级语言也能够用数组实现链表功能.
这个我就直接用网上的截图来说明了:
静态链表是用类似于数组方法实现的, 是顺序的存储结构, 在物理地址上是连续的, 而且需要预先分配地址空间大小. 所以静态链表的初始长度一般是固定的. 然后在这个里面存的时候不仅存储数据域, 同时存入了下一个数组 index 的位置. 相当于我们上面的指针域换成了数组的 index 值.
散列表(哈希表):
由上面我们已经可以知道数组和链表各自的优势和缺点了.
操作 | 数组 | 链表 |
---|---|---|
读取 | 擅长(可以随机 / 顺序访问) | 不擅长(只能顺序访问) |
插入 / 删除 | 不擅长 | 擅长 |
有了上面的知识, 我们就可以引入散列表了, 我们用具体的故事需求来引入散列表:
如果你有一天开了一家水果店, 你会拿一个本子来记各种水果的价格, 因为大家知道数组对于读取来说很方便, 所以我们用一个数组来记录各种水果的价格, 并且是按照开头字母来进行顺序写入的.
这时候, 如果有人问 Apple, 你就查询一下价格, 但是如果水果很多, 甚至很多都是 A 开头的水果, 比如有 20 个 A 开头的水果, 这时候你只能知道 A 开头的水果是前面 20 个, 但是具体是哪个, 你又要一个个的查过来, 如果我们马上就知道 Apple 对应的数组 index 值就好了, 这样就马上知道在数组的哪个位置, 然后马上就可以读取出来了.
比如下图:
这样我们就在 index 为 2 的地方存储了苹果的价格, 然后在 index 为 8 的地方存储了香蕉的价格, 依次类推, 所有水果都记录进去, 这样顾客问你苹果价格时候, 你就马上知道在 index 为 2 的地方去读取.
而把 Apple 变为 2 是通过散列函数来实现的.
散列函数:
我们要实现上面的需求, 这个散列函数需要一些基本要求:
如果输入的内容相同时, 每次得到的值都相同, 比如你每次输入都是 Apple, 比如每次得到的结果都是 2, 不能一下子 2, 一下子 5.
如果不管输入什么值得到的结果都相同, 那么这个函数也没用, 你输入 Apple 和输入 Banana 得到的值都相同, 那么没有任何分辨作用.
散列函数需要返回有效的索引, 比如上面我们的数组的长度只有 40, 你输入 Pair 时候输出 100, 这样是无效索引.
根据上面的情况我们知道了, 我们输入不同的值的时候, 通过散列函数换算后, 最好的结果是每个值都是不同, 这样的话他们的 index 也不同.
但是如果我们的数组只有长度为 6, 但是我们有 7 种水果, 那么一定会有二个水果得到的 index 是相同的. 这时候我们称这种情况为冲突.
处理冲突的方式有很多, 最简单的办法就是: 如果二个键映射到了同一个位置, 就在这个位置存储一个链表.
这样, 我们在查询其他水果时候还是很快, 只是在查询 index 为 0 的水果时候稍微慢一点, 因为要在 index 为 0 的链表中找到相应的水果.
散列表操作 | 平均情况 | 最糟情况 |
---|---|---|
查找 | O(1) | O(n) |
插入 | O(1) | O(n) |
删除 | O(1) | O(n) |
我们可以看到:
散列表的查找 (获取给定索引处的值) 速度与数组一样快, 而插入和删除速度与链表一样快. 因此它具备了二者的有点
但是最糟情况下, 散列表的各种操作速度都很慢(比如都集中在 index 为 0 的链表下面, 则查询就跟链表查询一样了.)
所以针对最糟的情况, 我们需要:
较低的填装因子: 散列表使用数组来存储数据, 因此需要计算数组中被占用的位置数. (比如, 数组的长度为 10, 我们填入的数占用了其中三个, 则填装因子为 0.3; 如果填入的数正好把长度占满, 则填装因子为 1; 如果填入了 20 个, 则填装因子为 2.) 当填装因子太大了, 说明数组长度不够了, 我们就要再散列表中添加位置了. 称为调整长度.(一旦填装因子大于 0.7 就调整散列表的长度, 为此你首先创建一个更长的新数组, 通常将数组增长一倍)
良好的散列函数: 良好的散列好书让数组中的值呈均匀分布, 糟糕的散列函数让值扎堆, 导致大量的冲突.
这样我们以后想要知道某个水果价格, 只需要输入水果名字, 然后通过散列函数返回一个 index 值就可以去数组中找相应的价格了.
结语:
哪里错误请帮忙指正, thanks.
参考:
大话数据结构
算法图解
来源: https://juejin.im/post/5add7571f265da0b9f3fe1f9