数据结构与算法

背景

最近在准备面试,结合之前的工作经验和近期在网上收集的一些面试资料,准备将Android开发岗位的知识点做一个系统的梳理,整理成一个系列:Android应用开发岗 面试汇总。本系列将分为以下几个大模块:
Java基础篇Java进阶篇常见设计模式
Android基础篇Android进阶篇性能优化
网络相关数据结构与算法
常用开源库、Kotlin、Jetpack

注1:以上文章将陆续更新,直到我找到满意的工作为止,有跳转链接的表示已发表的文章。
注2:该系列属于个人的总结和网上东拼西凑的结果,每个知识点的内容并不一定完整,有不正确的地方欢迎批评指正。
注3:部分摘抄较多的段落或有注明出处。如有侵权,请联系本人进行删除。

本节内容只对部分数据结构做概述,算法的学习和刷题,文章底下会给出推荐的公众号

一、八大数据结构分类

链接

二、常见集合

1 ArrayList

  • 数据结构:ArrayList的底层数据结构是一个数组,数组元素的类型为Object类型,对ArrayList的所有操作底层都是基于数组的。
  • 线程不安全:由于ArrayList进行添加元素的操作的时候是分两个步骤进行的,即第一步先在object[size]的位置上存放需要添加的元素;第二步将size的值增加1。由于这个过程在多线程的环境下是不能保证具有原子性的,因此ArrayList在多线程的环境下是线程不安全的。
  • 继承关系: ArrayList继承AbstractList抽象父类,实现了List接口(规定了List的操作规范)、RandomAccess(可随机访问)、Cloneable(可拷贝)、Serializable(可序列化)。
  • 扩容机制: 将原元素数组的长度增大1.5倍(oldCapacity + (oldCapacity >> 1)),然后对扩容后的容量与minCapacity进行比较:
    ① 新容量小于minCapacity,则将新容量设为minCapacity;
    ②新容量大于minCapacity,则指定新容量。
    最后将旧数组拷贝到扩容后的新数组中。
  • 默认大小:在没有指定ArrayList大小的时候,默认为10。
  • 增删改查效率:
    ①查询、修改:由于是基于数组的,可以通过数组下标直接定位到元素,因此查询和修改的时间复杂度为O(1)
    ②增加、删除:同理,在增加和删除元素时,增/删某个位置的元素后,后面的元素需要进行位移,因此时间复杂度为O(n)

链接

2 LinkedList

  • 数据结构:LinkedList的底层数据结构是一个双向链表,数组元素的类型为Object类型,包含两个重要的成员:header 和 size。
  • header: 是双向链表的表头,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。
  • 继承关系: 同ArrayList。
  • 扩容机制: 不需要扩容机制,因为添加元素,是改变头尾节点指向的元素。
    增删改查效率:
    ①查询、修改:由于是基于双向链表的,只能通过头尾节点去遍历定位到元素,因此查询和修改的时间复杂度为O(n)
    ②增加、删除:效率是比较高的,因为只涉及到指向节点的指针的改变,找到相应的节点之后进行替换设置好指针的前后指向地址,因此时间复杂度为O(1)

3 HashMap

3.1 数据结构

用到了4中数据结构:数组、链表、哈希表、红黑树(Java 8引入)

3.2 map.put(k,v)实现原理

(1)首先将k,v封装到Node对象当中(节点)。
(2)然后它的底层会调用K的hashCode()方法得出hash值。
(3)通过哈希表函数/哈希算法,将hash值转换成数组的下标,
①下标位置上如果没有任何元素,就把Node添加到这个位置上。
②如果下标对应的位置上有链表。此时,就会拿着k和链表上每个节点的k进行Object.equal()。
③如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。
④如其中有一个equals返回了true,那么这个节点的value将会被覆盖。

3.3 map.get(k)实现原理

(1)先调用k的hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。
(2)通过上一步哈希算法转换成数组的下标之后,在通过数组下标快速定位到某个位置上。
①如果这个位置上什么都没有,则返回null。
②如果这个位置上有单向链表,那么它就会拿着K和单向链表上的每一个节点的K进行equals,如果所有equals方法都返回false,则get方法返回null。
③如果其中一个节点的K和参数K进行equals返回true,那么此时该节点的value就是我们要找的value了,get方法最终返回这个要找的value。

3.3 HashMap红黑树原理分析

相比 jdk1.7 的 HashMap 而言,jdk1.8最重要的就是引入了红黑树的设计,红黑树除了插入操作慢其他操作都比链表快

  • 转化时机:
    当hash表的单一链表长度超过 8 个的时候,数组长度大于64,链表结构就会转为红黑树结构。当红黑树上的节点数量小于6个,会重新把红黑树变成单向链表数据结构。
  • 为什么要这样设计呢?
    好处就是避免在最极端的情况下链表变得很长很长,在查询的时候,效率会非常慢。

3.4 其他知识点

  • 初始容积:数组大小为16,即2的4次方
  • 扩容时机:容积大小(默认16) x 负载系数(0.75)= 12,即当数组达到12时,记性扩容,扩容成之前的两倍,即16 x 2 = 32.
  • hash算法:对key值进行hashCode,在对hash值进行取模,如:hash=1001,取模后为1,Hashmap中有对取模后的值进行二次hash(目的:让hash值尽量分散,避免碰撞),最终作为数组的下边,将元素存入数组。
  • hash碰撞:当hash=1和hash=1001,假设进行取模后,hash都为1,则出现hash碰撞,此时,引入链表,通过头插法,将最新的值放入链表的最前面
  • 什么时候创建数组:第一次put()时
  • 树化时机:单一链表长度超过 8 个的时候,数组长度大于64,链表结构就会转为红黑树结构。当红黑树上的节点数量小于6个,会重新把红黑树变成单向链表数据结构。

链接

三、算法

算法的学习和刷题是一个长期的过程,这里推荐一个不错的学习算法的地方:
labuladong 的算法小抄

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,393评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,790评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,391评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,703评论 1 270
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,613评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,003评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,507评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,158评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,300评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,256评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,274评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,984评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,569评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,662评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,899评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,268评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,840评论 2 339