Java数据结构和算法

Java数据结构和算法

数据结构

线性数据结构：常见的有一维数组，线性表，栈，队列，双队列，串。

非线性数据结构：常见的有：多维数组，集合，树，图，散列表(hash).

延申阅读

排序算法

查找算法

线性结构

• 1. 数组

特点：我们都知道数组中的元素在内存中连续存储的，可以根据是下标快速访问元素，因此，查询速度很快，然而插入和删除时，需要对元素移动空间，比较慢。

数组使用场景：频繁查询，很少增加和删除的情况。

• 1. 链表

特点：元素可以不连续内存中，是以索引将数据联系起来的，当查询元素的时候需要从头开始查询，所以效率比较低，然而添加和删除的只需要修改索引就可以了

使用场景：少查询，需要频繁的插入或删除情况

• 1. 队列

特点：先进先出，

使用场景：多线程阻塞队列管理非常有用

• 1. 栈

特点：先进后出，就像一个箱子，

使用场景：实现递归以及表示式

• 1. 串

串：也称字符串，是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat[]来进行储存。

KMP算法： 这个算法一定要牢记，Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是：在字符串比对的时候，主串的比较位置不需要回退的问题。

• 1. 数组与链表的区别

数组连续，链表不连续（从数据存储形式来说）

数组内存静态分配，链表动态分配

数组查询复杂度0（1），链表查询复杂度O(n)

数组添加或删除，复杂度o（n）,链表添加删除，复杂度O（1）

数组从栈中分配内存。链表从堆中分配内存。。

非线性结构

1：多维数组

一维数组前面咱也提到了，多维数组无非就是String ,int等。Java里面很少提供这样的工具类，而java里面tree和图底层的native方法用了多维数组来储存。

2：集合

由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

3：树

树形结构，作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成，可以有多个子节点。树，显然是由递归算法组成。

4：Hash

Hash概念：

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），变换成固定长度的输出，该输出就是散列值。一般通过Hash算法实现。

所谓的Hash算法都是散列算法，把任意长度的输入，变换成固定长度的输出，该输出就是散列值.（如：MD5,SHA1,加解密算法等）

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Java中的hashCode：

我们都知道所有的class都是Object的子类，既所有的class都会有默认Object.java里面的hashCode的方法，如果自己没有重写，默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。

最大的特性是：不同的对象，不同的值有可能计算出来的hashCode可能是一样的。

八大排序算法

• 一、直接插入排序（Insertion Sort）
• 二、希尔排序（Shell Sort）
• 三、选择排序（Selection Sort）
• 四、堆排序（Heap Sort）
• 五、冒泡排序（Bubble Sort）
• 六、快速排序（Quick Sort）
• 七、归并排序（Merging Sort）
• 八、基数排序（Radix Sort）

七大查找算法

• 1. 顺序查找
• 1. 二分查找
• 1. 插值查找
• 1. 斐波那契查找
• 1. 树表查找
• 1. 分块查找
• 1. 哈希查找