替代连续String.replace

Question

我想替换String输入中的一些字符串：

string=string.replace("<h1>","<big><big><big><b>");
string=string.replace("</h1>","</b></big></big></big>");
string=string.replace("<h2>","<big><big>");
string=string.replace("</h2>","</big></big>");
string=string.replace("<h3>","<big>");
string=string.replace("</h3>","</big>");
string=string.replace("<h4>","<b>");
string=string.replace("</h4>","</b>");
string=string.replace("<h5>","<small><b>");
string=string.replace("</h5>","</b><small>");
string=string.replace("<h6>","<small>");
string=string.replace("</h6>","</small>");

如您所见，这种方法不是最佳方法，因为每次我必须搜索要替换的部分时，等等，并且字符串是不可变的…而且输入很大，这意味着要考虑一些性能问题。

有没有更好的方法来减少此代码的复杂性？

Answer 1

尽管StringBuilder.replace()与相比是一个巨大的改进String.replace()，但它 离 优化还差 很远 。

问题StringBuilder.replace()在于，如果替换的长度与可替换部分的长度不同（适用于我们的情况），则char可能必须分配更大的内部数组，并且必须复制内容，然后替换才会发生（这也涉及复制）。

想象一下：您有一个包含10.000个字符的文本。如果要将"XY"位置1（第2个字符）处的子字符串替换为"ABC"，则实现必须重新分配char至少大于1
的缓冲区，必须将旧内容复制到新数组，并且必须复制9.997个字符（从位置3）右移1以适应"ABC"位置"XY"，最后将的字符"ABC"复制到启动位置1。每次更换都必须这样做！太慢了

更快的解决方案：即时构建输出

我们可以 即时 构建输出：不包含可替换文本的部分可以简单地附加到输出中，并且如果我们找到可替换的片段，则可以替换而不是替换。从理论上讲，仅循环输入
一次 即可生成输出。听起来很简单，实现起来并不难。

实现方式：

我们将使用Map预加载的replaceable-replacement字符串的映射：

Map<String, String> map = new HashMap<>();
map.put("<h1>", "<big><big><big><b>");
map.put("</h1>", "</b></big></big></big>");
map.put("<h2>", "<big><big>");
map.put("</h2>", "</big></big>");
map.put("<h3>", "<big>");
map.put("</h3>", "</big>");
map.put("<h4>", "<b>");
map.put("</h4>", "</b>");
map.put("<h5>", "<small><b>");
map.put("</h5>", "</b></small>");
map.put("<h6>", "<small>");
map.put("</h6>", "</small>");

并使用它，这里是替换代码：（ 代码后有更多解释）

public static String replaceTags(String src, Map<String, String> map) {
    StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

    for (int pos = 0;;) {
        int ltIdx = src.indexOf('<', pos);
        if (ltIdx < 0) {
            // No more '<', we're done:
            sb.append(src, pos, src.length());
            return sb.toString();
        }

        sb.append(src, pos, ltIdx); // Copy chars before '<'
        // Check if our hit is replaceable:
        boolean mismatch = true;
        for (Entry<String, String> e : map.entrySet()) {
            String key = e.getKey();
            if (src.regionMatches(ltIdx, key, 0, key.length())) {
                // Match, append the replacement:
                sb.append(e.getValue());
                pos = ltIdx + key.length();
                mismatch = false;
                break;
            }
        }
        if (mismatch) {
            sb.append('<');
            pos = ltIdx + 1;
        }
    }
}

测试它：

String in = "Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End";
System.out.println(in);
System.out.println(replaceTags(in, map));

输出：（ 包装以避免滚动条）

Yo<h1>TITLE</h1><h3>Hi!</h3>Nice day.<h6>Hi back!</h6>End

Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End

该解决方案比使用正则表达式更快，因为它涉及很多开销，例如编译a
Pattern，创建Matcheretc等，并且regexp也更加通用。它还会在引擎盖下创建许多临时对象，这些对象在替换后会被丢弃。在这里，我只使用了一个StringBuilder（加号的char数组），并且代码String仅对输入进行一次迭代。同样，该解决方案比使用StringBuilder.replace()该答案顶部详细介绍的解决方案要快得多。

注释和解释

我StringBuilder在这样的replaceTags()方法中初始化：

StringBuilder sb = new StringBuilder(src.length() + src.length() / 2);

因此，基本上，我以初始文件长度的150％的初始容量创建了它String。这是因为我们的替换项比可替换的文本长，因此，如果发生替换，则输出将明显长于输入项。赋予较大的初始容量StringBuilder将根本不会进行内部char[]重新分配（当然，所需的初始容量取决于可更换的替换对及其在输入中的出现频率/发生率，但这+
50％是一个不错的上限估计值）。

我还利用了所有可替换字符串都以'<'字符开头的事实，因此找到下一个潜在的可替换位置变得非常快：

int ltIdx = src.indexOf('<', pos);

这只是一个简单的循环和char内部的比较String，并且由于它总是从pos（而不是从输入的开头）开始搜索，因此，整个代码String仅对输入进行一次迭代。

最后要判断可替换String位置是否确实出现在可替换位置，我们使用该String.regionMatches()方法来检查可替换字符串，这也非常快，因为它所做的只是char在循环中比较值并在第一个不匹配字符处返回。

还有一个加号：

这个问题没有提及，但是我们的输入是一个HTML文档。HTML标记不区分大小写，这意味着输入内容可能包含<H1>而不是<h1>。
对于此算法，这不是问题。类中的regionMatches()in
String有一个重载，它支持不区分大小写的比较：

boolean regionMatches(boolean ignoreCase, int toffset, String other,
                          int ooffset, int len);

因此，如果我们想修改算法以查找和替换相同但使用不同字母大小写的输入标签，则只需修改以下一行：

if (src.regionMatches(true, ltIdx, key, 0, key.length())) {

使用此修改后的代码，可替换标签变得不区分大小写：

Yo<H1>TITLE</H1><h3>Hi!</h3>Nice day.<H6>Hi back!</H6>End
Yo<big><big><big><b>TITLE</b></big></big></big><big>Hi!</big>Nice day.
<small>Hi back!</small>End