数据结构与算法基础

基本概念

什么是数据结构?

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的科学。

逻辑结构

逻辑结构,是指数据对象中数据元素之间的相互关系。

类型 说明 数据结构
集合结构 集合结构中的元素除了同属于一个集合外,它们之间没有其它关系。 链表、Set
线性结构 线性结构中的元素之间是一对一的关系。 串、数组、链表、栈、队列、哈希
树型结构 属性结构中的元素之间存在一种一对多的层次关系。
图形结构 图形结构的数据元素是多对多的关系。

物理结构

物理结构,是指数据的逻辑结构在计算机中的存储形式。

类型 说明
顺序存储结构 是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。
链接存储结构 把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。
数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关联数据元素的位置。

算法时间复杂度

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。 算法的时间复杂度,也就是算法的时间量度,记作:T(n) = O(f(n))。 它表示随问题规模n的增大,算法执行时间的增长量和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。 其中f(n)是问题规模n的某个函数。 一般情况下,随着n增大,T(n)增长最慢的算法为最优算法。

常见的时间复杂度

执行次数函数 非正式术语 排序
12 O(1) 常数阶 1
5log2n+20 O(logn) 对数阶 2
2n+3 O(n) 线性阶 3
2n+3log2n+19 O(nlogn) nlogn阶 4
3n2+2n+1 O(n2) 平方阶 5
6n3+2n2+3n+4 O(n3) 立方阶 6
2n O(2n) 指数阶 7

常用数据结构的时间复杂度

数据结构 时间复杂度
哈希 O(1) 常数阶
O(log(n)) 对数阶
数组 O(n) 线性阶
链表 O(n) 线性阶

常用排序算法的时间复杂度

排序算法 时间复杂度(平均)
快速排序 O(n log(n))
归并排序 O(n log(n))
堆排序 O(n log(n))
冒泡排序 O(n^2)
插入排序 O(n^2)
选择排序 O(n^2)
桶排序 O(n+k)
基数排序 O(nk)

数据结构图解

数组

数组-图解.png
数组-图解.png

链表

链表-图解.png
链表-图解.png

哈希

HashMap/HashTable

HashMap-图解.png
HashMap-图解.png

ConcurrentHashMap

ConcurrentHashMap-图解.png
ConcurrentHashMap-图解.png

栈-图解.png
栈-图解.png

队列

队列-图解.png
队列-图解.png

树

图

对比

数据结构 优点/特点 缺点 适用场景
数组 插入快,如果知道下标,可以非常快的存取 查找慢,删除慢,大小固定 数量固定的元素集合
有序数组 比无序数组查找快 删除和插入慢,大小固定 数量固定的有序元素集合
提供后进先出方式的存取 存取其它项很慢 1. 检验源程序中的小括号、中括号、大括号是否匹配
2. 遍历树的节点
3. 辅助查找图的顶点
4. 波兰逆序表达式
队列 提供先进先出方式的存取 存取其它项很慢
链表 插入快,删除快 查找慢
二叉树 查找、插入、删除都快(如果树保持平衡) 删除算法复杂
红黑树 查找、插入、删除都快。
树总是平衡的
算法复杂
2-3-4树 查找、插入、删除都快。
树总是平衡的。
类似的树对磁盘存储有用。
算法复杂
哈希表 如果关键字已知则存取极快,插入快。 1. 删除慢,如果不知道关键字则存取很慢。
2. 基于数组,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重
3. 对存储空间使用不充分。
对现实世界建模 有些算法慢且复杂 -

树的分类

树的分类 说明
二叉树 树的任意节点至多包含两棵子树。
满二叉树 叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点。
完全二叉树(堆) 对于一颗二叉树,假设其深度为d(d>1)。除第d层外的所有节点构成满二叉树,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树。
二叉查找树(二叉搜索树、BST) 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也分别为二叉查找树;
没有键值相等的节点。
平衡二叉树(AVL) 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,同时,平衡二叉树必定是二叉搜索树。
红黑树 红黑树是一颗特殊的二叉查找树,除了二叉查找树的要求外,它还具有以下特性:
- 每个节点或者是黑色,或者是红色。
- 根节点是黑色。
- 每个叶子节点(NIL)是黑色。[注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
- 如果一个节点是红色的,则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
B树(B-tree、B-树) - 根结点至少有两个子女(如果B树只有一个根节点,这个根节点的key的数量可以为[1~m-1])
- 每个非根节点所包含的关键字个数 j 满足:⌈m/2⌉ - 1 <= j <= m - 1,节点的值按非降序方式存放,即从左到右依次增加
- 除根结点以及叶子节点以外的所有结点的度数正好是关键字总数加1,故内部节点的子树个数 k 满足:⌈m/2⌉ <= k <= m
- 所有的叶子结点都位于同一层
B+树 m阶B+树是m阶B-tree的变体,它的定义大致跟B-tree一致,不过有以下几点不同:
- 有n棵子树的结点中含有n个关键字,每个关键字不保存数据,只用来索引,所有数据都保存在叶子节点,其中⌈m/2⌉ <= n <= m
- 所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接
- 所有的非终端结点可以看成是索引部分,结点中仅含其子树(根结点)中的最大(或最小)关键字
- 通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点B+树
2-3树 2-3树是最简单的B-树(或-树)结构,其每个非叶节点都有两个或三个子女,而且所有叶都在统一层上。
2-3树不是二叉树,其节点可拥有3个孩子。2-3树.png
B*树 B树是B+树的变体,除了B+树的要求之外,还有以下特性:
- ⌈m
2/3⌉ <= n <=m 这里的n是除根节点之外的内部节点的键
- 增加内部节点中兄弟节点的指针,由左边指向右边B*树
字典树(Trie树、前缀树)) 是一种树形结构,在解决字符串相关问题中非常高效。其提供非常快速的检索功能,常用于搜索字典中的单词,为搜索引擎提供自动搜索建议,甚至能用于IP路由选择。
这些单词以从上到下的方式存储,其中绿色节点“p”,“s”和“r”分别表示“top”,“thus”和“their”的末尾。字典树

对比

时间复杂度 说明
二叉树 O(n) 如果树中插入的是随机数据,则执行效果很好。
如果插入的是有序数据(17,21,28,36,...)或者是逆序的数据(36,28,21,17,...),速度就变得特别慢。
因为当插入的数值有序时,二叉树就是非平衡的了。
而对于非平衡树,它的快速查找(插入、删除)指定项的能力就丧失了
红黑树 查找、插入、删除:O(logN)O(2*log2N) 为了能以较快的时间O(logN)来搜索一棵树,需要保证树总是平衡的。
红黑树的平衡是在插入(或删除)过程中,对一个要插入(或删除)数据项,检查会不会破坏树一定的特征。
如果破坏了,程序就会进行纠正,根据需要更改树的结果。
通过维持树的特征,保持了树的平衡。
平衡查找树(AVL) 查找:O(log(n)) 最早的一种平衡树,效率不如红黑树。
O(logn) 完全二叉树

Hashmap

hashmap的由来

数据结构 特点
数组 寻址容易,插入和删除困难,时间复杂度O(1)
链表 寻址困难,插入和删除容易,时间复杂度O(N)
哈希表(Hash table) 寻址容易,插入删除也容易(综合数组、链表的特性做出的链表的数组)

hashmap的特点

  • 基于Map接口实现
  • 允许null键/值
  • 非同步
  • 不保证有序(比如插入的顺序)
  • 也不保证序不随时间变化。

两个重要的参数

  • 容量(Capacity):buckets的数目。
  • 负载因子(Load factor):buckets填满程度的最大比例。

put函数的实现

  1. 对key的hashCode()做hash,然后再计算index;
  2. 如果没碰撞直接放到bucket里;
  3. 如果碰撞了,以链表的形式存在buckets后;
  4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树;
  5. 如果节点已经存在就替换old value(保证key的唯一性)
  6. 如果bucket满了(超过load factor*current capacity),就要resize。

get函数的实现

  1. bucket里的第一个节点,直接命中;
  2. 如果有冲突,则通过key.equals(k)去查找对应的entry
  3. 若为树,则在树中通过key.equals(k)查找,O(logn);
  4. 若为链表,则在链表中通过key.equals(k)查找,O(n)。

hash函数的实现

在get和put的过程中,计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标。

在Java 8之前的实现中是用链表解决冲突的,在产生碰撞的情况下,进行get时,两步的时间复杂度是O(1)+O(n)。因此,当碰撞很厉害的时候n很大,O(n)的速度显然是影响速度的。

因此在Java 8中,利用红黑树替换链表,这样复杂度就变成了O(1)+O(logn)了,这样在n很大的时候,能够比较理想的解决这个问题。

RESIZE的实现

当put时,如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例,那么就会发生resize。在resize的过程,简单的说就是把bucket扩充为2倍,之后重新计算index,把节点再放到新的bucket中。

图分类

图分类 说明
连通图
非连通图
有向图
带权图 -

搜索分类

搜索分类 说明
深度优先
广度优先 -

排序算法

排序算法 动画演示 介绍 描述
冒泡排序 冒泡排序.gif 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
3. 针对所有的元素重复以上的步骤,除了最后一个;
4. 重复步骤1~3,直到排序完成。
选择排序 选择排序 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 1. 初始状态:无序区为R[1..n],有序区为空;
2. 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
3. n-1趟结束,数组有序化了。
插入排序 插入排序 形象理解:打扑克抓牌
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
1. 从第一个元素开始,该元素可以认为已经被排序;
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5. 将新元素插入到该位置后;
6. 重复步骤2~5。
希尔排序(缩小增量排序) 希尔排序 1. 1959年Shell发明
2. 第一个突破O(n2)的排序算法
3. 简单插入排序的改进版。
4. 它与插入排序的不同之处在于,它会优先比较距离较远的元素。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:
1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
2. 按增量序列个数k,对序列进行k 趟排序;
3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
归并排序 归并排序 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 1. 把长度为n的输入序列分成两个长度为n/2的子序列;
2. 对这两个子序列分别采用归并排序;
3. 将两个排序好的子序列合并成一个最终的排序序列。
快速排序 快速排序 1. 快速排序由C. A. R. Hoare在1960年提出。
2. 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
3. 设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它左边,所有比它大的数都放到它右边,这个过程称为一趟快速排序。
1. 设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2. 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3. 从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]的值交换;
4. 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]的值交换;
5. 重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i,j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
堆排序 堆排序 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
2. 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
3. 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。
计数排序 计数排序 计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。 1. 找出待排序的数组中最大和最小的元素;
2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
4. 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
桶排序 桶排序 基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。 1. 设置一个定量的数组当作空桶;
2. 遍历输入数据,并且把数据一个一个放到对应的桶里去;
3. 对每个不是空的桶进行排序;
4. 从不是空的桶里把排好序的数据拼接起来。
基数排序 基数排序 基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。 1. 取得数组中的最大数,并取得位数;
2. arr为原始数组,从最低位开始取每个位组成radix数组;
3. 对radix进行计数排序(利用计数排序适用于小范围数的特点)。

对比

排序算法 时间复杂度 稳定性
冒泡排序 O(n2) 稳定
选择排序 O(n2) 不稳定
插入排序 O(n2) 稳定
希尔排序 O(n^1.25) 不稳定
归并排序 O(nlogn) 稳定
快速排序 O(nlogn) 不稳定
堆排序 O(nlogn) 不稳定
计数排序 O(n+k)
k是待排序列最大值
稳定
桶排序 O(n) 不稳定
基数排序 O(n) 稳定

应用场景

考虑因素 排序算法
小数据量 直接插入、选择、冒泡
大数据量效率 快速、归并、希尔、堆
稳定性 插入、冒泡排序、二叉树、归并、基数
快速、稳定 快速、归并
不稳定 快速、希尔、选择、堆

查找算法(未完待续)

查找算法 说明
顺序查找
二分查找
插值查找
斐波那契查找
树表查找
分块查找
哈希查找 -

代码实现

参考 data-structures-and-algorithms

常见问题

hashmap相关

hashmap工作原理

通过hash的方法,通过put和get存储和获取对象。 存储对象时,我们将K/V传给put方法时,它调用hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。 获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。 如果发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

hashmap中get和put的原理吗?equals()和hashCode()的都有什么作用?

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点。

hash的实现?为什么要这样实现?

在Java 1.8的实现中,是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。

如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

如果超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法。

为什么String, Interger这样的wrapper类适合作为键?

因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

我们可以使用自定义的对象作为键吗?

当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。

我们可以使用CocurrentHashMap来代替HashTable吗?

我们知道HashTable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。

Synchronized Map、ConcurrentHashMap、Hashtable区别

对比项 Synchronized Map ConcurrentHashMap Hashtable区别
锁定方式 Map锁定 Map锁定 永远不会锁定整个Map,而是将地图划分为多个段并对其进行锁定。
性能 最差 读写性能较好(推荐使用)
专门为并发使用而设计,即多个线程。默认情况下,它允许16个线程从Map读取和写入,无需任何外部同步。
多线程场景中表现不佳
如果许多读取器线程大于写入器线程数,它的性能会更好。

参考

在线动画

https://visualgo.net/zh

刷题网站

leetcode

博客

坚持原创技术分享,您的支持将鼓励我继续创作!
0%