HashMap,SparseArray比较

数据基于JDK1.8
主要分析分析SparseArray，HashMap 查找效率，内存空间占用

原理分析

HashMap数据结构 数组+链表

2695420-df501397c13049c4.jpg

从数据结构图上看，存取时，先通过hash 模获取index,到对应的index下创建链表存取，这样结构的问题：

1. hash冲突 问题
   存放在链表中
2. hash数组扩容问题
   那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能
3. 查找效率问题
   通过hash 模查找对应数组位置，再到链表中用equals查找链表
4. 删除节点问题
5. 空间浪费
   hash模比较分散时，产生空间浪费比较多

SparseArray 数据结构图 两个数组

14031304-de57e48aa4ac49de.png

key 是有序的，采用二分查找寻找
插入时，采用System.arraycopy依次后移
删除效率：在删除时只对其进行标记为delete为true，并未真正删除，等到再次有排序的插入，刚好占用此位置，其它的也不用后移

执行结果

一万条数据展示结果
添加数据展示结果:
SparseArray 内存前后比较：

SparseArray内存.png

HashMap前后内存比较：

HashMap内存.png

查询时间比较:

查询时长比较

十万条数据展示结果

查询时间比较：

查询时间比较

测试代码:

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>