HashMap,SparseArray比較

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

原理分析

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

2695420-df501397c13049c4.jpg

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

hash沖突問題
存放在鏈表中
hash數(shù)組擴(kuò)容問題
那么hashmap什么時(shí)候進(jìn)行擴(kuò)容呢脸甘？當(dāng)hashmap中的元素個(gè)數(shù)超過數(shù)組大小loadFactor時(shí)恳啥，就會進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值為0.75斤程，也就是說角寸，默認(rèn)情況下菩混，數(shù)組大小為16，那么當(dāng)hashmap中元素個(gè)數(shù)超過160.75=12的時(shí)候扁藕，就把數(shù)組的大小擴(kuò)展為2*16=32沮峡，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置亿柑，而這是一個(gè)非常消耗性能的操作邢疙，所以如果我們已經(jīng)預(yù)知hashmap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高h(yuǎn)ashmap的性能
查找效率問題
通過hash 模查找對應(yīng)數(shù)組位置望薄，再到鏈表中用equals查找鏈表
刪除節(jié)點(diǎn)問題
空間浪費(fèi)
hash模比較分散時(shí)疟游，產(chǎn)生空間浪費(fèi)比較多

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

14031304-de57e48aa4ac49de.png

key 是有序的，采用二分查找尋找
插入時(shí)痕支，采用System.arraycopy依次后移
刪除效率：在刪除時(shí)只對其進(jìn)行標(biāo)記為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í)間比較:

查詢時(shí)長比較

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

查詢時(shí)間比較：

查詢時(shí)間比較

測試代碼:

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>

HashMap,SparseArray比較

原理分析

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

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

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

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