MultiKeyedMap方案的实现

方案背景

所谓“MultiKeyedMap”是指允许多个关键字经过组合映射到一个对象的集合类。

比方说，我们有一个数据表，大概的结构如下：

ID	姓	名	性别	出生日期
1	王	小毛	男	'1973-05-18'
2	沈	佩佩	女	'1976-06-24'

数据结构大体如下：

class Person // 个人信息
{
    private final Integer id;
    private String lastName;
    private String firstName;
    private Gender gender;
    private Date birthDate;
}

enum Gender // 性别枚举
{
    MALE, FEMALE;
}

OK，这里，如果ID是关键字的话，可以做出下面的映射：

import static Gender;
void init()
{
    Person wang = new Person(1, "王", "小毛", MALE, Date.parse('1973-05-18'));
    Person shen = new Person(2, "沈", "佩佩", FEMALE, Date.parse('1976-06-24'));
    // ...
    Map hrInfo = new TreeMap(); // TreeMap比较节省空间
    hrInfo.put(wang.getId(), wang);
    hrInfo.put(shen.getId(), shen);
    // ...
}

Person checkHrInfo(int id)
{
    return hrInfo.get(id);
}

代码所见，这里你能做的唯一操作就是根据ID号查找人员信息。不过如果你要做特殊条件的查找，比方说：男性的？或者，姓王的？或者姓王的男性？对不起，此功能暂不提供。

假如是MultiKeyedMap的话，那么ID，姓，名，性别，生日都可以作为单独或任意组合的查询的条件从Map里面拣出所需对象（集合）。

这么说，感觉有点儿像我之前提交过的Object数组到泛型数组转换的伪解决方案里面的场景，都是做数据查询的例子。

技术难点

MultiKeyedMap的主要技术难点在于，每个Key都是独立的信息，也就是说，如果压缩了Key信息的存储空间，就必须使用更多的时间做计算；如果想要更快的获得结果，就必须提供给Key信息更多的空间。

技术方案

以下给出两套技术方案：

第一套：时间换空间

1. 把关键字组成一个对象，实现hashcode方法。然后用这个对象作为key保存映射关系。
2. 如果查找若干（非全部）关键字组合条件的信息，则首先要把缺失关键字的所有可能都找出来，形成完整关键字（的hashcode），查找对象集合。

其中，第二条内容看上去很可怕，似乎是n*n*n*...的时间，但可以使用约束条件，使组合的数量大大减少。具体约束条件由案例情况决定。这里略过。

第二套：空间换时间

1. 按照key的类型数量建立映射表。比方说，ID | 姓 | 性别 | 生日，就建立4个映射表。然后每个映射表以key为键，保留key对应的所有对象的set为值。
2. 查找任意组合key的值时候，比方说，null | "王" | MALE | null，取出非null的key，找到对应的set，然后，取出另一个非null的key，找到对应set，两个set做交集。

同样，第二条也有一些优化的内容以及特殊情况（比如说，全是null）要处理。不过整体看上去感觉比第一套方案要好。

其它

说句实话，第二套方案的实质不是MultiKeyedMap，其思想应该算是MultiMap，也就是一个key映射多个value。

最初我只想到了第一套方案。不过觉得性能上似乎不是很好。之后也参详了Apache Commons Collections库里面的MultiKeyMap，不过这个类更多的花头似乎是在装璜模式上，多个key必须齐全的情况下才能找到对象，不能做到凭1..n-1个key寻找对象集合。

后来学习了Google的Collections里面的MultiMap，看到了“key <-1 = n-> value”的想法，于是转变思路，发现这也是一个方案。就写了这篇文章纪念一下。

实现代码

废话少说，以下是第二套方案的demo实现。只是原型，不保证bug-free。有需要的自行取用。

public interface MultiKeyedMap
{
    void put(Object[] keys, Object value);

    MultiKeyedEntry[] get(Object[] keys);

    boolean containsKey(int keyIndex, Object key);
}

public class MultiKeyedEntry implements Comparable
{
    private final Object[] keys;
    private Object value;

    MultiKeyedEntry(Object[] keys)
    {
        this.keys = keys;
    }

    public Object[] getKeys()
    {
        return this.keys;
    }

    public boolean equals(Object o)
    {
        if (o instanceof MultiKeyedEntry) {
            MultiKeyedEntry mk = (MultiKeyedEntry) o;
            if (mk.keys.length != keys.length) {
                return false;
            }
            for (int i = 0; i < keys.length; i++) {
                Object k = mk.keys[i];
                Object _k = keys[i];
                if (k != null && _k != null && !k.equals(_k)) {
                    return false;
                }
            }
            return true;
        }
        return false;
    }

    /*
     * (non-Javadoc)
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    public int compareTo(Object o)
    {
        MultiKeyedEntry e = (MultiKeyedEntry) o;
        for (int i = 0; i < keys.length; i++) {
            int n = ((Comparable) keys[i]).compareTo(e.keys[i]);
            if (n != 0) {
                return n;
            }
        }
        return 0;
    }
    
    public String toString()
    {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < keys.length; i++) {
            sb.append(", ").append(keys[i]);
        }
        sb.append(": ").append(value);
        return sb.substring(2);
    }

    public void setValue(Object value)
    {
        this.value = value;
    }

    public Object getValue()
    {
        return value;
    }
}

public class MultiKeyedMapImpl implements MultiKeyedMap
{
    private final Map[] maps;

    MultiKeyedMapImpl(int keyCount)
    {
        if (keyCount < 1) {
            throw new IllegalArgumentException();
        }
        maps = new Map[keyCount];
        for (int i = 0; i < keyCount; i++) {
            maps[i] = new HashMap();
        }
    }

    /*
     * (non-Javadoc)
     * @see multimap.MultiKeyedMap#containsKey(int, java.lang.Object)
     */
    public boolean containsKey(int keyIndex, Object key)
    {
        return keyIndex >= maps.length ? false : maps[keyIndex].containsKey(key);
    }

    /*
     * (non-Javadoc)
     * @see multimap.MultiKeyedMap#get(java.lang.Object[])
     */
    public MultiKeyedEntry[] get(Object[] keys)
    {
        validateKeyCount(keys);
        Collection c = null;
        for (int i = 0; i < maps.length; i++)
        {
            Object key = keys[i];
            if (key != null) {
                Set valueSet = (Set) maps[i].get(key);
                if (valueSet == null) {
                    return new MultiKeyedEntry[0];
                }
                if (c == null) {
                    c = new LinkedHashSet(valueSet);
                } else {
                    c.retainAll(valueSet);
                    if (c.size() == 0) {
                        return new MultiKeyedEntry[0];
                    }
                }
            }
        }
        if (c == null) {
            c = new LinkedHashSet();
            Collection v = maps[0].values();
            
            for (Iterator it = v.iterator(); it.hasNext();) {
                c.addAll((Set)it.next());
            }
        }
        return (MultiKeyedEntry[]) c.toArray(new MultiKeyedEntry[c.size()]);
    }

    /*
     * (non-Javadoc)
     * @see multimap.MultiKeyedMap#put(java.lang.Object[], java.lang.Object)
     */
    public void put(Object[] keys, Object value)
    {
        validateKeyCount(keys);
        MultiKeyedEntry entry = new MultiKeyedEntry(keys);
        entry.setValue(value);
        for (int i = 0; i < maps.length; i++)
        {
            if (keys[i] == null) {
                throw new IllegalArgumentException();
            }
            Set set = (Set) maps[i].get(keys[i]);
            if (set == null) {
                set = new TreeSet();
                maps[i].put(keys[i], set);
            }
            set.add(entry);
        }
    }

    private void validateKeyCount(Object[] keys)
    {
        if (keys.length != maps.length) {
            throw new IllegalArgumentException();
        }
    }
}

public class TripleKeyedMap extends MultiKeyedMapImpl
{
    TripleKeyedMap()
    {
        super(3);
    }

    public void put(Object key1, Object key2, Object key3, Object value)
    {
        put(new Object[] { key1, key2, key3 }, value);
    }

    public MultiKeyedEntry[] get(Object key1, Object key2, Object key3)
    {
        return get(new Object[] { key1, key2, key3 });
    }
}

public class Main
{
    private static final Person
            wang = new Person(1, "王", "小毛", new Date(1973, 4, 18), Gender.MALE),
            shen = new Person(2, "沈", "佩佩", new Date(1976, 5, 24), Gender.FEMALE),
            lu = new Person(3, "陆", "小凤", new Date(898, 10, 7), Gender.MALE);

    public static void main(String[] args)
    {
        TripleKeyedMap map = new TripleKeyedMap();
        map.put(wang.getLastName(), wang.getBirthDate(), wang.getGender(), wang);
        map.put(shen.getLastName(), shen.getBirthDate(), shen.getGender(), shen);
        map.put(lu.getLastName(), lu.getBirthDate(), lu.getGender(), lu);
        MultiKeyedEntry[] entries = map.get(null, null, Gender.MALE);
        for (int i = 0; i < entries.length; i++) {
            System.out.println(entries[i]);
        }
    }
}

class Gender extends Enum
{
    private Gender(String value)
    {
        super(value);
    }

    public static final Gender
        MALE = new Gender("MALE"), FEMALE = new Gender("FEMALE");
}

class Person
{
    private final int id;
    private final String lastName;
    private final String firstName;
    private final Date birthDate;
    private final Gender gender;

    public Person(int id, String lastName, String firstName, Date birthDate, Gender gender)
    {
        this.id = id;
        this.lastName = lastName;
        this.firstName = firstName;
        this.birthDate = birthDate;
        this.gender = gender;
    }

    public int getId()
    {
        return id;
    }

    public String getLastName()
    {
        return lastName;
    }

    public String getFullName()
    {
        return lastName + ", " + firstName;
    }

    public Date getBirthDate()
    {
        return birthDate;
    }

    public Gender getGender()
    {
        return gender;
    }
}

abstract public class Enum implements Comparable
{ // Collection.retainAll方法要求对象必须扩展了Comparable接口
    private final String value;

    public Enum(String value)
    {
        this.value = value;
    }

    public boolean equals(Object o)
    {
        return compareTo(o) == 0;
    }

    public String toString()
    {
        return value;
    }

    public int compareTo(Object o)
    {
        if (this.getClass().equals(o.getClass())) {
            Enum e = (Enum) o;
            return value == null ? (e.value == null ? 0 : -1) : value.compareTo(e.value);
        }
        return -1;
    }
}