Skip to content

Instantly share code, notes, and snippets.

@johnboker johnboker/HASHIT.cs
Last active Aug 29, 2015

Embed
What would you like to do?
using System;
using System.Text;
namespace HASHIT
{
class MainClass
{
public static void Main (string[] args)
{
int t = Convert.ToInt32 (System.Console.ReadLine ());
for (int i = 0; i < t; i++)
{
string[] table = new string[101];
int n = Convert.ToInt32 (System.Console.ReadLine ());
for (int i2 = 0; i2 < n; i2++)
{
string line = System.Console.ReadLine ();
string op = line.Substring (0, 3);
string key = line.Substring (4);
int ix = FindKey (table, key);
if (op == "ADD")
{
if (ix == -1)
{
ix = FindNextOpenAddress (table, Hash (key));
if (ix >= 0)
{
table[ix] = key;
}
}
}
else
{
if (ix >= 0)
{
table[ix] = string.Empty;
}
}
}
StringBuilder sb = new StringBuilder ();
int count = 0;
for (int j = 0; j < 101; j++)
{
if (!string.IsNullOrEmpty (table[j]))
{
count++;
sb.AppendLine (j + ":" + table[j]);
}
}
Console.WriteLine (count);
Console.Write (sb.ToString ());
}
}
public static int Hash (string key)
{
int ret = 0;
ret = h (key) % 101;
return ret;
}
public static int h (string key)
{
int ret = 0;
int cnt = key.Length;
for (int i = 0; i < cnt; i++)
{
ret += (int)key[i] * (i + 1);
}
return ret * 19;
}
public static int FindKey (string[] table, string key)
{
int ix = Hash (key);
if (table[ix] == key)
return ix;
for (int j = 1; j < 20; j++)
{
int newix = (ix + j * j + 23 * j) % 101;
if (table[newix] == key)
{
return newix;
}
}
return -1;
}
public static int FindNextOpenAddress (string[] table, int ix)
{
if (string.IsNullOrEmpty (table[ix]))
return ix;
for (int j = 1; j < 20; j++)
{
int newix = (ix + j * j + 23 * j) % 101;
if (string.IsNullOrEmpty (table[newix]))
{
return newix;
}
}
return -1;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.