Very clear explanation overall👍.In your discussion on quadratic probing though, you said that items (Zuko) will be placed further down the list, preventing items (Zuko) to take other items’ place. I think this may not be convincing.
The problem with linear probing is that it creates Primary Clustering effect where items are clustered together if they all hashed to the same index. Quadratic probing just separate the items further away when they are hashed to the same index. It helps but it may again create Secondary Clustering effect as two items that are hashed to the same initial index will have the same probe sequence. Whichever collision resolution technique you use other than Separate chaining, you are placing items to “take some other item’s place”. Quadratic probing is better in a way that it spreads out the items slightly better than linear probing.
Also, the modulo in most hashing functions is used to wrap around the array because hash tables have a finite size.
Thanks for the comments! That's a really clear explanation of primary and secondary clustering, and I definitely agree that probing (linear or quadratic) is not perfect in preventing collision problems. Separate chaining may indeed be the better option.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Very clear explanation overall👍.In your discussion on quadratic probing though, you said that items (Zuko) will be placed further down the list, preventing items (Zuko) to take other items’ place. I think this may not be convincing.
The problem with linear probing is that it creates Primary Clustering effect where items are clustered together if they all hashed to the same index. Quadratic probing just separate the items further away when they are hashed to the same index. It helps but it may again create Secondary Clustering effect as two items that are hashed to the same initial index will have the same probe sequence. Whichever collision resolution technique you use other than Separate chaining, you are placing items to “take some other item’s place”. Quadratic probing is better in a way that it spreads out the items slightly better than linear probing.
Also, the modulo in most hashing functions is used to wrap around the array because hash tables have a finite size.
Thanks for the comments! That's a really clear explanation of primary and secondary clustering, and I definitely agree that probing (linear or quadratic) is not perfect in preventing collision problems. Separate chaining may indeed be the better option.