写游戏说白了就是和数据打交道，而数据结构和算法在不同语言，不同平台上原理是想通的。这篇文章只是简单回顾一下。
在Flash平台最常用的莫过于数组(Array)类型了。数组结构在实现上是一段连续的内存，所以按索引访问速度飞快。由于Flash内置的线性结构唯有Array一种，所以很多人就只用数组处理所有问题了。问题在于，虽然数组的随机访问速度快，但是其插入、移动的成本很高。但是这也不一定说传统的C/C++数据结构就可以直接照搬到Actionscript上来，因为Actionscript是一种脚本语言，其解释和执行均由AVM执行。由Actionscript定义的结构再经过AVM解释，效率往往反而不如使用Array（Flash内置并经过优化）。
使用非Array结构的一种场合可以是大量数据时。比如等角游戏，100×100格，4层地图共有100×100×4=40 000个数据，对这4万个数据如果采用Array存储并经常需要增删，那么Array的效率就不如自定义数据结构，比如链表。链表虽然是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比数组快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。使用链表结构可以充分利用内存空间，实现灵活的内存动态管理。链表的实现和与Array的对比可以参考http://lab.polygonal.de/
幸运的是，Haxe和Alchemy的出现弥补了这一不足。Alchemy可以编译C/C++程序为Flash字节码，而Haxe编译器可以很好的编译时优化代码，并且内置了List，FastList等结构。他们也各有缺点，比如缺乏调试环境，没有好的IDE支持，Alchemy编译出的文件过大等。
面试Flash程序员时我经常会问一些基础的数据结构的知识，比如什么是哈希结构。作为一种抽象数据结构，Hash表的实现思路如下：通过某种算法，在 键--值对的存储地址和 键--值对中的key之间，建立一种映射，使得每一个key，都有一个确定的存储地址于之对应。这种算法被封装在Hash函数中。在查找时，通过Hash函数，算出和key对应的存储地址，从而找到相应的键-值对。相对于通过遍历整个键-值对列表来进行查找，Hash表的查找效率要高得多，理想的情况下算法复杂度仅为o(1)(遍历查找的复杂度为o(n))。Flash内置的哈希结构有Object和Dictionary两种。访问速度上Dictionary要快于Object（参考 Dictionary VS Object VS Array ），并且支持弱引用。Haxe的选择面则更广一些。Dictionary提供了一种泛型结构，并针对key为int型的哈希结构做了特殊优化——IntHash。
数组、链表、哈希即最常用的数据结构，实际项目需要根据需要合理运用他们，并优先选择比较简单的数据结构。其他一些数据结构则在特定环境下能发挥更大的效用，比如二叉堆在寻路中的优化、四叉树在大地图管理中的使用等。
说了这些都是针对特定问题提出解决方案。那么有没有一种通用的方案呢？
答案是没有。即使有（比如，写一个小型数据库？），也不适合在游戏中使用。最近有人问我为什么不写一个数据库给引擎用呢？这样不用写各种类型的数据结构了，直接建表即可?......我很疑惑竟还真有某Flash游戏这么做了。数据库是“按照数据结构来组织、存储和管理数据的仓库”，一般是持久化存储。其定义已经明确了其功能，所以玩家的基本数据会被存储到数据库（Server），而游戏引擎中的数据则主要是为了更快的游戏速度和更小的空间占用，针对性的完成特定任务——爱偷懒的例外。
在Flash平台最常用的莫过于数组(Array)类型了。数组结构在实现上是一段连续的内存，所以按索引访问速度飞快。由于Flash内置的线性结构唯有Array一种，所以很多人就只用数组处理所有问题了。问题在于，虽然数组的随机访问速度快，但是其插入、移动的成本很高。但是这也不一定说传统的C/C++数据结构就可以直接照搬到Actionscript上来，因为Actionscript是一种脚本语言，其解释和执行均由AVM执行。由Actionscript定义的结构再经过AVM解释，效率往往反而不如使用Array（Flash内置并经过优化）。
使用非Array结构的一种场合可以是大量数据时。比如等角游戏，100×100格，4层地图共有100×100×4=40 000个数据，对这4万个数据如果采用Array存储并经常需要增删，那么Array的效率就不如自定义数据结构，比如链表。链表虽然是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比数组快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。使用链表结构可以充分利用内存空间，实现灵活的内存动态管理。链表的实现和与Array的对比可以参考http://lab.polygonal.de/
幸运的是，Haxe和Alchemy的出现弥补了这一不足。Alchemy可以编译C/C++程序为Flash字节码，而Haxe编译器可以很好的编译时优化代码，并且内置了List，FastList等结构。他们也各有缺点，比如缺乏调试环境，没有好的IDE支持，Alchemy编译出的文件过大等。
面试Flash程序员时我经常会问一些基础的数据结构的知识，比如什么是哈希结构。作为一种抽象数据结构，Hash表的实现思路如下：通过某种算法，在 键--值对的存储地址和 键--值对中的key之间，建立一种映射，使得每一个key，都有一个确定的存储地址于之对应。这种算法被封装在Hash函数中。在查找时，通过Hash函数，算出和key对应的存储地址，从而找到相应的键-值对。相对于通过遍历整个键-值对列表来进行查找，Hash表的查找效率要高得多，理想的情况下算法复杂度仅为o(1)(遍历查找的复杂度为o(n))。Flash内置的哈希结构有Object和Dictionary两种。访问速度上Dictionary要快于Object（参考 Dictionary VS Object VS Array ），并且支持弱引用。Haxe的选择面则更广一些。Dictionary
数组、链表、哈希即最常用的数据结构，实际项目需要根据需要合理运用他们，并优先选择比较简单的数据结构。其他一些数据结构则在特定环境下能发挥更大的效用，比如二叉堆在寻路中的优化、四叉树在大地图管理中的使用等。
说了这些都是针对特定问题提出解决方案。那么有没有一种通用的方案呢？
答案是没有。即使有（比如，写一个小型数据库？），也不适合在游戏中使用。最近有人问我为什么不写一个数据库给引擎用呢？这样不用写各种类型的数据结构了，直接建表即可?......我很疑惑竟还真有某Flash游戏这么做了。数据库是“按照数据结构来组织、存储和管理数据的仓库”，一般是持久化存储。其定义已经明确了其功能，所以玩家的基本数据会被存储到数据库（Server），而游戏引擎中的数据则主要是为了更快的游戏速度和更小的空间占用，针对性的完成特定任务——爱偷懒的例外。
好怀念数据结构啊~