Java面试任务：实现O(log(n))复杂度的线程安全元素存储与查询

Hey there! Let's break down how to solve this Java interview problem perfectly, hitting all the requirements: thread safety, O(log n) time for all methods, and support for dynamic updateTime changes.

Core Problem Analysis #

We need three key operations:

• add(Element): Insert or update an element by unique id
• getElement(id): Retrieve an element by its id
• getLastUpdatedElements(): Fetch all elements updated in the last minute

The main challenge is making all these operations O(log n) while keeping the store thread-safe, especially handling dynamic updateTime changes which break naive sorted set implementations.

Key Insight: Dual Sorted Structures #

Your initial thought of using two sorted structures is spot-on! We just need to ensure atomicity across both structures to avoid inconsistencies. Here's the plan:

1. A ConcurrentSkipListMap<Long, Element>: Keyed by id for O(log n) lookups and inserts.
2. A ConcurrentSkipListSet<Element>: Sorted by updateTime for O(log n) range queries (to get recent elements).
3. A Reentrant Lock: To guard all modification operations (add, update updateTime) and ensure atomicity across both structures.

Implementation Code #

Step 1: Define the Element Class #

We make id immutable (since it's a unique key) and restrict direct modification of updateTime to our store class to prevent inconsistent state in the sorted set.

import java.util.Objects;

class Element {
    private final long id;
    private String name;
    private volatile long updateTime; // Volatile ensures cross-thread visibility

    public Element(long id, String name, long updateTime) {
        this.id = id;
        this.name = name;
        this.updateTime = updateTime;
    }

    // Getters
    public long getId() { return id; }
    public String getName() { return name; }
    public long getUpdateTime() { return updateTime; }

    // Setters (name can be modified directly; updateTime is controlled by the store)
    public void setName(String name) { this.name = name; }
    void setUpdateTime(long updateTime) { this.updateTime = updateTime; }

    // Equals/hashCode based on id (since id is unique)
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Element element = (Element) o;
        return id == element.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

Step 2: Implement the Thread-Safe Store #

import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ConcurrentSkipListSet;
import java.util.concurrent.locks.ReentrantLock;

public class ElementStore {
    // Map for O(log n) lookups by id
    private final ConcurrentSkipListMap<Long, Element> idIndexedStore = new ConcurrentSkipListMap<>();
    // Set sorted by updateTime for O(log n) range queries
    private final ConcurrentSkipListSet<Element> timeSortedStore;
    // Lock to ensure atomicity across modification operations
    private final ReentrantLock modificationLock = new ReentrantLock();

    public ElementStore() {
        // Sort elements by updateTime in ascending order
        timeSortedStore = new ConcurrentSkipListSet<>(Comparator.comparingLong(Element::getUpdateTime));
    }

    /**
     * Adds or updates an element. O(log n) time.
     */
    public void add(Element element) {
        modificationLock.lock();
        try {
            // Replace existing element if id already exists
            Element oldElement = idIndexedStore.put(element.getId(), element);
            // Remove old element from time-sorted set if it existed
            if (oldElement != null) {
                timeSortedStore.remove(oldElement);
            }
            // Add new/updated element to time-sorted set
            timeSortedStore.add(element);
        } finally {
            modificationLock.unlock();
        }
    }

    /**
     * Retrieves an element by id. O(log n) time.
     */
    public Element getElement(long id) {
        // ConcurrentSkipListMap's get is thread-safe; no lock needed for read-only operation
        return idIndexedStore.get(id);
    }

    /**
     * Returns all elements updated in the last minute. O(log n + k) time, where k is the number of matching elements.
     * The core lookup to find the time boundary is O(log n), which meets the problem's requirement.
     */
    public Collection<Element> getLastUpdatedElements() {
        long oneMinuteAgo = System.currentTimeMillis() - 60 * 1000;
        // Dummy element to find the boundary in the sorted set
        Element timeBoundary = new Element(-1, "", oneMinuteAgo);
        // Get all elements with updateTime >= oneMinuteAgo (O(log n) time)
        NavigableSet<Element> recentElements = timeSortedStore.tailSet(timeBoundary, true);
        // Return an unmodifiable copy to prevent external modifications breaking our store
        return Collections.unmodifiableCollection(new ArrayList<>(recentElements));
    }

    /**
     * Updates the updateTime of an existing element. O(log n) time.
     * Returns true if the element was found and updated, false otherwise.
     */
    public boolean updateElementUpdateTime(long id, long newUpdateTime) {
        modificationLock.lock();
        try {
            Element element = idIndexedStore.get(id);
            if (element == null) {
                return false;
            }
            // Remove element from time-sorted set (using old updateTime)
            timeSortedStore.remove(element);
            // Update the time
            element.setUpdateTime(newUpdateTime);
            // Re-add to time-sorted set (using new updateTime)
            timeSortedStore.add(element);
            return true;
        } finally {
            modificationLock.unlock();
        }
    }
}

Why This Works #

1. Thread Safety:

   • The ReentrantLock ensures that all modification operations (add, update updateTime) are atomic, preventing inconsistent state between the two structures.
   • ConcurrentSkipListMap and ConcurrentSkipListSet provide thread-safe read operations without blocking, so multiple threads can read concurrently.

2. Time Complexity:

   • add(Element): O(log n) (both put on the map and add/remove on the set are O(log n)).
   • getElement(id): O(log n) (direct lookup in the skip list map).
   • getLastUpdatedElements(): The core boundary lookup is O(log n); iterating over matching elements is O(k) (k is the number of recent elements), which is acceptable since the problem's upper bound refers to the operation's core logic.

3. Dynamic updateTime Handling:

   • We never let external code modify updateTime directly. Instead, we use updateElementUpdateTime to first remove the element from the time-sorted set, update the time, then re-add it. This ensures the set's sorting stays correct.

Key Notes #

• Volatile updateTime: Ensures that when we update the time, all threads see the latest value immediately.
• Unmodifiable Return Collection: Prevents external code from modifying elements in the result, which could break the sorted set's state.
• Lock Scope: The lock is only held during modification operations, which are fast (O(log n)), so we avoid turning the application single-threaded.

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