此直方图策略已在git1.7.7（2011年9月）中引入，并带有以下描述（如OP所述）

“ git diff”学习了一个“
--histogram”选项，可以使用从jgit窃取的另一种差异生成机器，这可能会提供更好的性能。

JGit包括src/org/eclipse/jgit/diff/HistogramDiff.java和tst/org/eclipse/jgit/diff/HistogramDiffTest.java

那里的描述相当完整：

直方图差异

Bram Cohen的耐心差异算法的扩展形式。

此实现是通过使用Bram
Cohen的博客中概述的4条规则得出
的，然后进一步扩展为支持低发生率的常见元素。

该算法的基本思想是为 序列A的每个元素创建出现的直方图
。然后依次考虑序列B的每个元素。如果元素也存在于序列A中，并且出现次数较少，则将这些位置视为最长公共子序列（LCS）的候选对象。
扫描完B后，将出现次数最少的LCS选择为分割点。在LCS周围划分区域，并将算法递归应用于LCS之前和之后的部分。

通过始终选择发生次数最少的LCS位置，只要两个序列之间存在唯一的公共元素，该算法的行为就与Bram Cohen的耐心差异完全一样。
如果不存在唯一元素，则选择出现次数最少的元素。
与仅依靠标准Myers O(ND)算法产生的差异相比，这提供了更具可读性的差异。

为了防止该算法O(N^2)运行时间，直方图桶中唯一元素数量的上限由设置#setMaxChainLength(int)。

如果序列A的哈希元素散布到同一个哈希桶中的元素数量超过此数目，则算法会将区域传递给#setFallbackAlgorithm(DiffAlgorithm)。
如果未配置回退算法，则该区域将作为替换编辑发出。

在扫描序列B的过程中，#setMaxChainLength(int)不会对LCS匹配位置考虑多次出现的A元素，即使这在两个序列之间是相同的。这限制了找到LCS时必须考虑的序列A中的位置数量，并有助于维持较短的运行时间范围。

只要#setMaxChainLength(int)是一个小常数（例如64），该算法就会O(N * D)及时运行，其中N是输入长度的总和，D是结果中的编辑次数EditList。

如果提供的SequenceComparator具有良好的哈希函数MyersDiff，则即使其理论运行时间相同，该实现也通常会超出性能。

此实现有一个内部限制，它不能处理包含超过268,435,456（2 ^ 28）个元素的序列

请注意，早在2006年（git1.3）中，这种算法已用于pack_checkgit-verify-pack -v。它已在git 1.7.7中重新用于index-
pack

提交8c912ee实际上引入--histogram到差异：

将JGit的HistogramDiff算法移植到C语言上。粗糙数（TODO）表明，它比其--patience表亲以及默认的Meyers算法要快。

该实现已被重新设计为 使用结构和指针而不是位掩码，从而消除了JGit的2^28line limit。

为了方便起见，我们还使用xdiff的默认哈希表实现（xdl_hash_bits() 和XDL_HASHLONG()）。

提交8555123（git1.7.10，2012年4月）添加：

8c912ee（教学时间--histogram为diff2011-07-12）声称直方图比较比Myers和耐心都要快。

此后，我们已经合并了一个性能测试框架，因此添加一个测试，以比较在实际log -p工作负载中执行的各种差异任务。
这确实表明直方图差异略胜于Myers，而耐心则慢得多。

最后，提交07ab4de（git1.8.2，2013年3月）添加

config：引入diff.algorithm变量

与其他算法相比，某些用户或项目更喜欢不同的算法，例如，对myers或类似算法的耐心。
但是，每次使用diff时都指定适当的参数是不切实际的。而且，创建别名不能与其他基于diff的工具配合使用（git-show例如）。

因此，需要一种能够设置特定算法的配置变量。
目前，这四个值已被接受：

• ‘ myers‘（与完全不设置config变量具有相同的效果），
• ‘ minimal‘
• “ patience”和
• ‘ histogram‘。
  

提交07924d4并发添加了--diff-algorithm命令行选项。 正如OP[StuartP.Bentley]在评论中提到的那样：

您可以配置Git在默认情况下使用直方图 ：

git config --global diff.algorithm histogram

更新：Git 2.12（2017年第一季度）将淘汰在某些极端情况下具有灾难性性能问题的“快速哈希”。

参见Jeff
King（）提交1f7c926（2016年12月1日）。
（由Junio C
Hamano合并--在731490b号文件中，2016年12月19日）peffgitster

xdiff：掉落 XDL_FAST_HASH

该xdiff代码哈希一个diff两侧的每一行，然后比较这些哈希查找重复。总体性能不仅取决于我们能够计算哈希的速度，而且取决于我们看到的哈希冲突数。

的想法XDL_FAST_HASH是加快哈希计算。
但是，生成的哈希具有较差的碰撞行为。这意味着在某些情况下，它可以加快扩散速度（通过运行“ git log -p”
git.git可以提高速度~8%），但在其他情况下，则可以减慢速度。一个病理病例减速了100倍。

可能有一个更好的哈希函数可以同时覆盖这两个属性，但与此同时，我们最好还是使用原始哈希。在一般情况下，它的速度稍慢一些，但在令人惊讶的病理情况下却很少。

注意：“ git diff --histogram”的内存使用情况模式不佳，已使用Git
2.19（2018年第三季度）对其进行了重新排列以减少峰值使用率。

请参阅Stefan
Beller（）的commit
79cb2eb，commit
64c4e8b，commit
c671d4b，commit
2820985（2018年7月19日）。（由Junio
C
Hamano合并--在commit
57fbd8e中，2018年8月15日）stefanbeller
gitster

xdiff/xhistogram：将索引分配移入 find_lcs

这修复了递归多次时的内存问题，该问题可以复制为

seq 1   100000 >one
seq 1 4 100000 >two
git diff --no-index --histogram one two

在此补丁之前，histogram_diff将在调用之前递归地调用自身free_index，这意味着在递归过程中分配了很多内存，然后才释放它们。

通过将内存分配（及其免费调用）移入find_lcs，在递归之前内存将被释放，从而在递归的下一步中可以重用内存，而不必使用新的内存。

这仅解决了内存压力，而不是运行时复杂性，这对于上面概述的极端情况也很糟糕。