1.11Java-数据结构

柔光的暖阳◎ 2024-04-01 09:02 65阅读 0赞

**目录**

1.11.1前言

1.11.2什么是数据结构

1.11.3数组（Array）

1.11.4链表（Linked List）

1.11.4.1单链表

单链表结点数据结构

1.11.4.2双链表

1.11.5栈(Stack）

1.11.6队列（Queue）

1.11.7树（Tree）

1.11.8堆（Heap）

1.11.9散列表（Hash）

1.11.9.1什么是Hash()函数

1.11.9.2Hash()

1.11.9.2.1Hash()如何建立映射的呢？

1.11.9.2.2Hash冲突

1.11.9.2.3冲突避免

1.11.9.2.4解决冲突方法

1.11.9.2.5常用的Hash函数

--------------------

## 1.11.1前言 ##

由于数据结构是一门很重要的学科，而且我们这里只对学习一些java初级阶段所涉及到的简单理论进行学习，更为系统的数据结构可以在博主的数据结构专刊进一步学习。

## 1.11.2什么是数据结构 ##

现实世界中，客观事物都是相互联系的，所以数据之间也必然存在着联系。数据结构（Data Structure）就是指数据元素及其相互之间的关系。  
数据元素之间的相互联系称为数据的逻辑结构。根据数据元素之间关系的不同特性，数据结构可以分为集合、线性结构、树型结构、图结构4类基本结构。

（1）集合：数据元素间的关系同属一个集合，除此之外，别无其它关系。

（2）线性结构：结构中的元素间存在一对一的关系。

（3）树型结构：结构中的元素间存在一对多的关系。

（4）图（网状）结构：结构中的元素间存在多对多的关系

常用的数据结构有：数组（Array）、链表（Linked List）、栈（Stack）、队列（Queue）、堆（Heap）、树（Tree）、图（Graph）、散列表（Hash）等。

## 1.11.3数组（Array） ##

**数组（Array）**：数组是有序元素的序列，在内存中的分配是连续的，数组会为存储的元素都分配一个下标（索引），此下标是一个自增连续的，访问数组中的元素通过下标进行访问；数组下标从0开始访问；

![1d74e07fde73413d83a3ee3a3bce32db.png][]

**优点**：查询快

数据长度固定，且下标按顺序自增，知道数据的起始位置，顺着就能找到所有元素。

**缺点**：增删慢

由于每个元素的位置是固定，且是按顺序的，如果中间位置一个元素被删，或者增加一个元素，那么此位置后的所有元素都要移动。

## 1.11.4链表（Linked List） ##

### 1.11.4.1单链表 ###

#### 单链表结点数据结构 ####

![aea729f3fe9f4ad98b61e301e485f4ee.png][]

**单链表**

![c17550e2d6434a98b92ea4fcd6551689.png][]

单链表中，每个结点的数据域存储线性表的数据元素，每个结点的指针域存储其后继元素所在结点的地址，可以通过每个结点的指针域访问到其后继结点。

**优点**：增删元素快

每个结点都有指向下一个结点的指针索引，增删元素只需要修改指针即可

![82cab34e6029401c9587777a4d187e20.png][]

**缺点**：查找慢

查询元素，需要从头遍历结点，直到找到想要查询的元素

### 1.11.4.2双链表 ###

单向链表的每一个结点只有一个指向其后继结点的指针域，此时对每一个结点可以方便地查找到其后继结点，但要操作它的前驱结点，则必须从头结点开始依次搜索一遍。若某一个线性表的操作常常涉及到某一结点的前驱结点，则可以利用双向链表。  
双向链表（Double Linked List）的每一个结点由本身的数据元素信息、指向前驱结点的指针域和指向后继结点的指针域三部分组成。双向链表也可以带头结点，也可以采用循环链接。

## 1.11.5栈(Stack） ##

栈（Stack）又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问只能在某一端进行的线性数据结构。

堆栈允许插入、删除和访问的一端称为栈顶（Top），另一端称为栈底（Bottom）。栈顶的第一个元素被称为栈顶元素。不含数据元素的空表称为空栈。  
向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。  
堆栈的性质决定它的数据是按“先进后出”的顺序被访问，即最先存储的元素最后被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为“LIFO”（Last\_In，First\_Out）。

## 1.11.6队列（Queue） ##

**队列**（Queue）简称队，也是一种特殊的线性表，可定义为只允许在表的一端进行插入，而在表的另一端进行删除的线性结构。队列允许插入的一端称为**队尾**（Rear），允许删除的一端称为**队首**（Front）。

向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。

由于队列的插入和删除分别在不同的两端进行，因而先插入者自然先从另一端删除，所以队列具有“先进先出”的特点，简称为**FIFO**（First-In，First-Out）。

## 1.11.7树（Tree） ##

**树**(Tree) 是n (n≥0) 个结点的有限集合T，不含有任何结点（元素）的树称为空树，否则它满足如下两个条件：有且仅有一个称为**根**(Root)的结点；其余所有结点被分成m (m≥0)个互不相交的集合T1,T2,T3,…,Tm，其中每个集合又构成一棵树，称其为根结点的**子树**(SubTree)。树的根结点Root是每棵子树根结点的前驱，每棵子树的根结点是根结点Root的后继。  
树的分类有非常多种，平衡二叉树（AVL）、红黑树RBL（R-B Tree）、B树（B-Tree）、B+树（B+Tree）等。

## 1.11.8堆（Heap） ##

**堆（Heap）**：堆可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

## 1.11.9散列表（Hash） ##

### 1.11.9.1什么是Hash()函数 ###

由于顺序结构和平衡二叉树，元素关键码与其存储位置之间没有对应的关系，因此在搜索元素时，需要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( logN)。

因此，我们定义一个理想的环境，不需要比较，直接可以从表中取出元素。这时候就需要映射

我们之前提到过映射，它是一种对应关系，如身份证号与个人，一一对应。

我们可以通过函数使元素的存储位置与关键码建立映射关系，查找只需要通过函数就可以。这个函数就是hsah()。

### 1.11.9.2Hash() ###

#### 1.11.9.2.1Hash()如何建立映射的呢？ ####

首先先来了解HashCode:

**HashCode**就是通过Hash函数得来的，通俗的说，就是通过某一种算法得到的，HashCode就是在Hash表中有对应的位置。

插入元素 ：根据待插入元素的关键码，用hash()计算出该元素的存储位置  
搜索元素：根据待搜索元素的关键码，用hash()计算出该元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。  
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)。

**注：**

> 用Hash函数计算出的存储位置，不是物理地址！！，而是在该表中的位置（也就是HashCode）。
> 
> 因为Hash函数计算出的是HashCode,而这个HashCode代表的是存入该表的位置。
> 
> **hashcode代表对象的地址说的是对象在hash表中的位置，物理地址说的对象存放在内存中的地址**

例如：数据集合\{2，4，8，6，7，5\}；  
哈希函数设置为：[hash][](key) = key % capacity; capacity为存储元素底层空间总的大小。

![2bb5633069d94ef0ac32b4cf8ae70669.png][]

同时，我们也能发现一个严重的问题，如果储存位置重复了怎么办？这就是我们接下来要讨论的hash冲突。

#### 1.11.9.2.2Hash冲突 ####

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

#### 1.11.9.2.3冲突避免 ####

Hash函数设计原则

*  哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
 *  哈希函数计算出来的地址能均匀分布在整个空间中
 *  哈希函数应该比较简单

#### 1.11.9.2.4解决冲突方法 ####

**1.开放定址法**

> 简单来说就是一旦发生了冲突，通过某种探测技术，去寻找下一个空的散列地址，若能遇到一个开放的地址（即该地址单元为空）为止。之后如果要添加元素就在该地址添加。
> 
> 查找探测到开放的地址则表明表 中无待查的关键字，即查找失败。

所谓的探测技术

> 开放定址法为产生冲突的地址H(key)求得一个地址序列：
> 
> H0, H1, H2, …, Hs
> 
> 其中：
> 
> H0 = H(key)  
> Hi = (H(key) + di) % m
> 
> 其中m为表的长度，i = 1, 2, 3, …, n，对增量di有三种取法：
> 
> 1.线性探测再散列  
> di = 1, 2, 3, …, m - 1
> 
> 2.二次探测再散列  
> di = 12, -12, 22, -22, 32, -32, …, k2, -k2 （k <= m / 2）
> 
> 3.伪随机探测再散列  
> di = 伪随机数序列 （具体实现时，应建立一个伪随机数发生器，（如i = (i + p) % m），并给定一个随机数做起点。）  
>

**2.链地址法（拉链法**）  
这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。  
Java 中 HashMap 解决 Hash 冲突就是利用了这个方法。

示例：

关键字序列为\{19，14，23，01，68，20，84，27，55，11，10，79\}，散列函数H（k）=K %13，用链地址法处理冲突，建立表如下：

![6c93c83e496641dd8a459c567a4e177d.png][]

取余后相同的“串”在一起

**3.再哈希法**  
这种方法是同时构造多个不同的哈希函数：

Hi = RHi(key) (i = 1，2，…，k)

当哈希地址Hi = RHi(key) 发生冲突时，再计算Hi = RHi(key) ……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

**4.建立公共溢出区**  
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

#### 1.11.9.2.5常用的Hash函数 ####

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。常用Hash函数有:

1.直接寻址法

> 取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a \* key + b，其中a和b为常数（这种散列函数叫做自身函数)

2.数字分析法

> 分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几夹就会很大、俱是我们发现焦月具的后几位表示月份犯昊体月期的数字差别很大.如果思后面的数字来构成散列地址.则决突的几夹会明显.隆低。因此数字分近法就是找出数字的规律.尽可能利用这些数据来构造冲突较低的散烈地址。  
>

3.平方取中法

> 取关键字平方后的中间几位作为散列地址。

4.折叠法

> 将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址

5.随机数法

> 选择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。

6.除留余数法

> 取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。  
> 键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。  
>

[1d74e07fde73413d83a3ee3a3bce32db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f5560e145ac342128058f23a1c896cb8.png
[aea729f3fe9f4ad98b61e301e485f4ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4b9bf3455c054367aa1abb1c33504100.png
[c17550e2d6434a98b92ea4fcd6551689.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d17f4ab204f94ffa8c0167fcbe6a5615.png
[82cab34e6029401c9587777a4d187e20.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/11d8f31b94ae4d359bea8610410a2bd2.png
[hash]: https://so.csdn.net/so/search?q=hash&spm=1001.2101.3001.7020
[2bb5633069d94ef0ac32b4cf8ae70669.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f9c6a905f13748ca836f4cece8af2cf5.png
[6c93c83e496641dd8a459c567a4e177d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6333eb54afc443fd80eefcbc59a7bbfc.png