两个 collections 的左外连接

Question

标题中的问题差不多。我正在寻找一种比通过 collections.

进行全面搜索更有效的算法

我有两个 collection：

List<Map<TypeId, Object> > col1;
List<Entity> col2;

哪里

public enum TypeId{
    PLAYER,
    PARTNER,
    PLATFORM,
    AMOUNT
}

和

public class Entity{
    private int player_id;
    private int platform_id
    private BigDecimal amount;

    //GET, SET
}

类型为List<Map<TypeId, Object> >的col1collection仅包含PLAYER, PARTNER, PLATFORMTypeIds。

我需要写一个方法：

public List<Map<TypeId, Object> > merge(List<Map<TypeId, Object> > col1, List<Entity> col2){
    //Impl
}

这将产生 List<Map<TypeId, Object> > 每个映射的条目 entry 包含额外的 key-value (AMOUNT, AMOUNT's value) 其中 AMOUNT's value 是 amount Entity 实例 e 的字段，如果 e.player_id = entry.get(PLAYER) && e.platform_id = entry.get(PLATFORM)，否则 null。

其实操作和

是一样的

col1 LEFT OUTER JOIN 
col2 ON e.player_id = entry.get(PLAYER) && e.platform_id = entry.get(PLATFORM)

样本：

col1:
[{PLATFORM: 1, PARTNER: 1, PLAYER: 1},
 {PLATFORM: 1, PARTNER: 3, PLAYER: 1},
 {PLATFORM: 2, PARTNER: 1, PLAYER: 2}
 {PLATFORM: 3, PARTNER: 4, PLAYER: 5}]

col2:
[Entity(platform_id = 1, player_id = 1, amount = 100),
Entity(platform_id = 2, player_id = 2, amount = 200),
Entity(platform_id = 3, player_id = 4, amount = 300)]

result:
[{PLATFORM: 1, PARTNER: 1, PLAYER: 1, AMOUNT: 100},
 {PLATFORM: 1, PARTNER: 3, PLAYER: 1, AMOUNT: 100},
 {PLATFORM: 2, PARTNER: 1, PLAYER: 2, AMOUNT: 200},
 {PLATFORM: 3, PARTNER: 4, PLAYER: 5, AMOUNT: null}]

Answer 1

更容易就地进行更改，修改 col1 列表而不是创建新的 List。这是 Java-8 解决方案：

public List<Map<TypeId, Object> > merge(List<Map<TypeId, Object> > col1, List<Entity> col2){
    col1.forEach(map -> map.put(TypeId.AMOUNT, 
        col2.stream()
            .filter(e -> e.player_id == (int)map.get(TypeId.PLAYER) && 
                         e.platform_id == (int)map.get(TypeId.PLATFORM))
            .findFirst().map(e -> e.amount).orElse(null)
        ));
    return col1;
}

我想在这种情况下，就地更改 col1 是令人满意的。请注意，即使您将结果存储到新列表中，如果您修改现有地图，它也将无用。因此，要使结果完全独立于 col1，您将必须复制所有地图。

另请注意，它不是很有效，因为它遍历 col2 的每个 col1 条目，因此复杂度大约为 col1.size()*col2.size()。在您的情况下，最好丢弃 Entity class 并创建一个仅存储 platformId 和 playerId 的新的（正确实施 equals 和 hashCode）并使用它作为地图键：

public static class PlatformAndPlayer {
    private final int playerId, platformId;

    public PlatformAndPlayer(int playerId, int platformId) {
        this.playerId = playerId;
        this.platformId = platformId;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + platformId;
        result = prime * result + playerId;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        PlatformAndPlayer other = (PlatformAndPlayer) obj;
        if (platformId != other.platformId)
            return false;
        if (playerId != other.playerId)
            return false;
        return true;
    }
}

这样您将得到 Map:

而不是 col2 列表

Map<PlatformAndPlayer, BigDecimal> col2 = new HashMap<>();
col2.put(new PlatformAndPlayer(1, 1), BigDecimal.valueOf(100));
col2.put(new PlatformAndPlayer(2, 2), BigDecimal.valueOf(200));
col2.put(new PlatformAndPlayer(3, 4), BigDecimal.valueOf(300));

现在您的任务可以轻松有效地解决（即使使用 Java 5）：

public static List<Map<TypeId, Object>> merge(
        List<Map<TypeId, Object>> col1,
        Map<PlatformAndPlayer, BigDecimal> col2) {
    for (Map<TypeId, Object> map : col1) {
        map.put(TypeId.AMOUNT, col2.get(new PlatformAndPlayer(
            (int) map.get(TypeId.PLAYER), (int) map.get(TypeId.PLATFORM))));
    }
    return col1;
}

Answer 2

Guava 库提供了非常适合此类转换的函数式习语。下面是一个使用 Guava 实现方法的示例，不需要更改方法签名：

public List<Map<TypeId, Object>> merge(List<Map<TypeId, Object>> col1,
        List<Entity> col2) {                

    // create a lookup table for getting the amounts
    // based on entities (entity keys)
    final Map<Entity, BigDecimal> entityLookupTable = Maps.toMap(col2,
             new Function<Entity, BigDecimal>() {
                 @Override
                 public BigDecimal apply(Entity entity) {
                     return entity.getAmount();
                 }
    });

    // transform the col1 list using a transform function 
    // that adds the AMOUNT fetched from the lookup table to each entry map
    return Lists.transform(col1, new Function<Map<TypeId, Object>,
                                             Map<TypeId, Object>>() {

        @Override
        public Map<TypeId, Object> apply(Map<TypeId, Object> typeToValueMap) {

                    Entity keyWrapper = new Entity(
                            new EntityKey(
                                (Integer) typeToValueMap.get(TypeId.PLAYER),
                                (Integer) typeToValueMap.get(TypeId.PLATFORM)),
                            null);

                    typeToValueMap.put(TypeId.AMOUNT,
                            entityLookupTable.get(keyWrapper));

                    return typeToValueMap;
                }
            });
}

但是，需要创建一个 EntityKey class 来标识一个实体（类似于数据库中的主键）。此 class 然后可用于在 Entity 中实现 equals（和 hashCode），从而能够在查找映射中存储实体。

public class EntityKey {

    private int player_id;
    private int platform_id;

    public EntityKey(int player_id, int platform_id) {
        this.player_id = player_id;
        this.platform_id = platform_id;
    }

    /* Generated by Eclipse */
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + platform_id;
        result = prime * result + player_id;
        return result;
    }

    /* Generated by Eclipse */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        EntityKey other = (EntityKey) obj;
        if (platform_id != other.platform_id)
            return false;
        if (player_id != other.player_id)
            return false;
        return true;
    }        
}

public class Entity {

    private EntityKey key;
    private BigDecimal amount;

    public Entity(EntityKey key, BigDecimal amount) {
        this.key = key;
        this.amount = amount;
    }      

    /* Generated by Eclipse */
    /* Simply delegates to EntityKey */
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((key == null) ? 0 : key.hashCode());
        return result;
    }

    /* Generated by Eclipse */
    /* Simply delegates to EntityKey */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Entity other = (Entity) obj;
        if (key == null) {
            if (other.key != null)
                return false;
        } else if (!key.equals(other.key))
            return false;
        return true;
    }

    /**
     * @return the amount
     */
    public BigDecimal getAmount() {
        return amount;
    }
}

两个 collections 的左外连接

LEFT OUTER JOIN of two collections

java

collections