# 数据结构的存储⽅式

### 经济基础决定上层建筑

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;
}
```

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

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

### 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 .

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

– END –