这个早期的问题询问了4种不同的Git diff策略之间的区别，但是只解释了myers和patience之间的区别，这在其他地方已经非常好地解释了。
histogram策略如何工作？它与patience有什么不同？git-diff man页面只说它“扩展了耐心算法以支持低出现频率的公共元素”。其他页面提到它更快，并且来自JGit，但他们没有解释其算法或结果与patience的区别在哪里或如何不同。
patience算法相关的histogram算法的说明？（如果只是实现性能上的问题，没有产生不同结果的情况，为什么不将其作为patience的新后端实现？）“
git diff”学会了一个“--histogram”选项，使用从jgit窃取的不同的差异生成机制，这可能会提供更好的性能。
JGit包括 src/org/eclipse/jgit/diff/HistogramDiff.java 和 tst/org/eclipse/jgit/diff/HistogramDiffTest.java
这里的描述相当完整：
HistogramDiff
这个实现是通过使用Bram Cohen的博客中概述的4个规则派生出来的，然后进一步扩展以支持低出现频率的常见元素。
算法的基本思想是为序列A的每个元素创建一个出现次数的直方图。然后依次考虑序列B的每个元素。如果该元素也存在于序列A中，并且具有更低的出现次数，则将其位置视为最长公共子序列（LCS）的候选项。
扫描B完成后，选择具有最少出现次数的LCS作为拆分点。该区域围绕LCS进行拆分，并对LCS之前和之后的部分递归应用算法。
通过始终选择具有最低出现次数的LCS位置，当两个序列之间存在唯一的公共元素时，此算法的行为与Bram Cohen的patience diff完全相同。
当不存在唯一元素时，将选择出现次数最低的元素。
这提供了比仅回退到标准Myers的O(ND)算法产生更可读的差异。
为了防止算法具有O(N^2)的运行时间，对直方图桶中唯一元素的数量设置了上限，由#setMaxChainLength(int)进行配置。
如果序列A具有超过此数量的元素散列到同一个哈希桶中，则算法将该区域传递给#setFallbackAlgorithm(DiffAlgorithm)。
如果未配置回退算法，则该区域将作为替换编辑发出。
在扫描序列B期间，任何在A中出现超过#setMaxChainLength(int)次的元素都不会考虑用于LCS匹配位置，即使它是两个序列之间的常见元素也是如此。这限制了必须考虑以找到LCS的A序列中的位置的数量，并有助于维护较低的运行时间下限。
只要#setMaxChainLength(int)是一个小常数（例如64），该算法就以O(N * D)的时间运行，其中N是输入长度的总和，D是结果EditList中的编辑数。
如果提供的SequenceComparator具有良好的哈希函数，则即使其理论运行时间相同，该实现通常优于MyersDiff。
此实现具有一个内部限制，防止其处理具有超过268,435,456（2^28）个元素的序列
git-verify-pack -v。它在Git 1.7.7中被重用，用于index-pack。（链接）（链接）
提交 8c912ee 实际上引入了 --histogram 到 diff 命令：
将 JGit 的 HistogramDiff 算法移植到 C。初步数据（待办事项）显示，它比其
--patience表亲以及默认的 Meyers 算法更快。该实现已经重新设计为使用结构体和指针，而不是位掩码，因此消除了 JGit 的
2^28行限制。我们还使用了
xdiff的默认哈希表实现（使用xdl_hash_bits()和XDL_HASHLONG()）方便快捷。
提交 8555123 (git 1.7.10, 2012年4月) 添加了：
8c912ee（教学
--histogram到diff，2011-07-12）声称直方图差异比Myers和patience更快。此后，我们已经整合了一个性能测试框架，因此添加了一个测试，比较在真实的'
log -p'工作负载中执行的各种差异任务。
确实显示直方图差异略胜于Myers，而patience比其他差异算法慢得多。
最后，提交 07ab4de（git 1.8.2，2013年3月） 添加
一些用户或项目更喜欢使用不同的算法，例如耐心算法（patience）而非myers或类似算法。然而，每次使用diff时指定适当的参数是不切实际的。此外，创建别名与基于diff的其他工具（例如git-show）不兼容。因此，需要一个配置变量来设置特定的算法。目前，接受这四个值：'myers'（与不设置配置变量具有相同效果），'minimal'，'patience'和'histogram'。
config：引入diff.algorithm变量
提交 07924d4 同时添加了 --diff-algorithm 命令行选项。
正如 OP Stuart P. Bentley 在 评论中提到的那样：
you can configure Git to use histogram by default with:
git config --global diff.algorithm histogram
更新：Git 2.12（2017年第一季度）将取消“快速哈希”，该哈希在某些情况下表现极差。
请参见提交1f7c926（由Jeff King（peff）于2016年12月1日提交。
(由Junio C Hamano -- gitster --合并于提交731490b，2016年12月19日)
xdiff: 删除XDL_FAST_HASH
xdiff代码对差异的双方的每一行进行哈希处理，然后比较这些哈希值以查找重复项。总体性能取决于我们计算哈希值的速度以及我们看到的哈希碰撞数量。
XDL_FAST_HASH的想法是加速哈希计算。
但生成的哈希值具有更糟糕的碰撞行为。这意味着在某些情况下，它可以加快差异速度（在git.git上运行“git log -p”会提高〜8％），但在其他情况下可能会减慢速度。一个特例看到了100倍以上的减速。可能有更好的哈希函数涵盖了两个属性，但与此同时，我们最好使用原始哈希。在常见情况下稍微慢一些，但没有那么多令人惊讶的特殊情况。
git diff --histogram" 曾经存在内存使用模式不佳的问题，但在Git 2.19 (2018年第三季度)中已经进行了重新排列以减少峰值使用率。
查看提交 79cb2eb, 提交 64c4e8b, 提交 c671d4b, 提交 2820985 (2018年7月19日) 由Stefan Beller (stefanbeller)进行。
(由Junio C Hamano -- gitster --于提交 57fbd8e中合并，2018年8月15日)
xdiff/xhistogram：将索引分配移到find_lcs中
This fixes a memory issue when recursing a lot, which can be reproduced as
seq 1 100000 >one seq 1 4 100000 >two git diff --no-index --histogram one twoBefore this patch,
histogram_diffwould call itself recursively before callingfree_index, which would mean a lot of memory is allocated during the recursion and only freed afterwards.By moving the memory allocation (and its free call) into
find_lcs, the memory is free'd before we recurse, such that memory is reused in the next step of the recursion instead of using new memory.This addresses only the memory pressure, not the run time complexity, that is also awful for the corner case outlined above.
查看提交 43ad3af, 提交 4a37b80, 提交 61f8839, 提交 9df0fc3 (2022年2月16日) 由Phillip Wood (phillipwood)完成。
(由Junio C Hamano -- gitster --合并于提交 47be28e, 2022年3月9日)
xdiff: 修复内存泄漏报告者: Junio C Hamano
签名者: Phillip Wood
尽管耐心算法和直方图算法会初始化环境，但如果出现错误，它们不会释放环境。
相比之下，Myers算法在xdl_do_diff()中初始化环境，并在出现错误时释放它。
通过在xdl_do_diff()中始终初始化环境并在出现错误时释放它来解决此问题。
git config --global diff.algorithm histogram 可以用于配置 Git 默认使用直方图算法来比较最后一次提交的差异。 - Stuart P. BentleyXDL_FAST_HASH与这一切有什么关系？ - Stuart P. Bentley