#Day31 #100DaysOfCode
the problem with chaining is that it doesn't cache friendly. This means that related data might not be placed closed together in a temporary call which results in cache miss. This is why operation like delete works really well on a single linked list but in an array of linked list, it sometimes works and sometimes not. other than that, chaining costs extra spaces because each row of a table is a separate linked list which might be wasted if not used.
open addressing is a second technique of hash table that solves the drawback of chaining. all keys are stored in the table itself, so cache friendly. However, there is situation happens like clustering where different indexes iteratively occupying all the spaces in the table when a key is inserted, another new key inserted may find it hard to find a space. And the table might become full. therefore, open addressing works best when the no of keys and how frequent keys are inserted and deleted is known.
the first form of open addressing is linear probing. when h(k, 0) alr has key, h(k, 1) is checked. in simple words, if a slot is occupied, the next slot is checked.
the second form is quadratic probing. when h(k, i) is full, h(k, square(i)) is checked.
the final form is double hashing. this is where a second hash function is used when a space needs to be checked.
time complexity of open addressing is O(1) for insert, delete, and search (for best and average case), O(n) for worst case.
Space complexity is O(n).
the problem with chaining is that it doesn't cache friendly. This means that related data might not be placed closed together in a temporary call which results in cache miss. This is why operation like delete works really well on a single linked list but in an array of linked list, it sometimes works and sometimes not. other than that, chaining costs extra spaces because each row of a table is a separate linked list which might be wasted if not used.
open addressing is a second technique of hash table that solves the drawback of chaining. all keys are stored in the table itself, so cache friendly. However, there is situation happens like clustering where different indexes iteratively occupying all the spaces in the table when a key is inserted, another new key inserted may find it hard to find a space. And the table might become full. therefore, open addressing works best when the no of keys and how frequent keys are inserted and deleted is known.
the first form of open addressing is linear probing. when h(k, 0) alr has key, h(k, 1) is checked. in simple words, if a slot is occupied, the next slot is checked.
the second form is quadratic probing. when h(k, i) is full, h(k, square(i)) is checked.
the final form is double hashing. this is where a second hash function is used when a space needs to be checked.
time complexity of open addressing is O(1) for insert, delete, and search (for best and average case), O(n) for worst case.
Space complexity is O(n).
