2.3.1 数组

2017-02-13 17:35:37.0

    数组可以说是最简单的一种数据结构,它占据一块连续的内存并按照顺序存储数据。创建数组时,需要首先指定数组的容量大小,然后根据大小分配内存。即使只在数组中存储一个数字,也需要为所有的数据预先分配内存。因此数组的空间效率不好。

    由于数组的内存是连续的,于是可以根据下标在O(1)时间读/写任何元素,因此它的时间效率很高。可以根据时间效率高的优点,用数组来实现简单的哈希表:把数组的下标设为哈希表的键值(key),而把数组中的每一个数字设为哈希表的值(value),这样每一个下标及数组中该下标对应的数字就组成了一个键-值的配对。有了这样的哈希表,就可以在O(1)实现查找,从而可以快速高效地解决很多问题。