首先，我估计有一部分的同学可能还不知道DiffUtil是什么，说实话，之前我也根本不了解这是什么东西。DiffUtil是我在公司实习的时候了解到的一个类，在那之前，我使用RecyclerView的方式也是大部分的人差不多，就是RecyclerView和它的四大组成部分任意组合。
当时在公司第一次看到这个东西的时候，立即两眼发光，非常好奇这是什么东西，就好像在大街上看到美女一样。后来在非工作时间的时候，我去了解了一下这个类，不过当时也只是简单的了解这个东西。现在在系统的学习RecyclerView的源码，我觉得有必要深入的了解和学习一下这个东西--DiffUtil。
本文参考资料:

Investigating Myers' diff algorithm: Part 1 of 2

本文有一部分的内容来自上文的翻译。我的建议是，各位同学可以直接看上面的文章，大佬的文章已经将DiffUtil的核心算法讲的非常透彻。
本文打算从三个角度来分析DiffUtil

DiffUtil的基本使用
Myers差量算法的深入探究
DiffUtil的Myers算法实现以及DiffUtil怎么跟Adapter联系起来的

1. 概述

在正式分析DiffUtil之前，我们先来对DiffUtil有一个大概的了解--DiffUtil到底是什么东西。
我们相信大家都遇到一种情况，那就是在一次操作里面可能会同时出现remove、add、change三种操作。像这种情况，我们不能调用notifyItemRemoved、notifyItemInserted或者notifyItemChanged方法，为了视图立即刷新，我们只能通过调用notifyDataSetChanged方法来实现。
而notifyDataSetChanged方法有什么缺点呢？没有动画！对，通过调用notifyDataSetChanged方法来刷新视图，每个操作是没有动画，这就很难受了！
有没有一种方式可以实现既能保留动画，又能刷新动画呢？我们单从解决问题的角度来说，我们可以设计一种算法，来比较变化前后的数据源有哪些变化，这里的变化包括，如上的三种操作。哪些位置进行了change操作，哪些地方进行了add操作，哪些地方进行了remove操作，可以通过这种算法计算出来。
Google爸爸考虑到这个问题大家都能遇到，那我帮你们实现，这样你们就不用自己去实现了，这就是DiffUtil的由来。

2. DiffUtil的基本使用

在正式分析DiffUtil的源码之前，我们先来看看DiffUtil的基本使用，然后我们从基本使用入手，这样看代码的时候才不会迷茫。
我们想要使用DiffUtil时，有一个抽象类Callback是我们必须了解的，我们来看看，了解它的每个方法都都有什么作用。

方法名	作用
getOldListSize	原数据源的大小
getNewListSize	新数据源的大小
areItemsTheSame	判断给定两个Item的是否同一个Item。给定的是两个Position，分别是原数据源的位置和新数据源的位置。判断两个Item是否是同一个Item，如果是不同的对象（新数据源和旧数据源持有的不是同一批对象，新数据源可能是从旧数据源那里深拷贝过来，也有重新进行网络请求返回的），可以给每个Item设置一个id，如果是同一个对象，可以直接使用==来判断
areContentsTheSame	判断给定的两个Item内容是否相同。只有`areItemsTheSame`返回为true，才会回调此方法。也就是说，只能当两个Item是同一个Item，才会调用此方法来判断给定的两个Item内容是否相同。
getChangePayload	用于局部刷新，回调此方法表示所给定的位置肯定进行change操作，所以这里不需要判断是否为change操作。

简单的了解Callback每个方法的作用之后，我们现在来看看DiffUtil是怎么使用的。
我们先来看看ItemCallback是怎么实现的：

public class RecyclerItemCallback extends DiffUtil.Callback {    private List<Bean> mOldDataList;    private List<Bean> mNewDataList;    public RecyclerItemCallback(List<Bean> oldDataList, List<Bean> newDataList) {        this.mOldDataList = oldDataList;        this.mNewDataList = newDataList;
    }    @Override
    public int getOldListSize() {        return mOldDataList.size();
    }    @Override
    public int getNewListSize() {        return mNewDataList.size();
    }    @Override
    public boolean areItemsTheSame(int oldItemPosition, int newItemPosition) {        return Objects.equals(mNewDataList.get(newItemPosition).getId(), mOldDataList.get(oldItemPosition).getId());
    }    @Override
    public boolean areContentsTheSame(int i, int i1) {        return Objects.equals(mOldDataList.get(i).getContent(), mNewDataList.get(i1).getContent());
    }
}

这里，areItemsTheSame方法是通过id来判断两个Item是不是同一个Item，其次areContentsTheSame方法是通过判断content来判断两个Item的内容是否相同。
然后，我们再来看看DiffUtil是怎么使用的：

    private void refreshData() {        final List<Bean> oldDataList = new ArrayList<>();        final List<Bean> newDataList = mDataList;        // deep copy
        for (int i = 0; i < mDataList.size(); i++) {
            oldDataList.add(mDataList.get(i).deepCopy());
        }        // change
        for (int i = 0; i < newDataList.size(); i++) {            if (i % 5 == 0) {
                newDataList.get(i).setContent("change data = " + i);
            }
        }        // remove
         newDataList.remove(0);
         newDataList.remove(0);        // add
        addData(5, newDataList);        // diffUtil
        RecyclerItemCallback recyclerItemCallback = new RecyclerItemCallback(oldDataList, newDataList);
        DiffUtil.DiffResult diffResult = DiffUtil.calculateDiff(recyclerItemCallback, false);
        diffResult.dispatchUpdatesTo(mRecyclerAdapter);
    }

这里我们进行一些操作，来该改变数据源某些数据。请注意的是：所有的操作都必须在Adapter的数据源进行操作，否则这里刷新完全没有意义。正如上面的实现，在变换之前,我先将源数据深拷贝到oldDataList数组，然后所有的变化操作都在mDataList数组(因为它是Adapter的数据源，操作它才有意义)，然后将改变之后的数据称为newDataList。
如下便是DiffUtil的真正使用:

        RecyclerItemCallback recyclerItemCallback = new RecyclerItemCallback(oldDataList, newDataList);
        DiffUtil.DiffResult diffResult = DiffUtil.calculateDiff(recyclerItemCallback, false);
        diffResult.dispatchUpdatesTo(mRecyclerAdapter);

上面便是使用DiffUtil的固定步骤：显示创建ItemCallback的对象，然后通过DiffUtil的calculateDiff方法来进行差量计算，最后就是调用dispatchUpdatesTo方法进行notify操作。
整个过程还是比较简单的，我们来看看展示效果：

了解完DiffUtil是怎么使用，接下来我们将正式DiffUtil的差量计算算法，如果还有同学不明白DiffUtil怎么使用，可以到我的github下载上面的Demo： DiffUtilDemo。

3. Myers算法

DiffUtil进行差量计算采用的是著名的Myers算法。对于我们这种移动开发的菜逼，很少接触到算法，所以知道这个算法的同学应该比较少，况且还深入了解它。当然大家不要怕，本文会详细的介绍Myers算法，包括它的理论和实现。放心吧，这个算法比较简单，我觉得比看毛片算法还简单。
本部分的大部分内容来自于Investigating Myers' diff algorithm: Part 1 of 2这篇文章，有兴趣的同学可以直接看这篇文章。

(1). 定义概念

我们先来简单分析一下我们需要达到的目的。比如说有A数组和B数组，我们想要达到的目的就是，从A数组变成B数组，分别要进行哪些操作。这些操作里面无非是remove和add（在这里，move操作和change操作我们将拆分为remove和add操作），这里就让我想起来算法题中一道题是编辑距离。编辑距离的意思就是：从A字符串变成B字符串的最小操作步数，这里的操作就是上面的两种操作，有兴趣的可以看我之前的一篇文章：Java 算法-编辑距离(动态规划)。
我们就可以求解从A数组变成B数组的问题转换成为求解从A字符串变成B字符串的问题(其实，字符串就是字符数组)。
我们一步一步的分析这个问题，我们假设A字符串为ABCABBA，B字符串为CBABAC。然后我们可以得到下面的一个二维数组（如下的软件连接：DiffTutorial）。

从上面的图片中，我们可以看出来，我们假设X轴是原字符串，Y轴是新字符串。其中，这个问题的目的就是我们需要从点(0,0)(原点)到点(m,n)（终点）的最短路径，学过基本算法的同学应该都知道，这个就是回溯法的基本操作。
然后我们在来看一张图片：

这张图片相对于上面的图片，就是多了一些对角线。我们知道要想求解从(0,0)到(m,n)的最短路径，我们只能往右或者往下走，因为往上或者往左走都是在绕路。而多了对角线之后，我们还可以走对角线，如果能走对角线，相对于往右或者往下走的话，就更加的近了。那这些对角线的是按照什么规则画出来的呢？
其实非常的简单，我们就从左往右，从上往下扫描整个二维数组，如果当前位置的x表示的字符跟y表示的字符相同的话，就画一条对角线(从左上到右下)。从这里，我们就可以看出来，我们想要的答案就是路径里面尽可能包含多的对角线。

这里，我们简单的定义一下，向右走一个格子或者向下走一个格子表示一步，而走一条对角线不计入步数。

我们假设向右移动一步表示从A字符串中remove删除一个字符，向下移动一步表示向B字符串add一个字符。
在分析寻找路径的算法之前，我们先来定义几个概念：

snakes:一个snake表示向右或者向下走了一步，这个过程包括n个对角线。
k lines: k lines表示长的对角线，其中每个k = x - y。假设一个点m(m,n),那么它所在的k line值为m - n。如图：

作者：琼珶和予
链接：https://www.jianshu.com/p/3a0d0ce4e649

RecyclerView 源码分析(六) - DiffUtil的差量算法分析

1. 概述

2. DiffUtil的基本使用

3. Myers算法

(1). 定义概念