Android 常用的数据结构及优缺点

Android 常用的数据结构有八种：数组（Array），栈（Stack），链表（Linked List），图（Graph），队列（Queue），树（Tree），堆（Heap），散列表（Hash）；

SparseArray 与普通的数组不一样，它允许元素之间可以空缺（普通数组的元素必需是连续的），所以 SparseArray 类似于 Map。但是它的内存使用率比 HashMap 更高效：

SparseArray通过『二分法』来查找 key，当 SparseArray 数据太大时（元素太多了），它的执行效率还不如 HashMap，因为它通过『二分法』来添加或删除元素时，存在数组元素的重新移动（只有在空间不足时才会这样，下段话会解释）。

SparseArray为提高性能在删除数据时进行了优化，不会立即压缩数组而是为需要删除的条目打上标记，在往后需要数组扩容或者数据检索时进行数据清除和数组压缩，这样可以减少数组 *** 作的频率，同时可以复用key值。

大家注意，没有找到时，是对 lo 的取反。

一般情况，如果没有找到，我们都会返回 -1，表示没有找到，而这里的取反（正数取反就是负数），同样表示没有找到，但是，如果我们再取反（反反得正），就可以在该位置添加元素，是不是很巧妙？

SparseArray对比HashMap：

总体的来讲，数据存储方式有三种：一个是文件，一个是数据库，另一个则是网络。其中文件和数据库可能用的稍多一些，文件用起来较为方便，程序可以自己定义格式；数据库用起稍烦锁一些，但它有它的优点，比如在海量数据时性能优越，有查询功能，可以加密，可以加锁，可以跨应用，跨平台等等；网络，则用于比较重要的事情，比如科研，勘探，航空等实时采集到的数据需要马上通过网络传输到数据处理中心进行存储并进行处理。 对于Android平台来讲，它的存储方式也不外乎这几种，按方式总体来分，也是文件，数据库和网络。但从开发者的角度来讲它可以分为以下五种方式： 1.SharedPreferences共享偏好 2.Internal Storage内部存储空间 3.External Storage外部存储空间 4.SQLite Database数据库 5.Internet网络 这几种方式各自有各自的优点和缺点，要根据不同的实际情况来选择，而无法给出统一的标准。下面就各种方式谈谈它们的优缺点，以及最合适的使用情况： 1.Shared Preferences共享偏好 SharedPreferences是用来存储一些Key/Value类似的成对的基本数据类型，注意，它只能存储基本数据类型，也即int, long, boolean, String, float。事实上它完全相当于一个HashMap，唯一不同的就是HashMap中的Value可以是任何对象，而SharedPreferences中的值只能存储基本数据类型(primitive types)。 对于它的使用方法，可以参考Android Developer Guide，这里不重复。 如此来看，最适合SharedPreferences的地方就是保存配置信息，因为很多配置信息都是Key/Value。事实上，在Android当中SharedPreferences使用最多的地方也是用来保存配置（Settings）信息，系统中的Settings中这样，各个应用中的Settings也是这样。并且，Android中为了方便的使用SharedPreferences保存配置信息，它来专门有PreferenceActivity用来封装。也就是说如果你想在应用程序中创建配置（Settings），你可以直接使用PreferenceActivity和一些相关的专门为Preference封装的组件，而不用再直接去创建，读取和保存SharedPreference，Framework中的这些组件会为你做这些事。 再谈谈一些使用SharedPreference时的技巧，它只能保存基本数据类型，但假如我想保存一个数组，怎么办？可以把数据进行处理，把它转化成一个String，取出的时候再还原就好了；再如，如想保存一个对象，怎么办，同样，可以把对象序列化成为字符序列，或转成String（Object.toString()），或是把它的HashCode（Object.hashCode()）当成Value保存进去。 总之，SharedPreferences使用起来十分的方便，可以灵活应用，因为它简单方便，所以能用它就尽量不要用文件或是数据库。 1.Internal Storage内部存储空间 所谓的内部存储与外部存储，是指是否是手机内置。手机内置的存储空间，称为内部存储，它是手机一旦出厂就无法改变，它也是手机的硬件指标之一，通常来讲手机内置存储空间越大意味着手机价格会越贵(很多地方把它称为手机内存，但我们做软件的知道，这并不准确，内存是指手机运行时存储程序，数据和指令的地方；这里应该是手机内部存储的简称为内存，而并非严格意义上的内存)。 内部存储空间十分有限，因而显得可贵，所以我们要尽可能避免使用；另外，它也是系统本身和系统应用程序主要的数据存储所在地，一旦内部存储空间耗尽，手机也就无法使用了。所以对于内部存储空间，我们要尽量避免使用。上面所谈到的Shared Preferences和下面要谈到的SQLite数据库也都是存储在内部存储空间上的。 Android本身来讲是一个Linux *** 作系统，所以它的内部存储空间，对于应用程序和用户来讲就是“/data/data"目录。它与其他的（外部的存储）相比有着比较稳定，存储方便， *** 作简单，更加安全（因为可以控制访问权限）等优点。而它唯一的缺点就是它比较有限，比较可贵。 虽然，可以非常容易的知道程序本身的数据所在路径，所有的应用程序的数据路径都是“/data/data/app-package-name/”，所有的程序用到的数据，比如libs库，SharedPreferences都是存放在这个路径下面。但我们在使用的时候最好不要，或是千万不要直接引用这个路径。 使用内部存储主要有二个方式，一个是文件 *** 作，一个是文件夹 *** 作。无论哪种方式，Context中都提供了相应的函数来支持，使用Context不但 *** 作简单方便，最重要的是Context会帮助我们管理这些文件，也可以方便帮助我们控制文件的访问权限。先来系统的说下Context中关于文件和文件夹 *** 作的函数有哪些。 a. 创建一个文件，并打开成一个文件输出流，需要提供一个String，作为文件名 1.FileOutputStream output = Context.openOutputFile(filename， Context.MODE_PRIVATE)2.output.write(data）；// use output to write whatever you like 3.output.close()1.FileOutputStream output = Context.openOutputFile(filename， Context.MODE_PRIVATE)output.write(data）；// use output to write whatever you like output.close()b. 同样，想打开一个文件作为输入的话，也是只需要提供文件名 1.FileInputStream input = Context.openInputFile(filename)2.input.read()3.input.close()1.FileInputStream input = Context.openInputFile(filename)input.read()input.close()c. 列出所有的已创建的文件 1.String[] files = Context.fileList()2.for (String file : files) ｛ 3. Log.e(TAG, "file is " + file)4.} 1.String[] files = Context.fileList()for (String file : files) ｛ Log.e(TAG, "file is " + file)} d. 删除文件，能创建就要能够删除，当然也会提供了删除文件的接口，它也非常简单，只需要提供文件名 1.if (Context.deleteFile(filename)) { 2. Log.e(TAG, "delete file " + filename + " sucessfully“)3.} else { 4. Log.e(TAG, "failed to delete file " + filename)5.} 1.if (Context.deleteFile(filename)) { Log.e(TAG, "delete file " + filename + " sucessfully“)} else { Log.e(TAG, "failed to delete file " + filename)} e. 获取文件已创建文件的路径，它返回一个文件对象用于 *** 作路径 1.File fileDir = Context.getFileDir()2.Log.e(TAG, "fileDir " + fileDir.getAbsolutePath()1.File fileDir = Context.getFileDir()Log.e(TAG, "fileDir " + fileDir.getAbsolutePath()f. 创建一个目录，需要传入目录名称，它返回 一个文件对象用到 *** 作路径 1.File workDir = Context.getDir(dirName, Context.MODE_PRIVATE)2.Log.e(TAG, "workdir " + workDir.getAbsolutePath()1.File workDir = Context.getDir(dirName, Context.MODE_PRIVATE)Log.e(TAG, "workdir " + workDir.getAbsolutePath()g. 以File对象方式查看所创建文件，需要传入文件名，会返回文件对象 1.File store = Context.openFileStreamPath(filename)2.Log.e(TAG, "store " + store.length())1.File store = Context.openFileStreamPath(filename)Log.e(TAG, "store " + store.length())h. 获取Cache路径，无需要传入参数，返回文件对象 1.File cachedir = Context.getCacheDir()2.Log.e(TAG, "cachedir " + cacheDir.getAbsolutePath())1.File cachedir = Context.getCacheDir()Log.e(TAG, "cachedir " + cacheDir.getAbsolutePath())总结一下文件相关 *** 作，可以得出以下三个特点： 1. 文件 *** 作只需要向函数提供文件名，所以程序自己只需要维护文件名即可； 2. 不用自己去创建文件对象和输入、输出流，提供文件名就可以返回File对象或输入输出流 3. 对于路径 *** 作返回的都是文件对象。 如前所述，内部存储空间有限，可贵，安全，稳定，所以应该用来保存比较重要的数据，比如用户信息资料，口令秘码等不需要与其他应用程序共享的数据。也可以用来创建临时文件，但一定要注意及时删除。另外，对于内部存储还有一个非常重要的特点，那就是在应用程序被卸载时，应用程序在内部存储空间的文件数据将全部被删除。系统这样做的原因很简单，就是因为内部存储很有限，它必须保证它的可用性，因为一旦添满，系统将无法再正常工作。 1.External Storage外部存储空间 再来谈谈手机外部存储空间，与内部存储空间相对，外部存储空间是指手机出厂的时候不存在，用户在使用时候可以自由添加的外部存储介质比如TS卡，SD卡等闪存储介质。这些闪存介质由最初的空间小价格贵，到现在的大容量价格便宜，所以几乎每个支持外部存储的手机上面都有大容量（大于等于2G）的闪存卡。 Android也是不例外，它完全支持外部存储介质。其实更确切的说，它是要依赖于外部存储卡的，因为对于Android系统，如果没有外部存储卡，很多的系统应用无法使用，比如多媒体相关的应用程序无法使用。虽然Android很依赖，但是外部存储卡也有它自身的特点，它最大的优点就是存储空间大，基本上你可无限制的使用，也不怎么担心去清除数据。就目前来看，很多程序都在使用外部存储卡，但很少有程序去主动清理数据，所以无论你的SD卡有多大，它的可用空间却越来越少。与内部存储不同的是，当程序卸载时，它在外部存储所创建的文件数据是不会被清除的。所以清理外部存储空间的责任丢给了用户自己，每隔一段时间就去查看下SD卡，发现无用数据立马删除。外部存储的缺点就是不是很稳定，对于Android手机来讲可以说，很不稳定，本身闪存介质就容易出问题，SD卡处于不能正常使用的状态十分多。 先来说说外部存储相关的使用方法和API： a. Check media availability检查介质的可用性 如前所述，外部存储介质的稳定性十分的差，所以在使用之前一定要先检查它的可用性，如果可用再去用 view plaincopy to clipboardprint? 1.final String state = Environment.getExternalStorageState()2.if (state.equals(Environment.MEDIA_MOUNTED) || state.equals(Environment.MEDIA_READ_ONLY)) {// sd card is ready to us } view plaincopy to clipboardprint? 1.final String state = Environment.getExternalStorageState()if (state.equals(Environment.MEDIA_MOUNTED) || state.equals(Environment.MEDIA_READ_ONLY)) {// sd card is ready to us } final String state = Environment.getExternalStorageState()if (state.equals(Environment.MEDIA_MOUNTED) || state.equals(Environment.MEDIA_READ_ONLY)) {// sd card is ready to us } b. Get the directory获取外部存储卡的路径 事实上，外部存储卡的路径是“/mnt/sdcard"，所以你直接这样写去访问也能访问的到。鉴于可读性和可移植性的考虑，建议这样写： view plaincopy to clipboardprint? 1.File sdcardDir = Environment.getExternalStorageDirectory()view plaincopy to clipboardprint? 1.File sdcardDir = Environment.getExternalStorageDirectory()File sdcardDir = Environment.getExternalStorageDirectory()c. For API 8 or greater, there are some other useful APIs helping to manager files and directories. 如果你使用API 8(Android 2.2)或者更高，那么SDK中又多了几个 *** 作外部存储文件和路径的接口，文档中也建议开始者更加规范的使用SD卡。比如，创建相应的目录去存储相应的数据，Music，Picture，Video等。应用程序目录也变成了"/Android/data/package-name/data"。具体的使用可以参考文档，这里不重复。当然，就像编程规范一样，这里只是规范，你完全可以不遵守它，但出于可读性和可移植性，还是建议按照文档建议的去做。 下面总结一下使用时应该注意的一些和外部存储的特点： a. 外部存储卡不是随时想用就能够用的，所以一定要记得在使用之前检查它的可用性 b. 存储在外部存储卡上的数据是所有应用程序都可见，用户也可见（使用FileManager），所以安全性不是很好，虽然文档声称可以在外部存储卡上写程序私有数据，但貌似没用，用FileManager仍然可以删除或编辑文件（Market上面的FileManager功能都十分的强大，能让用户看到SD卡中的所有文件，和 *** 作能看到的文件）。 c. Android手机支持把外部存储卡Mount至PC做为U盘，当连接数据线时，这时SD卡变成了U盘连接到了另外的 *** 作系统中。什么意思，就是在Android当中虽然有的文件属性（隐藏，私有等），到了PC上就不一定管用了，用户在PC上可以随意 *** 作文件（这就是第二点中所提及的）。 d. 如果使用外部存储卡保存数据，一定要额外做好异常处理：外部存储卡不可用时把数据存入哪里；可用的时候再怎么同步数据（这是比较头疼的地方，可行的做法就是当SD卡不可用时不准用户写数据，但这用户体验又不是很好，但如你所知，很多应用都这么干）；你的数据被破坏了。当然常见的异常也要考虑，比如空间满了，无法写入，磁盘坏道等。 1.SQLite Database数据库 Android对数据库的支持很好，它本身集成了SQLite数据库，每个应用都可以方便的使用它，或者更确切的说，Android完全依赖于SQLite数据库，它所有的系统数据和用到的结构化数据都存储在数据库中。 它具有以下优点： a. 效率出众，这是无可否认的 b. 十分适合存储结构化数据 c. 方便在不同的Activity，甚至不同的应用之间传递数据 先前有一篇文章讲到了不同Activity和不同应用之间传递数据的麻烦，特别是对于大型数据结构，因为Activity虽是Java对象，但去无法像使用其他类对象那样去创建一个实例然后使用它，更无法给Activity加上Setters和Getters（虽然这样做了没有编译错误）。比较好的解决方案就是把结构化数据写入数据库，然后在不同的Activity之间传递它们的Uri。 d. 由专门的ContentProvider来帮忙管理和维护数据库 e. 可以方便的设置访问权限，私有还是都可见 f. *** 作方便，使用标准的CRUDE语句，ContentResolver.query(), update(), delete() insert()，详见ContentResolver g. 良好的可移植性和通用性，用标准的SQL语句就能实现CRUDE 对于它的使用方法可以去参考文档，这里也说不清楚。 1.Internet网络 网络是比较不靠谱的一个，因为移动终端的网络稳定性，以及所产生的流量让人伤不起，用户更伤不起。但若是对于非常重要的实时数据，或是需要发送给远端服务器处理的，也可以考虑使用网络实时发送。这已经有先例了，Apple和Google就是这样，iPhone设备和Android设备都会在用户不知情的情况 下收集用户的信息，然后又在用户不知情的情况 下发送到Apple和Google的服务器上，也就是所谓的“跟踪门”。除此之外，智能手机（特别是Android和火热的iPhone）上面的应用程序都会偷偷的在后台运行，收集用户数据，然后再偷偷的发服务器，直接伤害是用户流量，请看先前的文章。 对比这几种方式，可以总结下： 1. 简单数据和配置信息，SharedPreference是首选； 2. 如果SharedPreferences不够用，那么就创建一个数据库 3. 结构化数据，一定要创建数据库，虽然这稍显烦锁，但是好处无穷 4. 文件就是用来存储文件(也即非配置信息或结构化数据)，如文本文件，二进制文件，PC文件，多媒体文件，下载的文件等等。 5. 尽量不要创建文件 6. 如果创建文件，如果是私密文件或是重要文件，就存储在内部存储，否则放到外部存储 7. 不要收集用户数据，更不要发到网络上，虽然你们也有很多无奈。用户也无奈，也无辜，但更无助 平台为开发者准备了这么多的方式固然是一件好事，但我们要认清每一种的优点和缺点，根据实际情况选择最合适的。还有一个原则就是最简单原则，也就是说能用简单的方式处理，就不要用复杂的方式。

---