【数据结构】数组与实现分析

概念

所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。数组是在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。

数组有维度有分类，如一维、二维、三维等，而这个N维的N就是数组的向量了。结合数据结构的分类概念，只有一维数组属于线性结构类型，其它维度的都只属于非线性结构类型。

实现分析

在Java语言中的String类是通过字符数组实现的，那么String到底怎么利用数组实现的，下面可以通过String的源码进行分析：

/*String的属性*/
/** 这个value就是一个字符数组，也是字符串内容的存储所在地。*/
private final char value[];

/** offset属性是这个value字符存储数组的第一个索引，数组的起始索引是从0开始。 */
private final int offset;

/**count是用来记录value字符数组存储字符的数量，也可以看做是数组的长度。*/
private final int count;

/** 字符串的hashcode,默认为0，字符有自己的一套hashcode生成方式，后续讨论。 */
private int hash; // Default to 0;

/** 序列化版本hashcode */
private static final long serialVersionUID = -6849794470754667710L;

/** 这是序列化使用的一个对象属性数组 */
private static final ObjectStreamField[] serialPersistentFields =new ObjectStreamField[0];

从上述属性可以看出，Java的字符串类实际上就是一个由一个字符数组（char[] value）组成的，其它都是这个数组的相关属性。接下来看看String其中的一个构造函数：

 1 public String(String original) {
 2     int size = original.count;
 3     char[] originalValue = original.value;
 4     char[] v;
 5       if (originalValue.length > size) {
 6             int off = original.offset;
 7             v = Arrays.copyOfRange(originalValue, off, off+size);
 8      } else {
 9         v = originalValue;
10      }
11     this.offset = 0;
12     this.count = size;
13     this.value = v;
14 }

从重构造方法可以看出，如果原字符串的字符数组的长度大于它的大小属性，则新字符串的字符数组则通过Arrays.copyOfRange方法复制一个全新的数组，否则新字符数组引用原字符串数组地址，也就是共同指向同一个数组，但字符串本身的对象是不相等的。接下来再看看另外一个构造方法：

 1 public String(char value[], int offset, int count) {
 2 if (offset < 0) {
 3         throw new StringIndexOutOfBoundsException(offset);
 4     }
 5     if (count < 0) {
 6         throw new StringIndexOutOfBoundsException(count);
 7     }
 8     if (offset > value.length - count) {
 9         throw new StringIndexOutOfBoundsException(offset + count);
10     }
11     this.offset = 0;
12     this.count = count;
13     this.value = Arrays.copyOfRange(value, offset, offset+count);
14 }

此构造方法可以通过指定原字符数组的截取起始索引（offset）和截取长度（count）创建一个新的字符数组并赋值给新字符串的字符数组。接下来我们可以通过String的charAt函数来获取字符串的字符数组中的任意字符：

1 public char charAt(int index) {
2     if ((index < 0) || (index >= count)) {
3         throw new StringIndexOutOfBoundsException(index);
4     }
5     return value[index + offset];
6 }

其中index就是指定字符串的字符数组的下标。

除了Java语言，C语言的字符串同样使用字符数组，当然C是基础语言。下面来看看Redis（C语言实现）的字符串源码定义：

1 struct sdshdr {
2     unsigned int len;
3     unsigned int free;
4     char buf[];
5 };

其中len属性跟Java的String类的count属性是一样的，代表字符数组的长度，而buf就是一个存储字符串所有字符的数组，而free比较特别，这是Redis根据自己使用字符串的特性而定义的，标记char[]中未使用的元素个数，就是有几个空的没有使用的数组格的意思。关于数组的学习就暂时到这了，准备下一篇“栈”的使用学习了。