How is the time complexity O(n/k) instead of O(1) on average ?
I don’t understand how “John” = 28.
i think it is because
n/k=O(1) best case since the number of pigeons and holes are the same.
n/k=O(1) average case since the number of pigeons and holes are nearly the same (few collisions, n and k are similar)
n/k~n/1~n worst case, since all the pidgeons are in one hole.
In a hashmap the value on the left can be seen as a key to a specific slot in the hashmap while the value on the right is the value placed in that slot for that key. The hashmap itself has an algorithm that it uses to place items via their keys in really specific slots. The algorithm assures us that that same value in the map can only be accessed via that same key.
So, when they entered
hashmap.put(“John”, 28);
into the hashmap, they created a slot that can be accessed by the key “John” in the hashmap. Then, the right value, 28, is placed in that slot.
So, when they try to get a value from the hashmap where the key “John” is slotted it returns the value they placed there, 28.
Depending on what you choose your keys and values to be in a hashmap you could pair literally anything together. You could use ints as keys and strings as values or ints as keys and ints values or almost any other combination of types as keys and values. It’s up to you to assess the problem to decide what should be the key and what should be the associated values returned via those keys!
The hash function from in Slide 1 is f(x) = len(x) % 6 and len('John') = 4 so f('John') = 4 % 6 = 4.
So we put the corresponding value 28 into the array’s 4-th slot.
You made it a little to complicated.
John is equal to 28 because that’s the value of the key
“John” being the key
“28” being the value
what is the pigeon hole principle?
what is the point of using unordered_map in c++? cant the map suffice the req?
If you want something a little more Pythonic for the Counter implementation, I suggest using dictionary’s .get function.
def Counter( _itemList: list ):
# Initialize new dictionary
countOf = {}
for item in _itemList:
# Add or update dictionary item
countOf[item] = countOf.get(item, 0) + 1
return countOf
Just imagine 4 crates and 5 items to place in these crates. You know that at least one of these crates is going to hold two items.
That’s the general idea, it can get much more complicated than that. I’d suggest looking at a book chapter like Johnsonbaugh’s Discrete Mathematics if you want more context/practice. Or YouTube…
Why is the worse case O(n)?
If each item is hashed to the same hash, wouldn’t we just use a lookup at the hashed slot? Then it’s O(1) to add or lookup…
for item in _itemList:
countOf.setdefault(item, 0)
countOf[item] += 1
I think your mistaken; Take this for example phone numbers
John : “+1938-324-0382”
This is saying the name John has the phone number “+1938-324-0382”.
The hashing function uses the key in this case “John” to generate the index where this value in this case “+1938-324-0382” will be stored.
The 28 could literally be anything, it could be a string, integer, another object. It doesnt matter, the key is what is used in the hashing function to generate the address of the storage of the data.
Hope this helps 
Just curious, for the C# solution, why did you choose to use a dictionary in the implementation versus a hash table? faster performance?