java—用时间概念实现Map

wko9yo5t 于 2021-07-14 发布在 Java

关注(0)|答案(1)|浏览(339)

我最近被要求用以下两种方法实现数据结构： set(key, value, time) ：在指定时间将键设置为值。 get(key, time) ：获取键在指定时间或更早时间的值。
如果我们在某个特定的时间设置一个键，它将永远保持该值，或者直到它在以后的时间被设置为止。

示例

例1

d.set(1, 1, 0) // set key 1 to value 1 at time 0
d.set(1, 2, 2) // set key 1 to value 2 at time 2
d.get(1, 1) // get key 1 at time 1 should be 1
d.get(1, 3) // get key 1 at time 3 should be 2

例2

d.set(1, 1, 5) // set key 1 to value 1 at time 5
d.get(1, 0) // get key 1 at time 0 should be null
d.get(1, 10) // get key 1 at time 10 should be 1

例3

d.set(1, 1, 0) // set key 1 to value 1 at time 0
d.set(1, 2, 0) // set key 1 to value 2 at time 0
d.get(1, 0) // get key 1 at time 0 should be 2

Java performance Dictionary data-structures time-complexity

来源：https://stackoverflow.com/questions/67168299/implementing-a-map-with-the-notion-of-time

1条答案

按热度按时间

bcs8qyzn1#

以下是我的实现：

import java.util.HashMap;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

/**
 * An Implementation a Map with the notion of Time.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 * @param <T> the type of time tracked by this map.
 *            T MUST implement {@link Comparable} to have a notion of comparing times.
 * @author Hari Krishnan
 * @see Map
 * @see NavigableMap
 */
public class TimedMap<K, V, T extends Comparable<T>> {

    private final Map<K, NavigableMap<T, V>> map = new HashMap<>();

    /**
     * Associates the specified value with the specified key at the specified time in this map.
     * If the map previously contained a mapping for the key at this time,
     * the old value is replaced by the specified value.
     *
     * @param key   key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @param time  time at which said association should occur
     */
    public void set(K key, V value, T time) {
        if (!map.containsKey(key))
            map.put(key, new TreeMap<>());
        map.get(key).put(time, value);
    }

    /**
     * Returns the value to which the specified key is mapped at the specified time or earlier,
     * or {@code null} if this map contains no mapping for the key at the specified time or earlier.
     *
     * @param key  the key whose associated value is to be returned
     * @param time the time(or earlier) at which the values associated with the key is to be returned.
     * @return The value to which the specified key is mapped at the specified time or earlier, or
     * {@code null} if this map contains no mapping for the key at the specified time or earlier.
     */
    public V get(K key, T time) {
        try {
            return map.get(key).floorEntry(time).getValue();
        } catch (NullPointerException ex) {
            return null;
        }
    }

}

欢迎改进和建议！

赞(0）回复(0）举报 2021-07-14

我来回答

java—用时间概念实现Map

示例

1条答案

相关问题

热门标签

最新问答