数据结构与算法(一):数组、链表、哈希表
数组、链表、栈和队列、散列表是基础数据结构,几乎所有的高级开发语言都会涉及到这些数据结构,一些更复杂的数据结构也是基于基础数据结构的扩展。
基础数据结构是数据存储的基础理论,有必要彻底理解它。
数据存储结构可以分为 物理结构 和 逻辑结构。
物理结构又分为 线性结构 和 非线性结构
- 线性结构:如 顺序表,栈,队列,
- 非线性结构:如 图,树。
逻辑结构又分为 顺序存储结构 和 链式存储结构
- 顺序存储结构:如 数组。
- 链式存储结构:如 链表。
注意:某些复杂的数据结构是可以基于不同的数据结构类型来实现的,如 二叉树,是一种逻辑结构,也可以依托于物理上的数组或链表来实现。
数组
概念
数组(Array):是有限个相同类型的变量所组成的有序集合,数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。
数组在内存中是 顺序存储,在内存中是占用一块连续的内存空间,数组元素之间紧密排列,即不能打乱元素排列顺序,也不能跳过某个存储单元进行存储。
操作
读取元素
由于数组在内存中顺序存储,只要给出一个数组下标,就可以读取到应用的数组元数。数组下标从 0 开始,给出的数组下标必须在数组的长度范围之内,否则出现数组越界。
更新元素
把数组中某一个元数的值替换为一个新值。直接根据数组下标,赋给该元数新值。
插入元素
尾部插入:尾部插入最简单,直接在尾部追加。
中间插入:稍许复杂,需要把插入位置的元素及后面的元素向后移动,为插入元素腾出空间。
超范围插入:因数组的容量在创建时就确定的,如果需要超范围插入,就涉及数给扩容,通常是创建一个新数给,为旧数组的 2 倍,在把旧数组中的元素全部复制到新数组。
删除元素
根据元素下标删除,实际是把要删除的元素的后面元素向前挪动 1 位,覆盖要删除的元素。若没有顺序要求,可将最后一个元素赋值给要删除的元素的位置,这就无须进行大量的元素移动。
优势和劣势
- 优势:高效的访问性能,只需给出下标,就可找到对应的元素。
- 劣势:体现在插入和删除元素方面。因数组元素是连续紧密存储在内存在,插入、删除操作会导致大量元素被迫移动,影响效率。
通常来说,数组适合读操作多,写操作少的场景。
链表
链表(Linked list):是一种在物理上 非连续、非顺序的数据结构,由若干节点(node)所组成。
链表在内存中的存储方式是 随机存储,这样可以有效地利用零散的碎片空间。
单向链表
单向链表 的每一个节点仅包含两部分,一部分是存放数据的变量 data,另一部分是指向下一个节点的指针 next 。通过指针把数据完整地链接起来。
第 1 个节点被称为头节点,最后 1 个节点被称为尾节点,尾节点的 next 指针指向空。
单向链表只能一级一级,单线传递查找。
双向链表
双向链表 比单向链表稍微复杂一些,每一个节除了拥有 data 和 next 指针,还多了指向前置节点的 prev 指针。
基本操作
查找节点
只能从头节点开始,根据节点的 next 指针向后一个一个节点逐一查找。
更新节点
先查找节点,把旧数据替换成新数据即可。
插入节点
尾部插入:最简单,把最后一个节点的 next 针指指向新插入的节点即可。
头部插入:把新节点的 next 指针指向原先的头节点,把新节点变为链表的头节点。
中间插入:插入位置的前置节点的 next 指针指向插入的新节点,新节点的 next 指针指向前置节点的 next 指针原先指向的节点。
删除元素
尾部删除:最简单,把倒数第 2 个节点的 next 指针指向空即可。
头部删除:把链表的头节点设为原头节点的的 next 指针即可。
中间删除:把要删除节点的前置节点的 next 指针,指向要删除节点的下一个节点即可。
链表实现
1 | package com.datastructure.linkedlist; |
循环链表
循环链表 即尾节点的 next 指针指向 头节点,如果是双向循环链表,则头节点的 prev 指针指向属节点。
数组VS链表
数组 的优势在于能够快速定位元素,对于读操作多,写操作少的场景来说比较合适。
链表 的优势在于能够灵活地进行插入和删除操作,如需要在链表尾部频繁执行插入、删除操作,则链表更合适。
时间 / 空间复杂度比较 | 查找 | 更新 | 插入 | 删除 |
---|---|---|---|---|
数组 | Ο(1) | Ο(1) | Ο(n) | Ο(n) |
链表 | Ο(n) | Ο(1) | Ο(1) | Ο(1) |
哈希表
哈希表也称为 散列表(Hash Table),提供键(Key) 和值(Value)映射关系。只要给出 key ,就可以高效查找到映射的 Value,时间复杂度接近于 Ο(1) 。
在极端情况下,如果所有 Key 的数组下标都冲突,那么,Hash 表就退化为一条链表,查询的时间复杂度是 O(N)。
哈希表的物理存储其实是一个数组,通过 Hash函数计算 Key 的下标(HashCode)就可以找到在内存的位置,Key-Value 数据并不会直接存储在 Hash 表的数组中,因为数组要求存储固定的数据类型,主要是每个数组元素中要存放固定长茺的数据。所以,数组中存储的是 Key,Value 数据元素的地址指针。
哈希函数
哈希表 在本质上也是一个数组,通过 哈希函数 将数组下标转换为 Key 值。
不同的语言中,哈希函数 的实现方式不一样,下面以 Java 中的 HashMap 为例进行分析。
Java 中的每一个对像都有属于自己的 hashcode
,hashcode 是个整型变量,是区分不同对象的重要档识。
整型变量转化成数组下标,最简单的转化方式是按照数组长度进行取模运算。而 JDK 中的哈希函数是利用位运算的方式来优化性能。
取模运算,例如一个长度为 8 的数组,key 为 001121,转换为数组下标 index = hashcode(“001121”) % Array.length = 1420036703 / 8 = 7。
写操作(put)
写操作就是在散列表中插入新的键值对。以 HashMap 为例。
a. 实际是通过哈希函数,把 key 转化成数组下标。
b. 如果数组该下标对应的位置没有元素,就把这个元素存入到该位置。
c. 数组长度是有限的,当插入的元素越来越多时,不同的 Key 通过哈希函数获取的下标有可能相同,这种情况就出现了 哈希冲突。
哈希冲突是无法避免的,但然要想办法解决,主要有两种方法:一种是开放 寻址法,一种是 链表法。
开放寻址法
当一个 Key 通过 哈希函数 获得对应的数组下标已被占用时,则寻找下一个空的位置。这只是开放寻址法的基本思路。
寻址方式有很多种,如 线性探测再散列,二次探测再散列、双重散列等方法,使用某种探测算法在散列表中寻找下一个空的散列地址,只要散列表足够大,总能找到空的散列地址。可参考 数据结构:哈希表以及哈希冲突的解决方案 博文。
在 Java 中,
ThreadLocal
所使用的就是开放寻址法。链表法
Java 的 HashMap 使用此方法。
HashMap 数组中的每一个元素不仅是一个
Entry
对象,还是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时,只需插入到对应的链表中即可。备注: JDK 8 和以前的版本有较大的不同。当多个 Entry 被 Hash 到同一个数组下标的位置时,为了提升插入和查找的效率,HashMap 会把 Entry 的链表转化为
红黑树
这种数据结构。
读操作(get)
通过给定的 Key ,在散列表中查找对应的 Value。
a. 通过哈希函数,将 key 转换成数组下标。
b. 若直接找到则返回,若没有找到,则顺着该 Entry 的链表往下找到与 Key 对应的元素。
扩容(resize)
数组存在扩容,散列表是基于数组的,也同样涉及扩容的问题。
当散列表中多次插入元素达到一定饱和度时, Key 映射位置发生冲突的概率会逐渐提高。当大量元素拥挤在相同的数组下标位置,会形成很长的链表,对后续的插入和查表操作的情能有很大的影响。
这时,散列表就需要扩展它的长度,即需要进行 扩容 。
JDK 中的散列表实现类 HashMap 的扩容有两个因素:
- Capacity:即 HashMap 的当前长度。
- LoadFactory:即 HashMap 负载因子,默认值为
0.75f
。
扩容 是创建一个新的 Entry 空数组,长度为原数组的 2 倍。重新 Hash,遍历原 Entry 数组,把所有 Entry 重新 Hash 到新数组中。重新 Hash 是因为扩大长度后, Hash 规则也随之改变。
经过扩容,原来拥挤的散列表重新变得稀疏,原有的 Entry 也重新得到了尽可能均匀的分配。
其它参考
数据结构与算法(一):数组、链表、哈希表
http://blog.gxitsky.com/2019/07/12/DataStructure-01-array-linkedlist-hashtable/