Do you want to learn python from me with a lot of interactive quizzes, and exercises? Here is my project-based python learning course: codebasics.io/courses/python-for-beginner-and-intermediate-learners
Just started on the DSA journey combining practice with your guidance and taking notes. I started my Data science journey around 3n half years back and you were the first tutorial that I clicked for ML. I remember being so naive at that point but later on just got a flow out and got a chance to be a mature professional in data science field. Now feeling the urge for Targeting the Data Structure and Algorithms next!! Thank you so much! Enjoying it!
@Codebasics, I could image why HashTables are your favorite data structures...:) Exercises done and moving onto Stack and Queues ! Just brilliant tutorials.:)
Would be nice if you could touch on double hashing and also explain what happens when hash table itself needs to grow or the individual slot data structure has to grow. What happens to the time complexities in those cases?
You wrote this question one year ago, I don't know if my answer will help you anymore, but still I'm gonna answer it. However big a hash table/ hash map is gonna be, the time complexity will always be O(1), when talking about searching. The downside of hash tables is that if you need to store a huuuge amount of data, you need a pretty complex hash table and it will occupy a pretty big chunk of memory. The time complexity remains the same, though the *space complexity* will increase drastically.
Amazing video! Best explantion I have found and the exercises are very useful I just finnished the nyc_weather one. Used the built in hash function and handles collisions by adding (key, value) tuples to a list that is on the index. Thank you for the great video!
Thanks a lot Dhaval, I have been learning a lot from you and using this skill to search for a career as a developer or data scientist after 10 years of administration experience, hope I will find a career soon! I did all the exercises by myself with your encouragement but I check your every solution as well. I found the solution for Linear Probing is not working as expected when I am running the following case t = HashTable() t["march 6"] = 20 t["march 17"] = 88 del t["march 6"] t['march 17'] However, both of the following is working fine def __getitem__(self, key): h = self.get_hash(key) prob_range = self.get_prob_range(h) for prob_index in prob_range: element = self.arr[prob_index] if element is None: continue if element[0] == key: return element[1] def __getitem__(self, key): h = self.get_hash(key) for i in range(self.MAX): element = self.arr[h] h = (h+1)%self.MAX if element == None: continue if element[0] == key: return element[1]
Great videos, thank you so much! Do you have any projects that use these algorithms and data structures to help us imbed this information into our brains?
Hi, In the below snippet of your Linear Probing code, "if element is None: return" line is not required as it may return None if previous element of the desired element is None while traversing. However it is not running in any case when prob_range (even though it returns you all indexes) is used. def __getitem__(self, key): h = self.get_hash(key) if self.arr[h] is None: return prob_range = self.get_prob_range(h) for prob_index in prob_range: element = self.arr[prob_index] if element is None: return if element[0] == key: return element[1] For better understanding, if I change the code as shown below , then it will return None if previous element is None before the desired element is executed. Eg: [('march 17', 30), ('march 163', 355), ('march 193', 455), ('march 443', 455), ('march 553', 455), ('march 123', 455), ('march 133', 355), None, None, ('march 6', 20)] Output: It returns None for ''march 6' def __getitem__(self, key): h = self.get_hash(key) if self.arr[h] is None: return ##prob_range = self.get_prob_range(h) for prob_index in range(len(self.arr)): #Change here element = self.arr[prob_index] if element is None: return None #Change here if element[0] == key: return element[1] Thanks
I'm actually just kind of confused after watching these last two videos. In linked lists you clearly helped us understand the structure of a linked list then asked us to modify what you wrote with our own functions. That was helpful. Here you showed us 50 minutes of hash functions and how to mess with lists(arrays) to store values and avoid collisions. Yet none of the excercises have anything to do with the videos themselves. > videos: I'm going to teach you how to cook a steak on your stove top exercise: now pull out some chicken so we can get started
Great video! However I do have a confusion as you call a list of tuples as linked list in the video. Shouldn't it be just an array of tuples? Since these tuples are not really linked in anyway. I mean if I want to insert another tuple or delete one tuple, the time complexity here is O(n), where as it should be O(1) for linked list, correct?
h = self.gethash(key) key_exists = False slot = self.arr[h] #making a dynamic array to store collisions. for index, kv in enumerate(slot): #here Searching if the key already exists or not. k, v = kv #splitting the key and value pair if key == k: #if it matches the already existing key then insert it in the next slot. key_exists = True break if key_exists: #THIS IS TO UPDATE THE VALUE of same key. slot[index] =((key, value)) else: slot.append((key, value))
Thank you so much for your video! How would you implement a rehash to resize the current hash table? Any suggestions you could provide would be greatly appreciated!
I second this. I'm going through this transactional data that needs data augmentation with hash function and what Mandi has requested, will help alot. Thanks!
def display(self): for index, node in enumerate(self.arr): if node is not None: chain = [] current = node while current is not None: chain.append(f'({current.key}: {current.value})') current = current.next print(f'Index {index}: -> {" -> ".join(chain)}') else: print(f'Index {index}: -> None')
Sir you're awesome. I subscribed and liked your videos. In the future please make videos on how to prepare for coding test and interviews and tech interviews for companies
Hi i have a question here, to avoid collision we can resize the hashtable or increment it by one. So that we can get different hash values if there are any collisions. Is it possible to change the size of hashtable dynamically?
is this implementation is just for explaning the concept of hash table or it's practical cause why make thing when we already have dictionary and other data structures working like a hash table.
Hey man Excellent explanation and am studying from your videos right now I just found one small error in the hash table with linear probing solution We know according to our hash function 'march 6' and 'march 17' give the same value ie. 9 Now when using probing once we insert the value of march 6 followed by march 17 and if we delete the value for march 6 then calling for the value of march 17 returns none as while checking for the hash index it finds the index empty and returns none. Would love it if you could correct it as to how to get around this problem. Thanks a lot for the videos and seeing this in advance
Can anybody explain since we found the length of tuple is 2 and key is present at 0th index in the list then why do we inserting second key, value pair on that particular index.... isn't it that going to replace the first one
i finally completed the exercises. kind of annoyed that you just used a dictionary in the solution. i reimplemented an entire hashtable class with custom methods for them...like in the video. i had so many issues with the overall logic and making it solid. I had to figure out so many things..hah. i feel so dumb and like i wasted so much time
hello sir, thank you for your great tutorial, I’ve been following your AI engineer roadmap, so far I have learned a great deal of knowledge from your videos, I really appreciate it, but here I have a problem, the march 6 and march 17 with me return two different hashes which is 9 and 59 respectively, I’m kinda confused whether there is an issue with my code or you just made a simplifying assumption for understanding?
There is no linked list in the implementation of this program as you have not implemented one. Please add correction note. (You speak of linked list at around the 5:45 mark.)
Thanks for the great explanation......but I'm getting h value for 'march 6' and 'march 17' is different that is 9 and 59 ...so how to resolve this issue?
It's bcz you are using mod 100(means a 100 length array) but he is(in this video) using mod 10( reduced the array size to 10). In case you don't understand mod function here is used to make sure that our no.(index in this case) stays within our defined range.
Dhaval aap apni har video mai bol diya kijiye ki apka hindi channel bhi hai jo hindi mai comfortable hai woh bhi same benefits le sakta hai . Yeh ek request hai na ki salah. You are doing great job.
Awesome content! In my opinion, the following: for index,key_val_pair in enumerate(self.arr[h]): ## find key_value_pair that matches the key passed in by the function caller if len(key_val_pair) == 2 and key_val_pair[0] == key: self.arr[h][index] = (key,value) #tuples are immutable, so just replace the tuple with an entire new one found = True break could be replaced with: for key_val_pair in self.arr[h]: if len(key_val_pair) == 2 and key_val_pair[0] == key: key_val_pair = (key,value) found = True break It's shorter, and I think it's more intuitive. Thanks for these videos!
it doesn't update the values. I can not tell why, but I have just tried these loops on this array: arr = [[(i,i),(2*i,2*i)] for i in range(10)] your version doesn't update: for k in arr[9]: k=("value","key") this gives error: for k in arr[9]: k[0]="v" k[1]="k" this doesn't update: for i,k in enumerate(arr[9]): k=["key","val"] this updates the values: for i,k in enumerate(arr[9]): arr[9][i]=["key","val"] this updates as well: for i,k in enumerate(arr[9]): arr[9][i]=("key","val")
I understood the video well but the exercises are like made me feel am I really understanding. Please someone help me to choose the right path, do I need to go for learning advanced python side by side?
Sir, your video was of great help. Thank you. However, I have a doubt it would be helpful if you please clarify it. In chaining as said in video linked list is used. As I know every node in LL has a head and a next. So, if LL is used here then don't we have to use head and next in set and del methods? or simple list has been used here?
In python a simple list is a dynamic array. One can use dynamic array as well in place of a linked list. In previous tutorials I have mentioned difference between dynamic and static array. Please go through that.
A simple list is sufficient for chaining. I suspect chaining is used to show various ways of avoiding collision. This is the brute force solution. Then we go to better rehashing solutions like linear probing, quadratic probing, and eventually using the python built-in hashtable.
Can't we use hash function which is readily available and gives the unique hash value for every input so we won't be needing chaining and there won't be any case where the index of two or more different keys will be matching with each other.
Just a quick question: If Collision Handling methods make the search runtime go up to O(n), then is it really worth it to use hashmaps in the first place? I believe the lookup time also won't be constant time, it should be a linear time in the worst case.... Correct me if I'm wrong!
hello sir instead of using for loop directly if we check number of elements present in each list then going to for loop will it decrease the time complexity?
Hello Sir. Thank you so much for your videos, it has really been of help. I have just worked on the linear probing exercise and my solution is a little different from yours but it does what its suppose to do. I was hoping you could look into mine and comment on it, if it's right and why you didn't work it this way. class HashTable: def __init__(self): self.MAX = 10 self.arr = [None for i in range(self.MAX)] def get_hash(self, key): h = 0 for char in key: h += ord(char) return h % self.MAX def __setitem__(self, key, value): h = self.get_hash(key) if self.arr[h] is None: self.arr[h] = (key, value) else: empty_space = self.arr.index(None) # index() finds the first occurrence of an empty space self.arr[empty_space] = (key, value) def __getitem__(self, key): h = self.get_hash(key) return self.arr[h] h = HashTable() h['march 6'] = 130 h['march 7'] = 78 h['march 8'] = 210 h['march 9'] = 530 h['march 17'] = 28 print(h.arr) print(h['march 7']) Thank you very much sir. I look forward to your reply.
Hey, so when you manually modify your index position based on whichever the closest empty space is, you only do that in the setitem method and there is no conceivable way to calculate this changed index in the delitem and getitem methods so you end up with the wrong answer! For example: suppose you have an array the size of 5, and 2 keys: 'x' and 'y' which give you the same index 2. First when the array is empty, you add the value associated with 'x', say 'foo', at index 2. Now when you try to add 'boo' associated with key 'y', you get the same index 2 but then you see that it is not empty and so you add it at index 0. Now your hash function doesn't know that you've changed the index for the key 'y' to 0 and so when the user tries accessing the hash table with ['y'], the index that the function getitem receives is still 2 and so it returns the value of key 'x' instead of key 'y', thereby returning 'foo' instead of 'boo'! I hope this helped :)
@@akashvshroff HI.. can you kindly help in my doubt. In chaining as said in video linked list is used. As I know every node in LL has a head and a next. So, if LL is used here then don't we have to use head and next in set and del methods? or simple list has been used here?
@@debasmitachoudhury7398 Hey, so you could use your linked list and do that but here to make the implementation slightly easier to understand and for simplicity in code, a python list has been used. Moreover, unlike other languages, a python list is dynamic which means that it can be extended with no initial size and so it seems fitting for this scenario :)
You can introduce size as the argument in __init__() method for HashMap Class and give the desired size of hashmap while initializing the class when declaring the class object.
I am using following function: def add(key, val): hash_value = get_hash(key) d[hash_value].append((key, val)) instead of your __setitem__() function and still my code is working fine, and I don't understand why? and when I am using your __setitem__(), I am getting an error on the following line: self.arr[h][idx] = (key,val)
Sir,I have a doubt.Suppose all the elements got collided .Won't it append all the elements in a single array and therefore Won't the searching time be o(n)
I have one question, lets say we have three columns in an excel and i want to print the third column value on the basis of two columns as key. Ex: ice and cream keys give value “ice-cream trucks” another ex: ice and water gives “cold water” as value another ex: water and cream gives “yuck taste” as value , assume this in a excel and i want to display ice cream truck or yuck water or cold water on the basis of two key inputs how can i do that!!
I had the same question: I think its because if you notice he initiates the array as a list of empty lists. Python will return true to the if -statement in question for an empty list but we only want it to return true if there exist a tuple at each element in linked list. Seems to me hes being overcautious for the case that someone does want to insert an empty list as the key to a specific value.
Hello Sir, Since we already we have dict handy in python, then why we exactly use hashmap? Please help me to understand. Is it just to get to know how dict works
The code for implementing linear probing has problem with the case..... 1.March 6 and march 17 has same value of hash 2.March 6 already present in the correct position....let say at 9 3.March 17 is inserted at position 5 due to no gaps at previous position 4.if we deleted an element at position 3 5.and we want to update march 17 value ....due to gap present at position 3 it will again stored as a new element without getting updated...... ................................................ As I tried by myself and i compared wit the given solution i abel to find it Hope u change the code ....….....…............ aa.............. And i love the way you teaching i admire it thanks for this wonderful tutorials......❤️ From India,Andhra
Why is the hashtable in python implement as nested list however , other languages use a array that is linked with linked list to store data that has collisions?
Could someone please tell me why are we not appending the key value pair whenever we find key to be already present. We should append the key value pair to that element, isn't it? def __setitem__(self, key, value): h = self.get_hash(key) found = False # if key exists already then append the value to the key for idx, k in enumerate(self.arr[h]): if len(k) == 2 and k[0] == key: self.arr[h].append((key, value)) found = True break # if the key value pair doesn't exist, add the key and value if not found: self.arr[h].append((key, value))
Python dictionary works on the idea of hash table. Here we are building our own version of dictionary. So, using python's inbuilt dictionary to create a user defined dictionary makes no sense. I know your comment is from 9 months ago, may my comment be useful for upcoming viewers.
Because we are checking if the key value pair already exists or not. If they exit then just update them by new key,val pair else append them to the same index. Here's a Simpler code without found variable: hash_index = self.get_hash(key) for idx,ele in enumerate(self.hash_map[hash_index]): if ele[0]==key and len(ele)==2: self.hash_map[hash_index][idx] = (key,value) break else: self.hash_map[hash_index].append((key,value))
@@techno-tronics4946 I was confused about why we needed `self.hash_map[hash_index][idx] = (key,value)` since the if statement already checks for the key, value pairs. But now I understand that line of code is there to update a value, not just check it. Thanks for the explanation!
i think len(element) == 2 not important , because i want to check if key found in this position or not if key already found i will update its value regardless it was key, value or key without value i will put value for it , if it has length one that means key , None value that mean key already exist but has no value so i will update its value so i think len(element) == 2 not important@@techno-tronics4946
linear probing: class HashTable: def __init__(self): self.MAX = 10 self.arr = [(None,None) for i in range(self.MAX)] def get_hash(self, key): hash = 0 for char in key: hash += ord(char) return hash % self.MAX def __getitem__(self, index): h = self.get_hash(index) found=False if self.arr[h][0]==index: return self.arr[h][1] else: for idx,element in enumerate(self.arr[h+1:]+self.arr[:h-1]): if element[0] == index: return element[1] return self.arr[h] def __setitem__(self, key, val): h = self.get_hash(key) set = False for idx,element in enumerate(self.arr): if idx==h and element[0]!=None: for i,j in enumerate(self.arr[idx+1:]+self.arr[:idx-1]): if j[0]==None: self.arr[i]=(key, val) set=True break if not set: self.arr[h] = (key, val)
![Wiz Khalifa - Khalifa's Home [Official Music Video]](http://i.ytimg.com/vi/wnrLCTe0Nz4/mqdefault.jpg)
Do you want to learn python from me with a lot of interactive quizzes, and exercises? Here is my project-based python learning course: codebasics.io/courses/python-for-beginner-and-intermediate-learners
Hey, while handling the collisions in __setitem__() function, "if len(element) == 2" why is this necessary?
Timestamp : 7:42
@@Saurav061 Because we need to make sure that there are more than 1 element in there if we want to return from tuple, otherwise simply return value
Just started on the DSA journey combining practice with your guidance and taking notes. I started my Data science journey around 3n half years back and you were the first tutorial that I clicked for ML. I remember being so naive at that point but later on just got a flow out and got a chance to be a mature professional in data science field. Now feeling the urge for Targeting the Data Structure and Algorithms next!! Thank you so much! Enjoying it!
I have seen many videos but your videos have simplest explanation among all. Respect.
this is the best practical exercise and explanation for hashtables for python in entire web, big thank you
@Codebasics, I could image why HashTables are your favorite data structures...:)
Exercises done and moving onto Stack and Queues ! Just brilliant tutorials.:)
greatttttt.
i wanted to ask a ques dictionary itself handles this collision??
@@Shourya_performs No bro dictionary overwrites the previous value with the current value
@@saisridhart3133 yes bro.
Thnx
You're an excellent teacher, Dhaval. Thanks and hope your passion does a lot of good for you!
Took me a while to really get each of the steps but good video :)
Would be nice if you could touch on double hashing and also explain what happens when hash table itself needs to grow or the individual slot data structure has to grow. What happens to the time complexities in those cases?
You wrote this question one year ago, I don't know if my answer will help you anymore, but still I'm gonna answer it.
However big a hash table/ hash map is gonna be, the time complexity will always be O(1), when talking about searching. The downside of hash tables is that if you need to store a huuuge amount of data, you need a pretty complex hash table and it will occupy a pretty big chunk of memory. The time complexity remains the same, though the *space complexity* will increase drastically.
Amazing video! Best explantion I have found and the exercises are very useful I just finnished the nyc_weather one. Used the built in hash function and handles collisions by adding (key, value) tuples to a list that is on the index. Thank you for the great video!
Amazing video! This was by far the clearest explanation of this I've ever seen!
You are a very good teacher. Thank you Mr Dhaval
Best explanation and implementation of hash table ever, understand it immediately
Thanks a lot Dhaval, I have been learning a lot from you and using this skill to search for a career as a developer or data scientist after 10 years of administration experience, hope I will find a career soon!
I did all the exercises by myself with your encouragement but I check your every solution as well. I found the solution for Linear Probing is not working as expected when I am running the following case
t = HashTable()
t["march 6"] = 20
t["march 17"] = 88
del t["march 6"]
t['march 17']
However, both of the following is working fine
def __getitem__(self, key):
h = self.get_hash(key)
prob_range = self.get_prob_range(h)
for prob_index in prob_range:
element = self.arr[prob_index]
if element is None:
continue
if element[0] == key:
return element[1]
def __getitem__(self, key):
h = self.get_hash(key)
for i in range(self.MAX):
element = self.arr[h]
h = (h+1)%self.MAX
if element == None:
continue
if element[0] == key:
return element[1]
Sir your way of teaching is just excellent, god bless you!
Glad it was helpful!
Even to this date your videos are the best on the entire youtube. Hats off to you!! Really enjoying learning DSA :)
Great videos, thank you so much! Do you have any projects that use these algorithms and data structures to help us imbed this information into our brains?
This is actually a pretty good revision of the concepts too, thanks
glad you liked it
sooo clear and concise!!
And here I am paying college tuition and students loans to "learn" what this awesome dude gives out for free. You are the best man, love your content.
Hi,
In the below snippet of your Linear Probing code, "if element is None: return" line is not required as it may return None if previous element of the desired element is None while traversing. However it is not running in any case when prob_range (even though it returns you all indexes) is used.
def __getitem__(self, key):
h = self.get_hash(key)
if self.arr[h] is None:
return
prob_range = self.get_prob_range(h)
for prob_index in prob_range:
element = self.arr[prob_index]
if element is None:
return
if element[0] == key:
return element[1]
For better understanding, if I change the code as shown below , then it will return None if previous element is None before the desired element is executed.
Eg: [('march 17', 30), ('march 163', 355), ('march 193', 455), ('march 443', 455), ('march 553', 455), ('march 123', 455), ('march 133', 355), None, None, ('march 6', 20)]
Output: It returns None
for ''march 6'
def __getitem__(self, key):
h = self.get_hash(key)
if self.arr[h] is None:
return
##prob_range = self.get_prob_range(h)
for prob_index in range(len(self.arr)):
#Change here
element = self.arr[prob_index]
if element is None:
return
None #Change here
if element[0] == key:
return element[1]
Thanks
I'm actually just kind of confused after watching these last two videos. In linked lists you clearly helped us understand the structure of a linked list then asked us to modify what you wrote with our own functions. That was helpful.
Here you showed us 50 minutes of hash functions and how to mess with lists(arrays) to store values and avoid collisions. Yet none of the excercises have anything to do with the videos themselves.
> videos: I'm going to teach you how to cook a steak on your stove top
exercise: now pull out some chicken so we can get started
Great video! However I do have a confusion as you call a list of tuples as linked list in the video. Shouldn't it be just an array of tuples? Since these tuples are not really linked in anyway. I mean if I want to insert another tuple or delete one tuple, the time complexity here is O(n), where as it should be O(1) for linked list, correct?
Yes i am also confused
Crisp and clear tutorial for hash maps sir.Thank you. Could you please explain why if len(element) ==2 is checked in setitem function
It was done because your element is a (key,value) pair so the len has to be 2 for that.
Though I think the code will run smoothly without that.
h = self.gethash(key)
key_exists = False
slot = self.arr[h] #making a dynamic array to store collisions.
for index, kv in enumerate(slot): #here Searching if the key already exists or not.
k, v = kv #splitting the key and value pair
if key == k: #if it matches the already existing key then insert it in the next slot.
key_exists = True
break
if key_exists: #THIS IS TO UPDATE THE VALUE of same key.
slot[index] =((key, value))
else:
slot.append((key, value))
Thankyou sir i really apreciate your way of teaching
I commend your channel and explanations. Very well put together thank you!
I appreciate that!
@@codebasics sir can u please tell is it oky fir me btech cse interviews. ?
Wow thanks so much. Your explanation was very clear
Sir Sunday aur morning dono good ho gaye
Let me take the chance to click the 1000th like!! Do we have to manually deal with csv files or can the third party/standard lib modules be used?
well csv files can be read and analyzed easily using a python module called pandas
Great video. Thank you!
excellent explanation! thanks
Awesome videos. Thank so much for making such precise vidoes.
Glad you like them!
Thank you so much for your video! How would you implement a rehash to resize the current hash table? Any suggestions you could provide would be greatly appreciated!
I second this. I'm going through this transactional data that needs data augmentation with hash function and what Mandi has requested, will help alot. Thanks!
This was really helpful. Thank you.
def display(self):
for index, node in enumerate(self.arr):
if node is not None:
chain = []
current = node
while current is not None:
chain.append(f'({current.key}: {current.value})')
current = current.next
print(f'Index {index}: -> {" -> ".join(chain)}')
else:
print(f'Index {index}: -> None')
Great explanation!
You can use for else in 8:45 min.
Sir can you please make videos on dynamic programming...or can you please suggest some good channels from where i can follow.
G.O.A.T you're my hero!!
Sir you're awesome. I subscribed and liked your videos. In the future please make videos on how to prepare for coding test and interviews and tech interviews for companies
Thanks so much! Keep making these vids!
hey if anyone having a problem understanding for loop in this program try printing idx , element, h in after if statement and append statement
in Enumerate function we are not passing the entire array only the element of array ... that is the list of key value pairs of that particular element
In the __setitem__ method why do we have to check if the length of the element array is two ?
other than that great tutorial ♥️
Thanks ! I did 2 exercises by myself :) Soon going to Stack and Queue !
👍☺️ good job
Hi
i have a question here, to avoid collision we can resize the hashtable or increment it by one. So that we can get different hash values if there are any collisions. Is it possible to change the size of hashtable dynamically?
yes possible but again problem of re-allocation if you try to insert beyond the capacity
is this implementation is just for explaning the concept of hash table or it's practical cause why make thing when we already have dictionary and other data structures working like a hash table.
Hey man Excellent explanation and am studying from your videos right now
I just found one small error in the hash table with linear probing solution
We know according to our hash function 'march 6' and 'march 17' give the same value ie. 9
Now when using probing once we insert the value of march 6 followed by march 17 and if we delete the value for march 6 then calling for the value of march 17 returns none as while checking for the hash index it finds the index empty and returns none. Would love it if you could correct it as to how to get around this problem.
Thanks a lot for the videos and seeing this in advance
Room looks clean
Can anybody explain since we found the length of tuple is 2 and key is present at 0th index in the list then why do we inserting second key, value pair on that particular index.... isn't it that going to replace the first one
great channel sir. Can you please make vedios on priority queue and heap data structure?
This one was tough. Lot of moving parts for me. bout to get started on these problems
i finally completed the exercises. kind of annoyed that you just used a dictionary in the solution. i reimplemented an entire hashtable class with custom methods for them...like in the video. i had so many issues with the overall logic and making it solid. I had to figure out so many things..hah. i feel so dumb and like i wasted so much time
for adding elements to the linked list just do append method, you dont need to do the enumerate loop and the found check
I thinkkkkkkk.... :(((((
You need to do find check. Else if some one is updating a value at a given key it won't work
hello sir, thank you for your great tutorial, I’ve been following your AI engineer roadmap, so far I have learned a great deal of knowledge from your videos, I really appreciate it, but here I have a problem, the march 6 and march 17 with me return two different hashes which is 9 and 59 respectively, I’m kinda confused whether there is an issue with my code or you just made a simplifying assumption for understanding?
Same issue
When he was explaining Collision handling he assigned MAX to 10 instead of 100, that solved it for me and I think it will for you too
There is no linked list in the implementation of this program as you have not implemented one. Please add correction note. (You speak of linked list at around the 5:45 mark.)
def __delitem__(self, key):
h = self.get_hash(key)
for idx, k in enumerate(self.arr[h]):
if k[0] == key:
self.arr[h].remove(self.arr[h][idx])
thanks nice session
Thanks for the great explanation......but I'm getting h value for 'march 6' and 'march 17' is different that is 9 and 59 ...so how to resolve this issue?
It's bcz you are using mod 100(means a 100 length array) but he is(in this video) using mod 10( reduced the array size to 10). In case you don't understand mod function here is used to make sure that our no.(index in this case) stays within our defined range.
Instead of appending (key, value) tuple, can we append a list [key,value]? What changes will it make?
bruh first thing you should know is that we can't update a tuple so, he was not appending tuple he was appending list!!!
Dhaval aap apni har video mai bol diya kijiye ki apka hindi channel bhi hai jo hindi mai comfortable hai woh bhi same benefits le sakta hai . Yeh ek request hai na ki salah. You are doing great job.
Sure neha but I don't have many tutorials on Hindi channel. That's why I am not highlighting
Awesome content! In my opinion, the following:
for index,key_val_pair in enumerate(self.arr[h]):
## find key_value_pair that matches the key passed in by the function caller
if len(key_val_pair) == 2 and key_val_pair[0] == key:
self.arr[h][index] = (key,value) #tuples are immutable, so just replace the tuple with an entire new one
found = True
break
could be replaced with:
for key_val_pair in self.arr[h]:
if len(key_val_pair) == 2 and key_val_pair[0] == key:
key_val_pair = (key,value)
found = True
break
It's shorter, and I think it's more intuitive. Thanks for these videos!
it doesn't update the values. I can not tell why, but I have just tried these loops on this array:
arr = [[(i,i),(2*i,2*i)] for i in range(10)]
your version doesn't update:
for k in arr[9]:
k=("value","key")
this gives error:
for k in arr[9]:
k[0]="v"
k[1]="k"
this doesn't update:
for i,k in enumerate(arr[9]):
k=["key","val"]
this updates the values:
for i,k in enumerate(arr[9]):
arr[9][i]=["key","val"]
this updates as well:
for i,k in enumerate(arr[9]):
arr[9][i]=("key","val")
I understood the video well but the exercises are like made me feel am I really understanding. Please someone help me to choose the right path, do I need to go for learning advanced python side by side?
Sir, your video was of great help. Thank you. However, I have a doubt it would be helpful if you please clarify it. In chaining as said in video linked list is used. As I know every node in LL has a head and a next. So, if LL is used here then don't we have to use head and next in set and del methods? or simple list has been used here?
In python a simple list is a dynamic array. One can use dynamic array as well in place of a linked list. In previous tutorials I have mentioned difference between dynamic and static array. Please go through that.
A simple list is sufficient for chaining. I suspect chaining is used to show various ways of avoiding collision. This is the brute force solution. Then we go to better rehashing solutions like linear probing, quadratic probing, and eventually using the python built-in hashtable.
very informative
Glad it was helpful!
Can't we use hash function which is readily available and gives the unique hash value for every input so we won't be needing chaining and there won't be any case where the index of two or more different keys will be matching with each other.
for the setitem function, is the 'len(element) == 2 ' necessary? the every element in the linklist is the key-value pair, therefore it must be 2?
yea i also didnt get it can someone explain?
Its not required
yeah it may not be useful
Just a quick question: If Collision Handling methods make the search runtime go up to O(n), then is it really worth it to use hashmaps in the first place? I believe the lookup time also won't be constant time, it should be a linear time in the worst case.... Correct me if I'm wrong!
Yeah it will be in the first place if we wrote an efficient hash function..
You said "chaining" is using linked list; but I only see adding tuples to a list. Where is the linked list? Am I missing something? Thanks!
Thank you so much
Can you explain linearprobing imlementation same way??
hello sir instead of using for loop directly if we check number of elements present in each list then going to for loop will it decrease the time complexity?
why did you check the length of element in setitem method ?
Hello Sir. Thank you so much for your videos, it has really been of help. I have just worked on the linear probing exercise and my solution is a little different from yours but it does what its suppose to do. I was hoping you could look into mine and comment on it, if it's right and why you didn't work it this way.
class HashTable:
def __init__(self):
self.MAX = 10
self.arr = [None for i in range(self.MAX)]
def get_hash(self, key):
h = 0
for char in key:
h += ord(char)
return h % self.MAX
def __setitem__(self, key, value):
h = self.get_hash(key)
if self.arr[h] is None:
self.arr[h] = (key, value)
else:
empty_space = self.arr.index(None)
# index() finds the first occurrence of an empty space
self.arr[empty_space] = (key, value)
def __getitem__(self, key):
h = self.get_hash(key)
return self.arr[h]
h = HashTable()
h['march 6'] = 130
h['march 7'] = 78
h['march 8'] = 210
h['march 9'] = 530
h['march 17'] = 28
print(h.arr)
print(h['march 7'])
Thank you very much sir. I look forward to your reply.
Hey, so when you manually modify your index position based on whichever the closest empty space is, you only do that in the setitem method and there is no conceivable way to calculate this changed index in the delitem and getitem methods so you end up with the wrong answer!
For example: suppose you have an array the size of 5, and 2 keys: 'x' and 'y' which give you the same index 2. First when the array is empty, you add the value associated with 'x', say 'foo', at index 2. Now when you try to add 'boo' associated with key 'y', you get the same index 2 but then you see that it is not empty and so you add it at index 0. Now your hash function doesn't know that you've changed the index for the key 'y' to 0 and so when the user tries accessing the hash table with ['y'], the index that the function getitem receives is still 2 and so it returns the value of key 'x' instead of key 'y', thereby returning 'foo' instead of 'boo'! I hope this helped :)
@@akashvshroff HI.. can you kindly help in my doubt. In chaining as said in video linked list is used. As I know every node in LL has a head and a next. So, if LL is used here then don't we have to use head and next in set and del methods? or simple list has been used here?
@@debasmitachoudhury7398 Hey, so you could use your linked list and do that but here to make the implementation slightly easier to understand and for simplicity in code, a python list has been used. Moreover, unlike other languages, a python list is dynamic which means that it can be extended with no initial size and so it seems fitting for this scenario :)
@@debasmitachoudhury7398 a simple list have been used
Thanks
Hello Sir, can you please create a video developing of project using only DSA ?
sir, I have a doubt !!! why you saying that list as link-list at index h, as it is working as a list, not link-list.
@codebasics same doubt here!!
@@vrushaliprakashsalvi6167 same here also
which is correct while knowing the hash values %10 or %100 first video you used 100 in second you used 10
You can introduce size as the argument in __init__() method for HashMap Class and give the desired size of hashmap while initializing the class when declaring the class object.
i have doubt, for this setitem, getitem, delitem, still we are dependent on O(n). but how we are telling this o(1) ?
I am using following function:
def add(key, val):
hash_value = get_hash(key)
d[hash_value].append((key, val))
instead of your __setitem__() function and still my code is working fine, and I don't understand why?
and when I am using your __setitem__(), I am getting an error on the following line:
self.arr[h][idx] = (key,val)
Sir,I have a doubt.Suppose all the elements got collided .Won't it append all the elements in a single array and therefore Won't the searching time be o(n)
It can happen. And for that reason your hash function should be designed in a way that it can distribute elements equally among all buckets
Which hash function does dictionary implements behind is it linear probing or chaining using list
I can not find your exercises anywhere on-site . No Datastructure folder . Where are .cvs files .
I have one question, lets say we have three columns in an excel and i want to print the third column value on the basis of two columns as key. Ex: ice and cream keys give value “ice-cream trucks” another ex: ice and water gives “cold water” as value another ex: water and cream gives “yuck taste” as value , assume this in a excel and i want to display ice cream truck or yuck water or cold water on the basis of two key inputs how can i do that!!
tq so much sir.....................................
do more videos....
Sure.
Isn't the following incorrect?it always replaces the tuple in index 0 and it doesn't append
why the len(element) == 2 condition in the __setitem__ function
I had the same question: I think its because if you notice he initiates the array as a list of empty lists. Python will return true to the if -statement in question for an empty list but we only want it to return true if there exist a tuple at each element in linked list. Seems to me hes being overcautious for the case that someone does want to insert an empty list as the key to a specific value.
@@KarinaRodriguez-yv7mf its tuple of two elements ie key and value that's why len(element)==2
Hello Sir,
Since we already we have dict handy in python, then why we exactly use hashmap? Please help me to understand. Is it just to get to know how dict works
Yes. It is just to understand how dict works internally 👍😊
How come I don't see a Linked List? I only see the array was used in the collision place?
Sir i am getting march 17 hash as 59 is it wrong or its related ASCII code according to any other configuration of the computer system
Try using "July 18" and "July 27" it worked out for me!
@@vishwas2764 thx! you found it out by trial and error? because it would take a long time to find 2 keys with same hash values
what would be different if a dictionary was used in place of a simple list for chaining
Is that linked Liston separate chaining or usual 2d array
The code for implementing linear probing has problem with the case.....
1.March 6 and march 17 has same value of hash
2.March 6 already present in the correct position....let say at 9
3.March 17 is inserted at position 5 due to no gaps at previous position
4.if we deleted an element at position 3
5.and we want to update march 17 value ....due to gap present at position 3 it will again stored as a new element without getting updated......
................................................
As I tried by myself and i compared wit the given solution i abel to find it
Hope u change the code
....….....…............ aa..............
And i love the way you teaching i admire it thanks for this wonderful tutorials......❤️ From India,Andhra
Why is the hashtable in python implement as nested list however , other languages use a array that is linked with linked list to store data that has collisions?
The case where all the locations are filled in #LinearProbing i.e., 10 elements are filled according to the example what we need to do?
yes i also got that doubt
You didn't mention something pretty important as of 3.7 which is ordered insertion.
Could someone please tell me why are we not appending the key value pair whenever we find key to be already present.
We should append the key value pair to that element, isn't it?
def __setitem__(self, key, value):
h = self.get_hash(key)
found = False
# if key exists already then append the value to the key
for idx, k in enumerate(self.arr[h]):
if len(k) == 2 and k[0] == key:
self.arr[h].append((key, value))
found = True
break
# if the key value pair doesn't exist, add the key and value
if not found:
self.arr[h].append((key, value))
hello sir, what does the idx represents while iterating through the llist
Instead of taking python list what if I take a dictionary to store? It would not require looping all the values to find an item in that cell
is it possible to place a dictionary(a hash) under another hash table?
why not using dict element in the self.arr instead of linked lists?
Python dictionary works on the idea of hash table. Here we are building our own version of dictionary. So, using python's inbuilt dictionary to create a user defined dictionary makes no sense.
I know your comment is from 9 months ago, may my comment be useful for upcoming viewers.
Keys 'march 9' and 'march 10' has the same h, but are different keys, how do we deal with that. Thanks :-)
whats the use of len(element)==2 in " if len(element)==2 and element[0] == key" ???
Because we are checking if the key value pair already exists or not. If they exit then just update them by new key,val pair else append them to the same index.
Here's a Simpler code without found variable:
hash_index = self.get_hash(key)
for idx,ele in enumerate(self.hash_map[hash_index]):
if ele[0]==key and len(ele)==2:
self.hash_map[hash_index][idx] = (key,value)
break
else:
self.hash_map[hash_index].append((key,value))
@@techno-tronics4946 I was confused about why we needed `self.hash_map[hash_index][idx] = (key,value)` since the if statement already checks for the key, value pairs. But now I understand that line of code is there to update a value, not just check it. Thanks for the explanation!
@@zestful14 Anytime Bruh. Keep Learning 😁😁
i think len(element) == 2 not important , because i want to check if key found in this position or not if key already found i will update its value regardless it was key, value or key without value i will put value for it , if it has length one that means key , None value that mean key already exist but has no value so i will update its value so i think len(element) == 2 not important@@techno-tronics4946
linear probing:
class HashTable:
def __init__(self):
self.MAX = 10
self.arr = [(None,None) for i in range(self.MAX)]
def get_hash(self, key):
hash = 0
for char in key:
hash += ord(char)
return hash % self.MAX
def __getitem__(self, index):
h = self.get_hash(index)
found=False
if self.arr[h][0]==index:
return self.arr[h][1]
else:
for idx,element in enumerate(self.arr[h+1:]+self.arr[:h-1]):
if element[0] == index:
return element[1]
return self.arr[h]
def __setitem__(self, key, val):
h = self.get_hash(key)
set = False
for idx,element in enumerate(self.arr):
if idx==h and element[0]!=None:
for i,j in enumerate(self.arr[idx+1:]+self.arr[:idx-1]):
if j[0]==None:
self.arr[i]=(key, val)
set=True
break
if not set:
self.arr[h] = (key, val)
sir please make videos on tree data structure
Data Structures Tutorial In Python #7 - Tree (General Tree) ruclips.net/video/4r_XR9fUPhQ/видео.html
@@codebasics thank you sir , hope all data structures will be uploaded by u sir 🙏🙏 thank uu