數(shù)據(jù)基于JDK1.8
主要分析分析SparseArray，HashMap 查找效率，內(nèi)存空間占用

原理分析

HashMap數(shù)據(jù)結(jié)構(gòu) 數(shù)組+鏈表

2695420-df501397c13049c4.jpg

從數(shù)據(jù)結(jié)構(gòu)圖上看，存取時，先通過hash 模獲取index,到對應的index下創(chuàng)建鏈表存取，這樣結(jié)構(gòu)的問題：

1. hash沖突 問題
   存放在鏈表中
2. hash數(shù)組擴容問題
   那么hashmap什么時候進行擴容呢？當hashmap中的元素個數(shù)超過數(shù)組大小loadFactor時，就會進行數(shù)組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數(shù)組大小為16，那么當hashmap中元素個數(shù)超過160.75=12的時候，就把數(shù)組的大小擴展為2*16=32，即擴大一倍，然后重新計算每個元素在數(shù)組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經(jīng)預知hashmap中元素的個數(shù)，那么預設元素的個數(shù)能夠有效的提高hashmap的性能
3. 查找效率問題
   通過hash 模查找對應數(shù)組位置，再到鏈表中用equals查找鏈表
4. 刪除節(jié)點問題
5. 空間浪費
   hash模比較分散時，產(chǎn)生空間浪費比較多

SparseArray 數(shù)據(jù)結(jié)構(gòu)圖 兩個數(shù)組

14031304-de57e48aa4ac49de.png

key 是有序的，采用二分查找尋找
插入時，采用System.arraycopy依次后移
刪除效率：在刪除時只對其進行標記為delete為true，并未真正刪除，等到再次有排序的插入，剛好占用此位置，其它的也不用后移

執(zhí)行結(jié)果

一萬條數(shù)據(jù)展示結(jié)果
添加數(shù)據(jù)展示結(jié)果:
SparseArray 內(nèi)存前后比較：

SparseArray內(nèi)存.png

HashMap前后內(nèi)存比較：

HashMap內(nèi)存.png

查詢時間比較:

查詢時長比較

十萬條數(shù)據(jù)展示結(jié)果

查詢時間比較：

查詢時間比較

測試代碼:

package com.example.myapplication;

import android.app.Activity;
import android.os.AsyncTask;
import android.os.Bundle;
import android.util.Log;
import android.util.SparseArray;
import android.view.View;


import java.util.HashMap;

public class TestActivity extends Activity {
    private static final String TAG = TestActivity.class.getSimpleName();
    private static final int MAX = 100000;
    private SparseArray mSparseArray;
    private HashMap mHashMap;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_test);
    }

    public void testSparseArray(View view) {
        new AsyncTask<Void, Void, Void>() {
            @Override
            protected Void doInBackground(Void... voids) {
                sparseArrayPut();
                return null;
            }
        }.execute();
    }


    public void testHashMap(View view) {
        new AsyncTask<Void, Void, Void>() {
            @Override
            protected Void doInBackground(Void... voids) {
                hashMap();
                return null;
            }
        }.execute();
    }

    public void testTime(View view) {
        new AsyncTask<Void, Void, Void>() {

            @Override
            protected Void doInBackground(Void... voids) {
                testTime();
                return null;
            }
        }.execute();
    }


    private void testTime() {
        long currentTime = System.currentTimeMillis();
        if (mSparseArray != null) {
            for (int i = 0; i < MAX; i++) {
                mSparseArray.get(i);
            }
        }
        Log.i(TAG, "SparseArray get time is:" + (System.currentTimeMillis() - currentTime));
        currentTime = System.currentTimeMillis();
        if (mHashMap != null) {
            for (int i = 0; i < MAX; i++) {
                mHashMap.get(i);
            }
        }
        Log.i(TAG, "HashMap get time is:" + (System.currentTimeMillis() - currentTime));
    }

    private void sparseArrayPut() {
        if (mSparseArray != null) {
            mSparseArray.clear();
        } else {
            mSparseArray = new SparseArray();
        }
        for (int i = 0; i < MAX; i++) {
            mSparseArray.put(i, "spA" + i);
        }
        Log.i(TAG,"array push");
    }

    private void hashMap() {
        if (mHashMap != null) {
            mHashMap.clear();
        } else {
            mHashMap = new HashMap();
        }
        for (int i = 0; i < MAX; i++) {
            mHashMap.put(i, "hpM" + i);
        }
        Log.i(TAG,"map push");
    }
}

xml文件

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:orientation="vertical"
    tools:context=".TestActivity">

    <TextView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="Hello World!" />

    <Button
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:text="@string/test_sparse_array"
        android:onClick="testSparseArray"/>

    <Button
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:text="@string/test_hash_map"
        android:onClick="testHashMap"/>

    <Button
        android:text="@string/test_time"
        android:layout_width="match_parent"
        android:layout_height="wrap_content"
        android:onClick="testTime"/>

</LinearLayout>