Data Structure that performs set(), get(), setAll() in O(1)

Question

I'm trying to write a data structure that is capable to set all the Values in O(1).

My code:

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
    }
}

When I set variables for the first time and then set all the values to a specific variable it works, but when I try to put a new variable after setting all the variables I'm a bit confused.

What kind of solution can I use to make it work?

Answer 1

If you want to enhance your knowledge of Data Structures, I suggest you to implement your own version of Hash table data structure from the ground up (define an array of buckets, learn how to store elements in a bucket, how to resolve collisions and so on...) instead of decorating the HashMap.

Your current code is very contrived:

• By its nature, get() should not do anything apart from retrieving a value associated with a key because that's the only responsibility of this method (have a look at the implementation of get() in the HashMap class). Get familiar with the Single responsibility principle.
• The idea of throwing an exception when the given key isn't present in the map is strange. And NullPointerException is not the right type of exception to describe this case, NoSuchElementException would be more intuitive.
• You might also be interested in learning What does it mean to "program to an interface"?

And the main point is that is because you've picked the wrong starting point (see the advice at the very beginning), learn more about data structures starting from the simplest like Dynamic array, try to implement them from scratch, and gradually learn more about the class design and language features.

Time complexity

Regarding the time complexity, since your class decorates a HashMap methods set() and get() would perform in a constant time O(1).

If you need to change all the values in a HashMap, that could be done only a linear time O(n). Assuming that all existing values are represented by objects that are distinct from one another, it's inherently impossible to perform this operation in a constant time because we need to do this change for every node in each bucket.

The only situation when all values can be set to a new value in a constant time is the following very contrived example where each and every key would be associated with the same object, and we need to maintain a reference to this object (i.e. it would always retrieve the same value for every key that is present, which doesn't seem to be particularly useful):

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;
    }
}

And since we are no longer using the actual HashMap's functionality for storing the values, HashMap can be replaced with 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

If I'm understanding the problem here correctly, every time setAll is called, we effectively forget about all the values of the HashMap and track only its keys basically as if it were a HashSet, where get uses the value passed into setAll. Additionally, any new set calls should still track both the key and the value until setAll is called some time later.

In other words, you need to track the set of keys before setAll, and the set of key-and-values after setAll separately in order to be able to distinguish them.

See if you can find a way to amortize or through constant time operations, keep track of which keys are and are not associated with the latest setAll operation.

Given that this looks like a homework problem, I am hesitating to help further (as per these SO guidelines), but if this is not homework, let me know and I can delve further into this topic.