Hashing: Quadratic Probing

Discussion in 'Homework Help' started by zulfi100, May 4, 2016.

  1. zulfi100

    Thread Starter Member

    Jun 7, 2012
    320
    0
    Hi,
    My book shows following sequence:
    9, 10, 8, 13, 5, 18, 0, 6, 12, 15, 3, 7, 11, 1, 17, 16, 2, 14, 4

    I am trying to regenerate it. I am able to find:
    h(k) = 9%19 = 9
    h(k) + 1 power 2 = 10 % 19 = 10
    h(k) - 1 power 2 = 8 % 19 = 8
    h(k) + 2 power 2 = 13 % 19 = 13
    h(k) - 2 power 2 = 5 % 19 = 5
    h(k) + 3 power 2 = 18 % 19 = 18
    h(k) - 3 power 2 = 0
    h(k) + 4 power 2 = 9 + 16 = 25 % 19 = 6
    h(k) - 4 power 2 = 9 -16 = -7 %19 = -7 which is wrong, it should be 12. I know 19 -7 = 12. But i dont know how to get it.

    They are using the formula:

    h(K), h(K) + 1, h(k) -1, h(k) + 4, h(K) - 4, .... h(K) + (TSIZE -1)power 2 / 4, h(k) - (TSIZE -1) power 2 /4 all divided modulo TSize.
    where j =4 & table size = 19 & assuming h(K) = 9.
    Some body please guide me how to solve it.

    Zulfi.
     
  2. MrAl

    Well-Known Member

    Jun 17, 2014
    2,418
    488
    Hello there,

    Calculating Mod is different for negative numbers than for positive numbers. Look that up you'll find more information.

    For example, if the rule for Mod(-x,N) is to add N to -x until we get a number greater that zero, then we would get:
    -7+19=12

    What what i understand rules for Mod negative numbers vary so you'll have to simply do a few calculations to find out which rule they are using. it looks like that one above though., but test more results to be sure or look it up in your book if you have one.

    Just to note, the next two numbers in the sequence, 15 and 3, do result from using the above rule.
     
  3. WBahn

    Moderator

    Mar 31, 2012
    17,715
    4,788
    In most languages, the % operator is NOT the modulo operator, it is the remainder operator. When the dividend and the divisor are both positive, they produce the same result. But when one (or both) is negative they may or may not produce the same result. It depends on how integer division is defined and there are two options -- round toward zero or round toward negative infinity. As is commonly the case, each option has pros and cons and so, as is commonly the case, some languages choose one and other languages choose the other.

    In either case, most languages (I know of no exception) that support both integer division and the remainder operator require that the following relationship hold true:

    if a, b, q, r are integer types, then if

    q = a / b AND r = a % b

    then it is required that

    a = q * b + r

    Note that if a<0 and b>0, then if (a/b) rounds toward zero the only way the last equation can hold is if r < 0.

    If you want the principal modulus (i.e., 0 <= r < b) for b>0, then YOU are responsible for ensuring that this will happen. The easiest way is to ensure that both a and b are positive before applying the remainder operator. If b>0 (as is usually the case when you care about modulo division), then you can do something like

    while (a < 0) a += b;

    Unless you are doing something unusual, this loop should only execute a few times (usually just zero or one times), so the performance hit is very small.

    Another way is to adjust the result after the remainder operator is applied

    while (r < 0) r += b;

    In principle, this should always execute either zero or once, so you should be able to get away with a simple if statement instead of a while statement.
     
Loading...