Java代码优化求助：用户ID分配逻辑运行超时问题

Hey there! Let's fix that timeout issue with your ID allocation system. The most common culprit behind slow performance here is naive linear scans to find the next available ID—this gets really expensive once you have thousands of operations.

The optimal solution here uses a Union-Find (Disjoint Set Union, DSU) data structure, which gives us nearly constant-time operations (thanks to path compression) for both allocation and release. Here's how it works:

• We use a HashMap to track the parent of each ID. The parent of an ID points to the next available ID. If an ID is available, its parent is itself.
• When allocating an ID: We find the root of the desired ID (this root is the smallest available ID ≥ desired ID). We then mark this ID as used by updating its parent to point to the next available ID (root + 1).
• When releasing an ID: We simply reset its parent to itself, marking it as available. The path compression in the find operation will automatically handle reusing this ID in future allocations.

Here's the optimized Java code:

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

public class IdAllocator {
    // parent[id] = next available ID starting from 'id'
    private final Map<Integer, Integer> parent = new HashMap<>();

    // Find the root available ID (with path compression)
    private int find(int id) {
        if (!parent.containsKey(id)) {
            // If the ID hasn't been touched before, it's available
            parent.put(id, id);
            return id;
        }
        // Path compression: flatten the structure to speed up future queries
        if (parent.get(id) != id) {
            parent.put(id, find(parent.get(id)));
        }
        return parent.get(id);
    }

    // Allocate the smallest available ID ≥ desiredId
    public int allocate(int desiredId) {
        int availableId = find(desiredId);
        // Mark this ID as used: point it to the next available ID
        parent.put(availableId, find(availableId + 1));
        return availableId;
    }

    // Release an ID to make it available again
    public void release(int id) {
        // Reset the parent to itself—this marks the ID as available
        parent.put(id, id);
    }
}

Why this works (and is fast): #

• Path compression in the find method ensures that every subsequent query for an ID will jump directly to the nearest available ID, avoiding redundant checks.
• Both allocate and release operations run in O(α(n)) time, where α is the inverse Ackermann function—this is effectively constant time for any practical number of operations (way faster than linear scans).

Alternative: TreeSet-based approach #

If you prefer a more straightforward (though slightly less efficient) solution, you can use a TreeSet to track used IDs. This gives O(log n) time for operations:

import java.util.TreeSet;

public class IdAllocator {
    private final TreeSet<Integer> usedIds = new TreeSet<>();

    public int allocate(int desiredId) {
        if (!usedIds.contains(desiredId)) {
            usedIds.add(desiredId);
            return desiredId;
        }
        // Find the first gap after desiredId
        Integer nextUsed = usedIds.higher(desiredId);
        int newId;
        if (nextUsed == null) {
            newId = desiredId + 1;
        } else {
            newId = desiredId + 1;
            // If desiredId+1 is not occupied, use it
            if (newId >= nextUsed) {
                newId = nextUsed + 1;
            }
        }
        usedIds.add(newId);
        return newId;
    }

    public void release(int id) {
        usedIds.remove(id);
    }
}

The TreeSet approach is easier to grok but can have worse worst-case performance (like when all IDs are consecutive and you need to allocate a new one beyond the current max). The Union-Find approach is hands-down the best choice for high-throughput scenarios where you need to stick within that 1-second execution limit.

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