java - 为特定键分配和取消分配数字

Question

我正在处理以下面试问题:

有一个 Allocator 类，其中我有两个方法 allocate 和 deallocate

class Allocator {
    int allocate(String key);
    boolean deallocate(String key, int number); 
}

• allocate 方法会将以 0 开头的数字分配给特定的键。如果我们再次分配相同的 key ，则增加最后使用的数字。
• deallocate 方法将为该特定键解除分配该数字。在为特定 key 释放该号码后，如果我们再次分配相同的 key ，那么我们应该使用当前 key 不可用的 key 。

例如:

 allocate("foo") -> 0
 allocate("foo") -> 1
 allocate("bar") -> 0
 allocate("foo") -> 2
 allocate("foo") -> 3
 allocate("foo") -> 4

 deallocate("foo", 2)

 allocate("foo") -> 2
 allocate("foo") -> 5

下面是我得到的，它可以工作，但我认为时间复杂度可能不适合分配和解除分配。有没有更好、更有效的方法来做到这一点？

public class Allocator {
  private static final Map<String, List<Integer>> cmap = new HashMap<>();
  private static final Map<String, List<Integer>> umap = new HashMap<>();

  public static void main(String[] args) {
    Allocator na = new Allocator();
    System.out.println(na.allocate("foo"));
    System.out.println(na.allocate("foo"));
    System.out.println(na.allocate("bar"));
    System.out.println(na.allocate("foo"));
    System.out.println(na.allocate("foo"));
    System.out.println(na.allocate("foo"));

    System.out.println(na.deallocate("foo", 2));
    System.out.println(na.allocate("foo"));
    System.out.println(na.allocate("foo"));
  }

  public int allocate(String key) {
    if (umap.containsKey(key)) {
      List<Integer> l = umap.get(key);
      if (!l.isEmpty()) {
        int val = l.remove(0);
        List<Integer> currentList = cmap.get(key);
        if (currentList == null) {
          currentList = new ArrayList<>();
          currentList.add(val);
          cmap.put(key, currentList);
          return val;
        }
        currentList.add(val);
        Collections.sort(currentList);
        cmap.put(key, currentList);
        return val;
      }
    }
    if (!cmap.containsKey(key)) {
      List<Integer> list = new ArrayList<>();
      list.add(0);
      cmap.put(key, list);
      return 0;
    }
    List<Integer> l = cmap.get(key);
    Collections.sort(l);
    int value = l.get(l.size() - 1) + 1;
    cmap.get(key).add(value);
    return value;
  }

  public boolean deallocate(String key, Integer number) {
    if (!cmap.containsKey(key)) {
      return false;
    }
    List<Integer> l = cmap.get(key);
    boolean o = l.remove(number);
    if (!o) {
      return false;
    }
    if (!umap.containsKey(key)) {
      List<Integer> list = new ArrayList<>();
      list.add(number);
      umap.put(key, list);
      return true;
    }
    umap.get(key).add(number);
    return true;
  }
}

Answer 1

更好的方法是存储下一个数字和每个键的释放列表:

public class Allocator {
    private final Map<String,Value> values = new HashMap<>();

    private class Value {
        private int nextValue = 0;
        private List<Integer> deallocatedValues = new ArrayList<>();

        public int allocate() {
            if (deallocatedValues.isEmpty()) {
                return nextValue++;
            else
                return deallocatedValues.remove();
        }

        public void deallocate(int value) {
            assert value >= 0 && value < nextValue;
            assert !deallocatedValues.contains(value);
            deallocatedValues.add(value);
        }
    }

    public int allocate(String key) {
        return values.computeIfAbsent(key, k -> new Value()).allocate();
    }

    public void deallocate(String key, int value) {
        assert values.containsKey(key);
        values.get(key).deallocate(value);
    }
}