如何判断CPU是大端还是小端模式

2018-01-18 C语言

一、概念及详解

在各种体系的计算机中通常采用的字节存储机制主要有两种： Big-Endian和Little-Endian，即大端模式和小端模式。

Big-Endian和Little-Endian的定义如下：

1) Little-Endian：就是低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。
2) Big-Endian：就是高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。

举一个例子，比如16进制数字0x12345678在内存中的表示形式为：

大端小端没有谁优谁劣，各自优势便是对方劣势：

小端模式：强制转换数据不需要调整字节内容，1、2、4字节的存储方式一样。
大端模式：符号位的判定固定为第一个字节，容易判断正负。

【Android】源码分析 - LRUCache缓存实现原理

2018-01-12 Android

一、Android中的缓存策略

一般来说，缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比较好理解，那么为什么还要删除缓存呢？这是因为不管是内存缓存还是硬盘缓存，它们的缓存大小都是有限的。当缓存满了之后，再想其添加缓存，这个时候就需要删除一些旧的缓存并添加新的缓存。

因此LRU(Least Recently Used)缓存算法便应运而生，LRU是近期最少使用的算法，它的核心思想是当缓存满时，会优先淘汰那些近期最少使用的缓存对象，有效的避免了OOM的出现。在Android中采用LRU算法的常用缓存有两种：LruCache和DisLruCache，分别用于实现内存缓存和硬盘缓存，其核心思想都是LRU缓存算法。

其实LRU缓存的实现类似于一个特殊的栈，把访问过的元素放置到栈顶（若栈中存在，则更新至栈顶；若栈中不存在则直接入栈），然后如果栈中元素数量超过限定值，则删除栈底元素（即最近最少使用的元素）。详细算法实现如下图：

新数据压入到栈顶；
每当缓存命中（即缓存数据被访问），则将数据移到栈顶；
当栈满的时候，将栈底的数据丢弃。

举个例子演示一下：

二、LruCache的使用

LruCache是Android 3.1所提供的一个缓存类，所以在Android中可以直接使用LruCache实现内存缓存。而DisLruCache目前在Android 还不是Android SDK的一部分，但Android官方文档推荐使用该算法来实现硬盘缓存。

讲到LruCache不得不提一下LinkedHashMap，因为LruCache中Lru算法的实现就是通过LinkedHashMap来实现的。LinkedHashMap继承于HashMap，它使用了一个双向链表来存储Map中的Entry顺序关系，这种顺序有两种，一种是LRU顺序，一种是插入顺序，这可以由其构造函数public LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder)的最后一个参数accessOrder来指定。所以，对于get、put、remove等操作，LinkedHashMap除了要做HashMap做的事情，还做些调整Entry顺序链表的工作。LruCache中将LinkedHashMap的顺序设置为LRU顺序来实现LRU缓存，每次调用get(也就是从内存缓存中取图片)，则将该对象移到链表的尾端。调用put插入新的对象也是存储在链表尾端，这样当内存缓存达到设定的最大值时，将链表头部的对象（近期最少用到的）移除。关于LinkedHashMap详解请前往：理解LinkedHashMap

【算法】字符串循环移位后是否可包含

2017-12-31 Algorithm

问题

给定两个字符串s1和s2，要求判断s2是否能够被通过s1做循环移位（rotate）得到的字符串包含。
例如，s1=AABCD和s2=CDAA，返回true；给定s1=ABCD和s2=ACBD，返回false。

解法一

最直接最笨的方法就对s1进行循环移动，再进行字符串包含的判断，从而遍历其所有的可能性。字符串循环移动，时间复杂度为O（n），字符串包含判断，采用普通的方法，时间复杂度为O（n*m），总体复杂度为O（n*n*m）。字符串包含判断，若采用KMP算法，时间复杂度为O（n），这样总体的复杂度为O（n*n）。若字符串的长度n较大，显然效率比较低。其中n为s1的长度，m为s2的长度。

解法二

对s1的循环移位操作，可以使用拼接s1+s1的方式得到。

以S1 = ABCD为例，先分析对S1进行循环移位之后的结果，如下所示：

ABCD—>BCDA—->CDAB—->DABC—->ABCD……

假设我们把前面的移走的数据进行保留，会发现有如下的规律：

ABCD—>ABCDA—->ABCDAB—->ABCDABC—->ABCDABCD……

因此，可以看出对s1做循环移位所得到的字符串都将是字符串s1s1的子字符串。如果s2可以由s1循环移位得到，那么s2一定在s1s1上，这样时间复杂度就降低了。

【算法】如何判断链表有环

2017-12-24 Algorithm

如何判断单链表是否存在环

有一个单向链表，链表当中有可能出现“环”，就像题图这样。如何用程序判断出这个链表是有环链表？

不允许修改链表结构。

时间复杂度O(n)，空间复杂度O(1)。

方法一、穷举遍历

方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。

例如这样的链表：A->B->C->D->B->C->D，当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。

假设从链表头节点到入环点的距离是D，链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 ，可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。

【Android】源码分析 - Activity启动流程

2017-12-18 Android

启动Activity的方式

Activity有2种启动的方式，一种是在Launcher界面点击应用的图标、另一种是在应用中通过Intent进行跳转。我们主要介绍与后者相关的启动流程。

1 2	Intent intent = new Intent(this, TestActivity.class); startActivity(intent);

从Activity入手

@Override
public void startActivity(Intent intent) {
    this.startActivity(intent, null);
}

@Override
public void startActivity(Intent intent, @Nullable Bundle options) {
    if (options != null) {
        startActivityForResult(intent, -1, options);
    } else {
        // Note we want to go through this call for compatibility with
        // applications that may have overridden the method.
        startActivityForResult(intent, -1);
    }
}

【Java】HashMap源码分析（JDK1.8）

2017-11-25 Java

前言

Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，类继承关系如下图所示：

下面针对各个实现类的特点做一些说明：

(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它继承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

【Android】源码分析 - View事件分发机制

2017-11-18 Android

事件分发对象

（1）所有 Touch 事件都被封装成了 MotionEvent 对象，包括 Touch 的位置、时间、历史记录以及第几个手指(多指触摸)等。

（2）事件类型分为 ACTION_DOWN， ACTION_UP，ACTION_MOVE，ACTION_POINTER_DOWN，ACTION_POINTER_UP， ACTION_CANCEL，每个事件都是以 ACTION_DOWN 开始 ACTION_UP 结束。

主要发生的Touch事件有如下四种：

MotionEvent.ACTION_DOWN：按下View（所有事件的开始）
MotionEvent.ACTION_MOVE：滑动View
MotionEvent.ACTION_CANCEL：非人为原因结束本次事件
MotionEvent.ACTION_UP：抬起View（与DOWN对应）

事件列：从手指接触屏幕至手指离开屏幕，这个过程产生的一系列事件
任何事件列都是以DOWN事件开始，UP事件结束，中间有无数的MOVE事件，如下图：

即当一个点击事件发生后，系统需要将这个事件传递给一个具体的View去处理。这个事件传递的过程就是分发过程。

（3）对事件的处理包括三类，分别：

传递——dispatchTouchEvent()函数；
拦截——onInterceptTouchEvent()函数
消费——onTouchEvent()函数和 OnTouchListener

【Java】生产者消费者模式的实现

2017-11-10 Java

前言

生产者消费者问题是线程模型中的经典问题：生产者和消费者在同一时间段内共用同一存储空间，生产者向空间里生产数据，而消费者取走数据。

阻塞队列就相当于一个缓冲区，平衡了生产者和消费者的处理能力。这个阻塞队列就是用来给生产者和消费者解耦的。

wait/notify方法

首先，我们搞清楚Thread.sleep()方法和Object.wait()、Object.notify()方法的区别。根据这篇文章java sleep和wait的区别的疑惑?

sleep()是Thread类的方法；而wait()，notify()，notifyAll()是Object类中定义的方法；尽管这两个方法都会影响线程的执行行为，但是本质上是有区别的。
Thread.sleep()不会导致锁行为的改变，如果当前线程是拥有锁的，那么Thread.sleep()不会让线程释放锁。如果能够帮助你记忆的话，可以简单认为和锁相关的方法都定义在Object类中，因此调用Thread.sleep()是不会影响锁的相关行为。
Thread.sleep和Object.wait都会暂停当前的线程，对于CPU资源来说，不管是哪种方式暂停的线程，都表示它暂时不再需要CPU的执行时间。OS会将执行时间分配给其它线程。区别是调用wait后，需要别的线程执行notify/notifyAll才能够重新获得CPU执行时间。

【Android】Dialog异常CalledFromWrongThreadException深入分析

2017-10-26 Android

问题

在使用Dialog时，因为线程问题，在调用dismiss方法时出现了CalledFromWrongThreadException的Crash，如下：

1	android.view.ViewRootImpl$CalledFromWrongThreadException: Only the original thread that created a view hierarchy can touch its views.

抛出异常为CalledFromWrongThreadException，很明显第一反应就是出现了非ui线程进行了ui操作造成了此异常。通过分析工程代码，发现本质上是因为在非ui线程中创建了Dialog，而在主线程（即ui线程）中调用了show()以及dismiss()方法，我把问题模型写成测试代码如下：

public class MainActivity extends BaseActivity {
    private static final String TAG = "MainActivity test";
    private ProgressDialog dialog;


    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        EventBus.getDefault().register(this);

        new Thread(new Runnable() {
            @Override
            public void run() {
                Looper.prepare();

                //子线程中创建Dialog
                dialog = new ProgressDialog(MainActivity.this);
                dialog.setCanceledOnTouchOutside(true);
                dialog.setOnCancelListener(new DialogInterface.OnCancelListener() {
                    @Override
                    public void onCancel(DialogInterface dialog) {
                        Log.d(TAG, "Dialog onCancel thread: " + getThreadInfo());
                    }
                });
                dialog.setOnDismissListener(new DialogInterface.OnDismissListener() {
                    @Override
                    public void onDismiss(DialogInterface dialog) {
                        Log.d(TAG, "Dialog onDismiss thread: " + getThreadInfo());
                    }
                });
                dialog.setMessage("正在加载...");
                Log.d(TAG, "Dialog create thread: " + getThreadInfo());

                Looper.loop();
            }
        }).start();


        Button btn = (Button) findViewById(R.id.btn_helloworld);
        btn.setOnClickListener(new View.OnClickListener() {
            @Override
            public void onClick(View v) {
                //UI主线程中show，然后点击空白区域dismiss
                dialog.show();
                Log.d(TAG, "Dialog show thread: " + getThreadInfo());
            }
        });
    }

  
    /**
     * 输出线程信息
     */
    private String getThreadInfo(){
        return "[" + Thread.currentThread().getId() + "]" +
                ((Looper.myLooper() == Looper.getMainLooper())? " is UI-Thread" : "");
    }
}

就是Activity打开的时候，使用work子线程创建了一个Dialog，然后手动点击按钮的时候，显示Dialog。再点击空白处，dialog本应该dismiss的，但是直接crash了。抛出了CalledFromWrongThreadException的异常。

在上面的代码中，我顺便输出了Dialog每个操作的线程ID，同时会判定是不是ui主线程。我们来看看log：

10-26 16:11:07.836 7405-7652/com.cuc.myandroidtest D/MainActivity test: Dialog create thread: [3953]
10-26 16:11:27.763 7405-7405/com.cuc.myandroidtest D/MainActivity test: Dialog show thread: [1] is UI-Thread
10-26 16:11:35.642 7405-7652/com.cuc.myandroidtest D/MainActivity test: Dialog onCancel thread: [3953]

——– beginning of crash

可以看到，以上出现的问题中执行Dialog操作的线程信息如下：

创建Dialog：work子线程
show()：ui主线程
cancel()：work子线程
dismiss()：因为crash没有执行到，未知

如果说只有创建这个控件的线程才能去更新该控件的内容。那么在调用show方法的时候为什么不会crash，然后dismiss的时候才会崩溃？

另外，到底是不是所有的操作都必须放到ui线程中执行才对？带着疑问我们深入Dialog源码一看究竟。

【算法】字符串是否包含问题

2017-10-18 Algorithm

在网上看到这篇文章：一次谷歌面试趣事。觉得其中的算法题以及作者的解决思路很有趣，就拿来分享一下吧。

问题

假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？

比如，如果是下面两个字符串：

String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPO

答案是true，所有在String2里的字母String1也都有。如果是下面两个字符串：

String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPZ

答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

iTimeTraveler

Someone knock at the door.

Mr.Seven