基于Google Guava实现Java Symbol Table的效率与值更新问题

Great question! Let's break down your concerns about using Google Guava's Multimap for a symbol table (essentially a multi-value hash table) and how to update specific values in it.

1. Is Guava Multimap efficient for frequent value updates? #

First off, Guava's Multimap implementations (like HashMultimap and ArrayListMultimap) are built on top of optimized standard Java collections, so they’re well-suited for most symbol table use cases. Here’s the breakdown on efficiency:

• Underlying structure: A Multimap is essentially a Map<K, Collection<V>>. When updating a value, you first look up the collection tied to the key (O(1) average case for hash-based implementations), then modify that collection.
• Pick the right implementation:
  • Use HashMultimap if you need fast lookups/removals of individual values: it stores values in a HashSet, so checking existence or removing a value takes O(1) average time.
  • Use ArrayListMultimap if value order matters: it uses an ArrayList, so removing a specific value takes O(n) time (since you have to scan the list), but updating by index is O(1).
• Real-world performance: For most symbol table scenarios—even with frequent updates—Guava’s Multimaps are more than efficient enough. Unless you’re dealing with extreme high-frequency updates in a performance-critical system, you won’t need to roll your own implementation. Guava’s code is battle-tested and optimized for reliability and speed.

2. How to update a specific value (e.g., change "Aeroplane" to "Orange" for key "abc")? #

The approach depends on whether you want to update by value or by position. Here are two common scenarios:

Scenario 1: Update by value (replace "Aeroplane" with "Orange") #

Use HashMultimap for fast value lookups:

import com.google.common.collect.HashMultimap;
import com.google.common.collect.Multimap;

public class SymbolTableUpdateExample {
    public static void main(String[] args) {
        Multimap<String, String> symbolTable = HashMultimap.create();
        symbolTable.put("abc", "Apple");
        symbolTable.put("abc", "Aeroplane");
        
        // Replace Aeroplane with Orange
        if (symbolTable.containsEntry("abc", "Aeroplane")) {
            symbolTable.remove("abc", "Aeroplane");
            symbolTable.put("abc", "Orange");
        }
        
        // Output: [Apple, Orange]
        System.out.println(symbolTable.get("abc"));
    }
}

Scenario 2: Update by position (replace the second value in the list) #

If you need to maintain order and update by index, use ArrayListMultimap:

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.ListMultimap;
import java.util.List;

public class OrderedSymbolTableUpdateExample {
    public static void main(String[] args) {
        ListMultimap<String, String> symbolTable = ArrayListMultimap.create();
        symbolTable.put("abc", "Apple");
        symbolTable.put("abc", "Aeroplane");
        
        // Get the list of values for key "abc"
        List<String> values = symbolTable.get("abc");
        // Find the index of "Aeroplane" (or use index directly if you know it)
        int targetIndex = values.indexOf("Aeroplane");
        
        if (targetIndex != -1) {
            values.set(targetIndex, "Orange");
        }
        
        // Output: [Apple, Orange]
        System.out.println(symbolTable.get("abc"));
    }
}

Key notes: #

• Always check if the entry exists before removing it to avoid unnecessary operations.
• For concurrent environments, wrap your Multimap with Multimaps.synchronizedMultimap() or use ConcurrentHashMultimap from Guava’s concurrent package.

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