Hashing With Quadratic Probing - BunksAllowed

BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

Join WhatsApp Grpup using https://chat.whatsapp.com/EAcqRurEOXb52Ax7Tlmj9I

  • Home
    • Home Data Structures Technology Hashing With Quadratic Probing

    Hashing With Quadratic Probing

    Share This

    Quadratic probing uses a hash function of the form:

    h(k, i)= (h'(k) + c1i + c2i2) mod m

    Where h' is the auxiliary hash function, c1 and c2 != 0 .The initial position probed is T(h'(k)); later positions probed are offset by amounts that depend in a quadratic manner on the probe number i .

    Let's take an example. Consider the keys 76, 26, 37, 59, 21, and 65 into the hash table of size m=11 using quadratic probing with c1=1 and c2=3 with hash function h'(k)=k mod m.


    Initially, the table is empty.

    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]

    h(76,0) = (76 mod 11 + 0 + 3x0) mod 11 =10

    h(26,0) = (26 mod 11 + 0 + 3x0) mod 11=4

    h(59,0) = (59 mod 11 + 0 + 3x0) mod 11=4. a[4] is not free. So the next sequence will be

    h(59,1) = (59 mod 11 + 1 + 3x1) mod 11=8

    Similarly, other keys are placed properly in the correct position. The hash table becomes,

    a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
    65 21 26 59 37 76 
    Source code of Hashing with Quadratic Probing
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    #include <stdio.h>
    #define MAX 11
    int a[MAX];
    void qp(int ,int[]);
    void qpsr(int, int[]);
    void display(int[]);
    int main()
    {
    int i,key,ch;
    for(i=0;i < MAX;i++)
    a[i]=-1;
    do
    {
    printf("\n1.insert");
    printf("\n2.search key");
    printf("\n3.Display");
    printf("\n4.exit");
    printf("\nenter choice:");
    scanf("%d",&ch);
    switch(ch)
    {
    case 1:do
    {
    printf("\nenter key value[type -1 for termination]");
    scanf("%d",&key);
    if(key!=-1)
    qp(key,a);
    }while(key!=-1);
    break;
    case 2:printf("\nenter search key value:");
    scanf("%d",&key);
    qpsr(key,a);
    break;
    case 3:display(a);
    break;
    case 4:return 0;
    }
    }while(ch!=4);
    return 0;
    }
    void qp(int key,int a[MAX])
    {
    int loc,i=1;
    loc=key%MAX;
    while(a[loc]!=-1)
    {
    loc=(key%MAX+(i*i));
    loc=loc%MAX;
    i++;
    }
    a[loc]=key;
    }
    void qpsr(int key,int a[MAX])
    {
    int loc;
    loc=key%MAX;
    while((a[loc]!=key)&&(a[loc]!=-1))
    loc=++loc%MAX;
    if(a[loc]!=-1)
    printf("\nsearch successful at %d index of list",loc);
    else
    printf("\nsearch unsuccessful");
    }
    void display(int a[MAX])
    {
    int i;
    for(i=0;i < MAX;i++)
    printf("%d ",a[i]);
    }
    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX




    Happy Exploring!

    Tags
    Share This
    Author Image

    About BunksAllowed

    By on
    Labels: ,

    No comments:

    Post a Comment

    Note: Only a member of this blog may post a comment.

    Subscribe to: Post Comments (Atom)

    About BunksAllowed