==代替Object#equals() - 加速在容器类中搜索元素速度的可能性

== vs. Object#equals() to accelerate Collection#contains()

问题的描述

众所周知，在需要将对象进行大量比较(equals)的场景，比如List#contains()的大量调用中，Object#equals(Object)实现的效率是很重要的。

提高对象比较效率的途径之一是用地址比较来代替内容比较。比如String#equals(Object)实现的内部逻辑应该是先进行地址比较，看是不是同一个对象；否则再进行内容比较。

但是String#equals(Object)还是不能彻底摆脱内容比较。

以String为例，我们来讨论用纯粹地址比较来实现Object#equals(Object)的可能性。

 

String的内部实现

其实，Java编译对字符串赋值的处理和String#intern()提供了将字符串对象放在常量池(Constant Pool)里，并且内容相同的字符串共享同一对象的可能 -- 它们的引用指向同一片地址。

如果这种常量池和共享的模式做彻底了，对字符串的比较就可以用纯粹地址比较。

但是，考虑到有些字符串，比如仅仅是用于日志打印输出，其实生存周期很短。所以并不是所有的字符串都需要以共享的方式放在常量池中，它们也应被允许生存在Heap中，甚至Eden中，能迅速被回收。而且有重复对象(redundance)。

这种灵活性，使String无法做纯粹的地址比较。

 

Symbol vs. String

虽然无法控制JVM底层内存管理机制，但我们仍然可以模拟常量池，并对对象做纯粹的地址比较。

 

package trial;

import java.util.HashMap;
import java.util.Map;

public class Symbol {
    private final static Map<String, Symbol> symbolPool = new HashMap<String, Symbol>();
   
    public static Symbol newInstance(String content) {
        String internContent = content.intern();
        Symbol symbol = symbolPool.get(internContent);
        if (symbol == null) {
            symbol = new Symbol(internContent);
            symbolPool.put(internContent, symbol);
        }
        return symbol;
    }

    private String stringValue;
    
    private Symbol(String content) {
        this.stringValue = content;
    }

    @Override
    public int hashCode() {
        return this.stringValue.hashCode();
    }

    @Override
    public String toString() {
        return stringValue;
    }
}

 

 

特征

使用Symbol的前提是，需要大量对象比较。而且因为实际的需要，即便不放在常量池中，对象的生存周期也较长。

 

用Symbol做容器(Colletion)类的元素， 能够起到同时降低空间复杂度和时间复杂度的效果。

因为元素域(range of element)可能无限，但元素的值域(the range of element content value)是有限的。或者说元素的个数可以很多，但它们的值很多是重复的。这样通过对象共享，可以降低内存消耗。

另一方面，Symbol#equals(Object)比String#equals(Object)快很多，至少快一倍，而且随着字符串内容长度的增加，Symbol#equals(Object)速度不变，而String#equals(Object)会成倍降低。附件中是我测试的代码。

其他可能

为什么不能通过重载和实现具体的容器类(AddressCompareList)，达到用==来比较对象元素的效果呢？因为这种方案无法保证另一个前提，即传入的相同对象共享地址。

 

建议

但是在上面给出的例子中，为了方便，Symbol以String对象为成员，其实是一种浪费。

以后的JDK可以新提供一个Symbol类。用Char数组为核心成员，按String的实现，把它作为常量String(the Sharing String cached in Constant Pool)来实现。

评论

1 楼 liugm1 2013-06-25  

学习下，一种好思路。不过没运行测试过，我觉得现代cpu的运算速度应该可以减少String与Symbol两种方式的速度差别吧。