数据结构的存储⽅式

微信扫一扫,分享到朋友圈

数据结构的存储⽅式

点击关注上方“ 知了小巷 ”,

设为“置顶或星标”,第一时间送达干货。

数据结构的存储⽅式只有两种:数组(顺序存储)和链表(链式存储)。

数据的存储方式可分为线性表、树和图三种存储结构,而每种存储结构又可细分为顺序存储结构和链式存储结构。

数据的 逻辑结构 :数据之间的逻辑关系。

数据的存储结构,也就是 物理结构 ,指的是数据在物理存储空间上选择集中存放还是分散存放。在做数据结构存储结构时,如果选择集中存储,就使用顺序存储结构;反之,就使用链式存储,主要取决于存储设备的状态以及数据的用途。

集中存储(底层实现使用的是数组)需要使用一大块连续的物理空间,假设要存储大小为 1G 的数据,若存储设备上没有整块大小超过 1G 的空间,就无法使用顺序存储,此时就要选择链式存储,因为链式存储是随机存储数据,占用的都是存储设备中比较小的存储空间,因此有一定几率可以存储成功。

简单认识链表

单链表

单链表的插入和删除

循环链表

双向链表

双向循环链表

链表VS数组的时间复杂度

经济基础决定上层建筑

Java中散列表的实现HashMap

table是Node<K,V>数组,当然也用到了链表和树-red-black tree。「散列表」就是通过散列函数y=f(x)把键映射到⼀个⼤数组⾥[y1, y2…yn]。⽽且对于解决散列冲突(哈希碰撞)的⽅法,拉链法需要链表特性,操作简单,但需要额外的空间存储指针;线性探查法就需要数组特性,以便连续寻址,不需要指针的存储空间,但操作稍微复杂些;Java在链表基础上达到一定条件后转换为红黑树。

public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
... // 成员变量
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
// 下一个节点
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
...//略
}
public final K getKey()        { return key; }
public final V getValue()      { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
...//略
}
public final boolean equals(Object o) {
...//略
}
}
...//略
// 数组
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {...}

Java中栈的实现Stack

Stack继承自Vector,其中elementData是Object数组。

public
class Stack<E> extends Vector<E> {...}
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 数组
/**
* The array buffer into which the components of the vector are
* stored. The capacity of the vector is the length of this array buffer,
* and is at least large enough to contain all the vector's elements.
*
* <p>Any array elements following the last element in the Vector are null.
*
* @serial
*/
protected Object[] elementData;
...//略
}

Java中队列的实现ArrayBlockingQueue

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
implements BlockingQueue<E>, java.io.Serializable {
// 数组
/** The queued items */
final Object[] items;
}

「栈」和「队列」这两种数据结构既可以使⽤链表也可以使⽤数组实现。⽤数组实现,就要处理扩容缩容的问题;⽤链表实现,没有这个问题,但需要更多的内存空间存储节点指针。

「图」的两种表⽰⽅法,邻接表就是链表,邻接矩阵就是⼆维数组。邻接矩阵判断连通性迅速,并可以进⾏矩阵运算解决⼀些问题,但是如果图⽐较稀疏的话很耗费空间。邻接表⽐较节省空间,但是很多操作的效率上肯定⽐不过邻接矩阵。

树用数组来实现就是堆,堆是一颗完全二叉树。⽤数组存储树的节点不需要节点指针,操作也⽐较简单;⽤链表实现就是很常⻅的「树」,由于不⼀定是完全⼆叉树,所以不适合⽤数组来存储。在这种链表「树」结构之上,⼜衍⽣出各种巧妙的设计,⽐如⼆叉搜索树、AVL树、红⿊树、区间树、B树等等,以应对和处理不同应用场景的问题。

Redis提供的数据结构

Redis is an in-memory database that persists on disk . The data model is key-value , but many different kind of values are supported: Strings, Lists, Sets, Sorted Sets, Hashes, Streams, HyperLogLogs, Bitmaps .

对于Redis中的每种数据结构,底层的存储⽅式都⾄少有两种,以便于根据存储数据的实际情况使⽤合适的存储⽅式。

比如最基础的SDS,数据空间是char数组:

/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度(初次分配空间,一般没有空余,在对字符串修改的时候,会有剩余空间出现)-预分配
int free;
// 数据空间
char buf[];
}

总结

上面如此多样化的数据结构,从实现原理来看,都是在链表或者数组之上设计的特殊操作,API不同⽽已。数据结构种类很多,甚⾄也可以发明⾃⼰的数据结构,但是底层存储⽆⾮数组或者链表,⼆者的优缺点如下:

数组:

由于是紧凑连续存储,可以随机访问,通过索引(下标)快速找到对应元素,⽽且相对节约存储空间。但正因为连续存储,内存空间必须⼀次性分配够,所以说数组如果要扩容,需要重新分配⼀块更⼤的空间,再把数据全部复制过去,时间复杂度 O(N);⽽且你如果想在数组中间进⾏插⼊和删除,每次必须搬移后⾯的所有数据以保持连续,时间复杂度 O(N)。

链表:

因为元素不连续,⽽是靠指针指向下⼀个元素的位置(内存地址偏移量),所以不存在数组的扩容问题;如果知道某⼀元素的前驱和后继,操作指针即可删除该元素或者插⼊新元素,时间复杂度 O(1)。但是正因为存储空间不连续,你⽆法根据⼀个索引算出对应元素的地址,所以不能随机访问;⽽且由于每个元素必须存储指向前后元素位置的指针,会消耗相对更多的储存空间。

– END –

猜你喜欢:

数据中台实战系列笔记

浅谈OLAP系统核心技术点(建议收藏)

HBase基础面试题总结

Hive基础面试题总结

MapReduce和YARN基础面试题总结

HDFS基础面试题总结

微信扫一扫,分享到朋友圈

数据结构的存储⽅式

Facebook在Instagram和Messenger上推出跨平台信息传递功能

上一篇

如何建设省时省力的BI平台?

下一篇

你也可能喜欢

数据结构的存储⽅式

长按储存图像,分享给朋友