LeetCode食物评分系统问题：HashMap修改未同步至TreeSet

我实现了LeetCode的食物评分系统，用HashMap（tFood）存储Food对象，另一个HashMap（tRate）存储菜系到Food对象TreeSet的映射。

初始化后系统包含（"sushi", "japanese", 8），调用changeRating()把sushi评分改成16后，updateHighestRated方法会重复把该对象添加到tRate的TreeSet里。我猜测TreeSet里还保留着该对象旧状态（评分8）的记录，哪怕对象本身已经被改成16了。测试时发现，再次调用changeRating("sushi", 16)时，TreeSet就不会重复添加了。

代码实现 #

class Food{
    public String name;
    public String cuisine;
    public int rating;

    public Food(String name, String cuisine, int rating){
        this.name = name;
        this.cuisine = cuisine;
        this.rating = rating;
    }

    void setRating(int rating){
        this.rating = rating;
    }
    int getRating(){
        return this.rating;
    }
    String getName(){
        return this.name;
    }
    String getCuisine(){
        return this.cuisine;
    }

    public String toString(){
        return this.cuisine + " " + this.name + " " + this.rating;
    }
}

public class FoodRatings {

    HashMap<String, Food> tFood; //name -> Food
    HashMap<String, TreeSet<Food>> tRate; //cuisine -> TreeSet<Food>

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {

        tFood = new HashMap<String, Food>();
        tRate = new HashMap<String, TreeSet<Food>>();

        for(int i = 0; i < foods.length; i++){

            Food obj = new Food(foods[i], cuisines[i], ratings[i]);
            tFood.put(foods[i], obj);

            updateHighestRated(obj);
        }
    }
    public void changeRating(String name, int newRating) {
        Food obj = tFood.get(name);
        obj.setRating(newRating);

        updateHighestRated(obj);
    }

    public void updateHighestRated(Food obj){
        String cuisine = obj.cuisine;
        TreeSet<Food> tSet = tRate.get(cuisine);
        if(tSet == null){

            Comparator<Food> comp = Comparator.comparing(Food::getRating)
                    .reversed()
                    .thenComparing(Food::getName);
            tSet = new TreeSet<Food>(comp);
            tRate.put(cuisine, tSet);
        }
        boolean b = tSet.add(obj);                  //<------- 问题所在!
        if(b)
            System.out.println("added " + obj);
    }

    public String highestRated(String cuisine) {
        return tRate.get(cuisine).first().getName();
    }

    public static void main(String[] args) {
        String[] foods = {"kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"};
        String[] cuisines = {"korean", "japanese", "japanese", "greek", "japanese", "korean"};
        int[] ratings = {9, 12, 8, 15, 14, 7};

        FoodRatings foodRatings = new FoodRatings(foods, cuisines, ratings);//("sushi", "japanese", 8)

        foodRatings.changeRating("sushi", 16);  // 这里会重复添加
        foodRatings.changeRating("sushi", 16);
        System.out.println(foodRatings.highestRated("japanese"));

        foodRatings.changeRating("ramen", 16);
        System.out.println(foodRatings.highestRated("japanese"));
    }
}

问题原因 #

核心问题在于TreeSet的底层机制：

• TreeSet靠元素的比较结果维护有序性和唯一性，它不会主动监听元素内部属性的变化，仅在添加/删除元素时做一次比较判断。
• 当你修改Food对象的rating后，该对象在TreeSet中的排序位置已经失效，但TreeSet对此毫无察觉。此时调用add(obj)，TreeSet会用当前的rating=16去和集合里的元素比较——原来的元素是基于rating=8排序的，比较结果会认为这是一个新元素，所以会重复添加。
• 第二次调用changeRating("sushi",16)时，对象的rating没有变化，TreeSet用当前属性比较后，发现集合里已经存在匹配的元素，因此不会重复添加。

另外，你的Food类没有重写equals()和hashCode()，不过TreeSet主要依赖你定义的Comparator判断元素是否重复，这里Comparator是按rating倒序+name正序，所以rating变化后，比较结果和旧记录不一致，TreeSet就会判定为新元素。

修复方案 #

修改评分时，必须先把旧状态的Food对象从对应菜系的TreeSet中移除，再添加修改后的对象：

public void changeRating(String name, int newRating) {
    Food obj = tFood.get(name);
    // 先移除旧状态的对象
    tRate.get(obj.cuisine).remove(obj);
    obj.setRating(newRating);
    // 再添加更新后的对象
    updateHighestRated(obj);
}

这样就能保证TreeSet中始终只有该Food对象的最新状态，既不会出现重复元素，也能维持正确的排序逻辑。

内容的提问来源于stack exchange，提问作者Abe