Class Notes (1,100,000)

CA (620,000)

Queen's (10,000)

CISC (500)

CISC 235 (20)

Robin W Dawes (20)

Lecture 13

CISC 235 – Lecture 13

Hashing Continued

Quadratic Probing

Quadratic probing is similar to linear probing except that instead of

f(i) = i, we use f(i) = c1*i + c2 * i^2 , where c1 and c2 are

constants

The algorithms we developed for linear probing (using "empty"

and "deleted" flag values) need only the new f(i) function to be

added.

Quadratic_Probing_Insert(k):

i = 0

v = h'(k)

a = v

while (i < m) and (T[a] not "empty") and (T[a]

not "deleted")

i += 1

a = (v + c1*i + c2*i^2) % m

if (T[a] is "empty") or (T[a] is "deleted")

T[a] = k

else

report "table full, insert failed"

Quadratic_Probing_Search(k):

i = 0

v = h'(k)

a = v

while (i < m) and (T[a] not "empty") and (T[a]

!= k)

i += 1

a = (v + c1*i + c2*i^2) % m

if T[a] == k

report "found it"

else

report "search failed

Quadratic_Probing_Delete(k):

i = 0

v = h'(k)

a = v

while (i < m) and (T[a] not "empty") and (T[a]

!= k)

i += 1

a = (v + c1*i + c2*i^2) % m

if T[a] == k

T[a] = "deleted"

else

report "search failed - could not

delete"

Quadratic probing greatly reduces the effect of primary

clustering. To illustrate this, consider a simple example: let c1 =

c2 = 1, and let m = 11. Let k1 and k2 be two keys. Suppose h'(k1)

= 0. Then k1's probe sequence is

i

h(k1,i)

0

0

1

2

2

6

3

1

4

9

...

...

Now suppose h'(k2) = 2. Then k2's probe sequence is

i

h(k2,i)

0

2

1

4

2

8

3

3

4

0

...

...

Even though the probe sequences both contain 2, they go off in

different directions after that. In general, two probe sequences

may hit the same address at any point, but then hit different

addresses after that.

Note that there is still a problem with what is called secondary

clustering: if h'(k1) == h'(k2), the probe sequences for k1 and k2

will be identical. Thus there are only m different probe sequences,

out of a possible m! sequences in which we could conceivably

search the table.

Quadratic probing has a potentially much bigger problem: unless

m, c1 and c2 are carefully chosen, a probe sequence may only

include a subset of the possible addresses. For example, let m =

16, c1 = 0 and c2 = 1. Suppose h'(k1) = 0. The probe sequence is

0, 1, 4, 9, 0, 9, 4, 1, 0, 1, 4, 9 etc. (taking 0, 1, 4, 9, 16, 25, 36, 49,

64, 81, 100, 121 etc all mod 16) ... we never examine any of the

other addresses.

Double Hashing

Double hashing attempts to combine the strong point of linear

probing (all addresses considered) with the strong point of

quadratic probing (reduced primary clustering). The technique is

simple: we include a second hash function h"(k), and define

h(k,i) = (h'(k) + i*h"(k)) mod m

Double hashing is effectively a generalization of linear probing,

except that instead of having a fixed "step size" that determines

how far we jump forward in the hash table on each iteration (in

linear probing, the step size is 1), we use the key itself to determine

the step size. Since the key is used to determine both the initial

**Unlock Document**

## More from OC330671

###### CISC 235 Lecture Notes - Lecture 1: Autocomplete

Lecture Note

###### CISC 235 Lecture Notes - Lecture 12: Self-Balancing Binary Search Tree, Binary Tree, Null Pointer

Lecture Note

###### CISC 235 Lecture Notes - Lecture 4: Reverse Polish Notation, Infix Notation, Operand

Lecture Note

## Similar documents like this

###### CISC235 Lecture 5: Week 6

Lecture Note

###### CISC 235 Lecture Notes - Lecture 8: Reverse Polish Notation, Polish Notation, Binary Tree

Lecture Note

###### CISC 235 Lecture Notes - Lecture 6: Binary Tree

Lecture Note

###### CISC 235 Lecture 12: CISC_235_29-March-2016

Lecture Note

###### CISC 235 Lecture Notes - Lecture 19: Directed Acyclic Graph, Topological Sorting, Critical Path Method

Lecture Note

###### CISC 235 Lecture Notes - Lecture 15: Merge Sort, Heapsort, Priority Queue

Lecture Note

###### CISC 235 Lecture Notes - Lecture 14: Donald Knuth, American Broadcasting Company

Lecture Note

###### CISC 235 Lecture Notes - Lecture 7: Binary Tree, Search Algorithm, Binary Search Algorithm

Lecture Note

###### CISC 235 Lecture Notes - Lecture 4: Sorting Algorithm, Quicksort, Simple Algorithm

Lecture Note

###### CISC 235 Lecture Notes - Lecture 2: Random-Access Machine, Virtual Memory, Memory Address

Lecture Note

###### CISC 235 Lecture Notes - Lecture 20: Minimum Spanning Tree, Binary Heap, Prims

Lecture Note

###### CISC 235 Lecture Notes - Lecture 9: Binary Search Tree, Search Algorithm, Binary Tree

Lecture Note

###### CISC 235 Lecture Notes - Lecture 21: Bit Array, The Algorithm, Bloom Filter

Lecture Note

###### CISC 235 Lecture Notes - Lecture 18: Popular Alternative, Tree Traversal, Binary Tree

Lecture Note

###### CISC235 Lecture 17: Week 17- Graph Searching Algorithms

Lecture Note