Quadratic probing

quadratic

1. Quadratic probing M.Rishi vinthiya M.SC(IT)

2. Quadratic probing Quadratic probing  is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary  quadratic polynomial until an open slot is found.

3. Quadratic probing can be a more efficient algorithm in a open addressing table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune. It also provides good memory caching because it preserves some locality of reference however , linear probing has greater locality and, thus, better cache performance

4. Quadratic function Let h(k) be a hash function that maps an element k to an integer in [0,m-1], where m is the size of the table. Let the i th  probe position for a value k be given by the function Quadratic Probing is similar to Linear probing. The difference is that if you were to try to insert into a space that is filled you would first check 1^2 = 11​2​​=1 element away then 2^2 = 42​2​​=4 elements away, then 3^2 =93​2​​=9 elements away then 4^2=164​2​​=16 elements away and so on.

5. Double Hashing Double Hashing is works on a similar idea to linear and quadratic probing. Use a big table and hash into it. Whenever a collision occurs, choose another spot in table to put the value. The difference here is that instead of choosing next opening, a second hash function is used to determine the location of the next spot. For example, given hash function H1 and H2 and key

6. Check location hash1(key). If it is empty, put record in it. If it is not empty calculate hash2(key). check if hash1(key)+hash2(key) is open, if it is, put it in repeat with hash1(key)+2 hash2(key), hash1(key)+3 hash2(key) and so on, until an opening is found. like quadratic probing, you must take care in choosing hash2. hash2 CANNOT ever return 0. hash2 must be done so that all cells will be probed eventually.

7. Quadratic Probing Algorithm Let h(k) be a hash function that maps an element to an integer in {o, m-1}, where m is the size of the table . Let the i th  probe position for a value be given by the function h( k,i )=(h(k)+c 1 i+c 2 i 2 )(mod m)where c 2 ≠0. if c 2 =0,then h( k,i ) degrades to a linear probe. For a given hash table, the values of C 1  and C 2  remain constant.

8. Linear probing has the best cache performance but suffers from clustering. One more advantage of Linear probing is easy to compute. Quadratic probing lies between the two in terms of cache performance and clustering Double hashing has poor cache performance but no clustering . Double hashing requires more computation time as two hash functions need to be computed

9. Chaining is mostly used when it is unknown how many and how frequently keys may be inserted or deleted. Open addressing is used when the frequency and number of keys is known. Cache performance of chaining is not good as keys are stored using linked list.