在O(1)中执行set()， get()， setAll()的数据结构

Question

我试图写一个数据结构，能够设置所有的值在0 (1).

我的代码:

public class myData {
boolean setAllStatus = false;
HashMap<Integer, Integer> hasMap = new HashMap<>();
int setAllValue = 0;
int count = 0;
public void set(int key, int value) {
hasMap.put(key, value);
}
public int get(int key) {
if (setAllStatus) {
if (hasMap.get(key) != null) {
if (count == hasMap.size()) {
return setAllValue;
} else {
// do something
}
} else {
throw new NullPointerException();
}
} else {
if (hasMap.get(key) == null) {
throw new NullPointerException();
} else {
return hasMap.get(key);
}
}
}
public void setAll(int value) {
setAllStatus = true;
setAllValue = value;
count = hasMap.size();
}
public static void main(String[] args) {
myData m = new myData();
m.set(1, 4);
m.set(4, 5);
System.out.println(m.get(4)); // 5
m.setAll(6);
System.out.println(m.get(4)); // 6
m.set(8, 7);
System.out.println(m.get(8)); // 7
}
}

当我第一次设置变量，然后将所有值设置为一个特定的变量，它工作，但是当我试图在设置所有变量后放入一个新变量时，我有点困惑。

我可以用什么样的解决方案使它工作?

Answer 1

如果你想增强你对数据结构的知识，我建议你从头开始实现你自己的哈希表数据结构版本(定义一个桶数组，学习如何在桶中存储元素，如何解决冲突等等…)，而不是装饰HashMap。

你当前的代码是非常做作的:

• 就其本质而言，get()除了检索与键相关的值之外不应该做任何事情，因为这是该方法的唯一职责(请查看HashMap类中get()的实现)。熟悉单一责任原则
• 当给定的键不在映射中时抛出异常的想法很奇怪。NullPointerException不是描述这种情况的正确异常类型，NoSuchElementException更直观。
• 你可能也有兴趣了解"编程到接口"是什么意思?

主要的问题是，这是因为你选错了起点(参见最开始的建议)，从最简单的开始学习更多的数据结构，如动态数组，尝试从头实现它们，并逐渐学习更多关于类设计和语言特性的知识。

时间复杂度。关于时间复杂度，因为你的类修饰了一个HashMap方法，set()和get()将在一个常数时间内执行O(1).

如果您需要更改所有在HashMap中，这只能在线性时间内完成O(n)． 假设所有现有的值都由不同的对象表示。从另一个角度来看，在恒定时间内执行此操作本质上是不可能的，因为我们需要对每个桶中的每个节点进行此更改。

所有值都可以在固定时间内设置为新值的唯一情况是下面这个非常人为的例子，其中每个键都将与相同的对象相关联。，我们需要维护对该对象()的引用，即:它总是为每个存在的键检索相同的值，这似乎不是特别有用):

public class SingleValueMap<K, V> {
private Map<K, V> map = new HashMap<>();
private V commonValue;

public void setAll(V newValue) {
this.commonValue = newValue;
}

public void add(K key) {
map.put(key, commonValue);
}

public void add(K key, V newValue) {
setAll(newValue);
map.put(key, commonValue);
}

public V get(K key) {
if (!map.containsKey(key)) throw new NoSuchElementException();

return commonValue;
}
}

由于我们不再使用实际的HashMap的功能来存储值，HashMap可以替换为HashSet:

public class SingleValueMap<K, V> {
private Set<K> set = new HashSet<>();
private V commonValue;

public void setAll(V newValue) {
this.commonValue = newValue;
}

public void add(K key) {
set.add(key);
}

public void add(K key, V newValue) {
setAll(newValue);
set.add(key);
}

public V get(K key) {
if (!set.contains(key)) throw new NoSuchElementException();

return commonValue;
}
}

Answer 2

如果我正确理解这里的问题，每次调用setAll时，我们有效地忘记HashMap的所有值并且只跟踪它的键，就好像它是一个HashSet，其中get使用传递给setAll的值。此外，任何新的set调用应该仍然跟踪键和值，直到setAll在一段时间后被调用。

换句话说，您需要分别跟踪setAll之前的键集和setAll之后的键和值集，以便能够区分它们。

看看你是否能找到一种方法来平摊或通过常数时间操作，跟踪哪些键与最近的setAll操作相关联，哪些没有关联。

考虑到这看起来像一个家庭作业问题，我犹豫是否进一步帮助(根据这些SO指南)，但如果这不是家庭作业，请告诉我，我可以进一步研究这个主题。