月度归档:2015年08月

ArrayMap VS HashMap

在Java里面用Collection里面的HashMap作为容器我们使用的频率很高,而ArrayMap是Android api提供的一种用来提升特定场和内存使用率的特殊数据结构。今天我就写一篇博客记录一下。

HashMap

QQ截图20150823235946

Java库里的HashMap其实是一个连续的链表数组,通过让key计算hash值后插入对应的index里。当hash值发生碰撞时,可以采用线性探测,二次hash,或者后面直接变成链表的结构来避免碰撞。因为hash的值不是连续的,所以hashmap实际需要占用的大小会比它实际能装的item的容量要大。我们可以看一下HashMap的源码:

  
 public HashMap(int initialCapacity, float loadFactor)   
 {   
     // 初始容量不能为负数  
     if (initialCapacity < 0)   
         throw new IllegalArgumentException(   
        "Illegal initial capacity: " +   
             initialCapacity);   
     // 如果初始容量大于最大容量,让出示容量  
     if (initialCapacity > MAXIMUM_CAPACITY)   
         initialCapacity = MAXIMUM_CAPACITY;   
     // 负载因子必须大于 0 的数值  
     if (loadFactor <= 0 || Float.isNaN(loadFactor))   
         throw new IllegalArgumentException(   
         loadFactor);   
    //....
    // 设置容量极限等于容量 * 负载因子  
     threshold = (int)(capacity * loadFactor);   
     // 初始化 HashMap用于存储的数组  
     table = new Entry[capacity];            // ①  
     init();   
 }   

你会发现它又一个变量叫loadfactor,还有threshold。threshold就是临界值的意思,代表当前HashMap的储存机构能容纳的最大容量,它等于loadfactor * 容量。当HashMap记录存入的item size大于threshold后,HashMap就会进行扩容(resize)。当我们第一次新建一个HashMap对象的时候,默认的容量是16,若你只打算在HashMap里放入3个元素那将浪费至少13个空间。

ArrayMap

ArrayMap是怎么实现节省内存的呢?先放数据结构图:

QQ截图20150824001700

 

他用两个数组来模拟Map,第一个数组存放存放item的hash值,第二数组是把key,value连续的存放在数组里,通过先算hash在第一个数组里找到它的hash index,根据这个index在去第二个数组里找到这个key-value。

在这里,在第一个数组里查找hash index的方法当然是用二分查找啦(binary search)。QQ截图20150824002101

这个数据结构的设计就做到了,有多个item我就分配多少内存,做到了memory的节约。并且因为数据结构是通过数组组织的,所以遍历的时候可以用index直接遍历也是很方便的有没有!但是缺点也很明显,查找达不到HashMap O(1)的查找时间。

当要存储的对象较少的时候(1000以下的时候)可以考虑用ArrayMap来减少内存的占用。

曲线的魔力—贝塞尔曲线(二)

先放效果图!(类似腾讯qq的消息消失动画)上一篇回顾

 

gooey怕了吧,有没有好奇这个动画到底是怎么做的?其实原理超级简单,不要被唬住了。这里就是展现贝塞尔曲线牛逼的时候到了。其实上一篇将贝塞尔曲线只是说了它的原理,但是没有一个形象的比喻,下面我要用一个形象的比喻来解释贝塞尔曲线。控制贝塞尔曲线的过程其实就像是操纵橡皮筋,我们首先把橡皮筋的两头用钉子固定住(这就是确定了start point和end point),然后我们可以用手去拨动橡皮筋中间的部分,这就是贝塞尔曲线另外一个概念控制点(control point),我们可以通过设置不同的控制点产生不同的曲线。cubic

explain

看图其实这个动画就是两个圆形,中间两条曲线由贝塞尔曲线画出来!是不是很简单!但是难点在于,如何控制两条曲线的变化,也就是如何确定贝塞尔曲线的控制点呢?我在这里的实现比较简单,先看下图:

explain

 

控制点如图就是p5和p6,他们分别是线p1p4和p2p3线的中点。每次动态更具圆的位置动态计算控制点的位置就ok啦!

代码我就不讲解啦,很简单:

package com.example.qianlv.gooeyeffect;

import android.content.Context;
import android.graphics.Canvas;
import android.graphics.Paint;
import android.graphics.Path;
import android.graphics.PointF;
import android.graphics.RectF;
import android.view.MotionEvent;
import android.view.View;
import android.view.animation.Animation;
import android.view.animation.LinearInterpolator;
import android.view.animation.Transformation;

/**
 * Created by qianlv on 2015/8/16.
 */
public class GooeyView extends View {
    float radius1;
    float radius2;
    RectF rect1;
    RectF rect2;
    Paint paint;
    TimeAnimation animation;
    private float mInterpolatedTime;
    PointF p1;
    PointF p2;
    PointF p3;
    PointF p4;
    PointF p5;
    PointF p6;
    float dx1;
    float dy1;
    float dx2;
    float dy2;

    public GooeyView(Context context) {
        super(context);

        paint = new Paint(Paint.ANTI_ALIAS_FLAG);
        paint.setColor(0xff30accf);
        paint.setStyle(Paint.Style.STROKE);
    }

    @Override
    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
        super.onMeasure(widthMeasureSpec, heightMeasureSpec);
        int width = MeasureSpec.getSize(widthMeasureSpec);
        // 设置两个圆大小
        radius1 = width * 0.13f;
        radius2 = width * 0.1f;

        rect1 = new RectF();
        rect1.left = width*0.05f;
        rect1.top = rect1.left;
        rect1.right = radius1 * 2;
        rect1.bottom = rect1.top + radius1 * 2;

        rect2 = new RectF();
        rect2.left = rect1.right + 200;
        rect2.right = rect2.left + radius2 * 2;
        rect2.top = rect1.centerY() - radius2;
        rect2.bottom = rect2.top + radius2 * 2;
        dx1 = radius1*0.5f;
        dy1 = dx1*1.732f;
        dx2 = radius2*0.5f;
        dy2 = dx2*1.732f;

        p1 = new PointF(rect1.centerX()+dx1,rect1.centerY()-dy1);
        p3 = new PointF(rect1.centerX()+dx1,rect1.centerY()+dy1);
        p2 = new PointF(rect2.centerX()-dx2,rect2.centerY()-dy2);
        p4 = new PointF(p2.x,rect2.centerY()+dy2);
        p5 = new PointF((p1.x + p4.x)*0.5f,(p1.y + p4.y)*0.5f);
        p6 = new PointF((p2.x+p3.x)*0.5f,(p2.y+p3.y)*0.5f);

    }

    @Override
    protected void onDraw(Canvas canvas) {
        canvas.drawRGB(255, 255, 255);
        canvas.drawCircle(rect1.centerX(), rect1.centerY(), radius1, paint);
        canvas.drawCircle(rect2.centerX(), rect2.centerY(), radius2, paint);

        // 绘制贝塞尔曲线
        Path curve1 = new Path();
        curve1.moveTo(p1.x,p1.y);
        curve1.quadTo(p5.x,p5.y,p2.x,p2.y);
        curve1.lineTo(p4.x,p4.y);
        curve1.quadTo(p6.x,p6.y,p3.x,p3.y);
        curve1.lineTo(p1.x, p1.y);
        canvas.drawPath(curve1,paint);

        // 每次重绘时移动距离
        rect2.left +=5;
        rect2.right +=5;
        if (rect2.right > getWidth()){
            rect2.left = rect1.right + 30;
            rect2.right = rect2.left + radius2 * 2;
        }

        // 重新计算每个点的位置
        p2.x = rect2.centerX()-dx2;
        p2.y = rect2.centerY()-dy2;
        p4.x = p2.x;
        p4.y = rect2.centerY()+dy2;
        p5.x = (p1.x + p4.x)*0.5f;
        p5.y = (p1.y + p4.y)*0.5f;
        p6.x = (p2.x+p3.x)*0.5f;
        p6.y = (p2.y+p3.y)*0.5f;
    }

    // 用于改变时间
    private class TimeAnimation extends Animation {
        @Override
        protected void applyTransformation(float interpolatedTime, Transformation t) {
            super.applyTransformation(interpolatedTime, t);
            mInterpolatedTime = interpolatedTime;
            invalidate();
        }
    }

    private void startAnimation() {
        animation = new TimeAnimation();
        animation.setDuration(10000);
        animation.setInterpolator(new LinearInterpolator());
        animation.setRepeatCount(Animation.INFINITE);
        animation.setRepeatMode(Animation.REVERSE);
        startAnimation(animation);
    }

    @Override
    protected void onAttachedToWindow() {
        super.onAttachedToWindow();
        startAnimation();
    }
    private void stopAnimation() {
        this.clearAnimation();
        postInvalidate();
    }
    @Override
    protected void onDetachedFromWindow() {
        stopAnimation();
        super.onDetachedFromWindow();
    }

    @Override
    public boolean onTouchEvent(MotionEvent event) {
        // 重置
        rect2.left = rect1.right + 30;
        rect2.right = rect2.left + radius2 * 2;
        startAnimation();
        return true;
    }
}

参考: