0
Reply

Probing and Hashing problem

Matthew Peckham

Matthew Peckham

Sep 8 2010 5:16 PM
1.8k
Hi guys, for a University assignment (referral, eek!) I need to hash and sort some data. Which isn't too bad, but then I need to write a program displaying the results in C#. Here's the data I need to work with, and my worked out values:

Hashing function H(Ln) = n%10
Probing function P(Ln) = max (1, n/10)

A1 % 10 = 1
I9 % 10 = 9
R18 % 10 = 8
S19 % 10 = 9
E5 % 10 = 5
O15 % 10 = 5
Y25 % 10 = 5


This tells me that the data should appear in the table as such:


0 -
1 - A1
2 -
3 - Y25

4 - O15

5 - E5

6 -

7 - S19

8 - R19

9 - E5


But, when I code it, the results tell me S19 appears in row 6 as opposed to row 7! Please can you take a look at my code and tell me exactly where I've gone wrong? Thanks.

 using System;
using System.Collections.Generic;
using System.Text;

namespace ReferralAssignment1Question1
{
public class ReferralHashing
{
public struct Referral
{
//Define the variables
public int value1;
public string withLetter;

public Referral(int a, string b, string c)
{
value1 = a;
withLetter = b;
}
}

//Input the hashing and probing formulas
public int hashing(int n)
{
int position;

position = n % 10;
return position;
}

public int probe(int n)
{
int position;

position = Math.Max(1, n / 10);
return position;
}

public int wrap(int h, int p, int[] f)
{
int d;

d = h - p;

if (d < 0)
{
d = 10 + (h - p);
}
if (f[d] == 1)
{
d = d - p;
d = wrap(d, p, f);
}

return d;
}

public static void Main(string[] args)
{
//Input the values to be processed
int key = 0;
int pos = 0;
int h;
int p;
int[] flag = new int[10] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int[] value1 = new int[7] { 1, 9, 18, 19, 5, 15, 25 };
string[] withLetter = new string[7] {"A1",
"I9",
"R18",
"S19",
"E5",
"O15",
"Y25"};

Referral[] bl = new Referral[10];
for (int i = 0; i < 10; i++)
{
bl[i] = new Referral();
}

ReferralHashing blh = new ReferralHashing();

for (int i = 0; i < 7; i++)
{
key = value1[i];
h = blh.hashing(key);
if (flag[h] == 1)
{
p = blh.probe(key);
pos = blh.wrap(h, p, flag);
}
else
{
pos = h;
}
flag[pos] = 1;
bl[pos].value1 = value1[i];
bl[pos].withLetter = withLetter[i];

//Display the results in the console
Console.WriteLine(bl[pos].withLetter + "'s position in the table: " + pos);
}
}
}
}