How would an empty HashMap with .containsKey() be true?-CodePudding

I am a beginner programmer working on a Two Sum problem. An array of integers are given as well as an integer, target. The intention of the program is to find which two numbers in the array of integers add up to the target integer. The most efficient solution I am seeing is quite ingenious in how it iterates over all of the integers in the array and checks if the difference between each integer in the array and the target number is another integer in the array. Then those two would be the solution. My issue is with the HashMap part. How would an empty HashMap .containsKey() work if it is empty and has no keys in it?

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n=nums.length;
        Map<Integer,Integer> map=new HashMap<>();
        int[] result=new int[2];
        for(int i=0;i<n;i  ){
            if(map.containsKey(target-nums[i])){
                result[1]=i;
                result[0]=map.get(target-nums[i]);
                return result;
            }
            map.put(nums[i],i);
        }
        return result;
    }
}

I tried to research solution explanations but all of them just said that the solution checks if the values are in the map but how would any values be in the map if it is empty and was never linked to the integers array? Thanks a lot for the help.

CodePudding user response：

I give you a phone book. I ask you if 'Ryan Siegrist' is in it. You open it up intending to scan it (or perhaps you're going to be smarter about it and use a fancy algorithm, such as binary searching by opening it to the middle page to see if you should go 'higher' or 'lower') - and it turns out the phone book is simply empty.

The correct answer is of course 'no, Ryan Siegrist is not in this empty phone book'.

HashMap is no different. .containsKey(whateverYouLike) returns false if you invoke it on an empty list. Why wouldn't it?

The stated algorithm does nothing the first time you loop, but note that at the end of the for look, whether the if ( containsKey ) check worked out or failed, an entry is added to the map. So the second and further runs through that loop, the map is no longer empty.

CodePudding user response：

Short version: If the map is empty and it does not contain a key. Then the line:

map.put(nums[i],i);

will still execute. This is because it is outside of the if check.

Long version

So when the code first iterates through the array, the HashMap is always empty at first because it was initialized as such:

Map<Integer,Integer> map=new HashMap<>();

Then the first iteration of the if check returns false:

if(map.containsKey(target-nums[i]))

But it still executes the line of code which will associate the map with the value of nums at the index of i with the index of i as the value for the map.

Then the loop will continue iterating until a solution is found or the loop terminates.