Skip to content

Instantly share code, notes, and snippets.

@ismailkocacan
Last active June 4, 2021 12:35
Show Gist options
  • Save ismailkocacan/bfaa254b597b1b127e6096b34f93c387 to your computer and use it in GitHub Desktop.
Save ismailkocacan/bfaa254b597b1b127e6096b34f93c387 to your computer and use it in GitHub Desktop.
simple array based hash table implementation
using System;
unsafe class Program
{
static KeyValue[] hashTable = new KeyValue[10];
static int Hash(string key, int count)
{
int total = 0;
fixed (char* pbegin = key)
{
char* p = pbegin;
while (*p != '\0')
{
total += (byte)*p;
p++;
}
}
return total % count;
}
unsafe static int djb2Hash(string key, int count)
{
int hash = 5381;
fixed (char* pbegin = key)
{
char* p = pbegin;
while (*p != '\0')
{
hash = ((hash << 5) + hash) + (byte)*p;
p++;
}
}
return hash % count;
}
class KeyValue
{
public KeyValue Next { get; set; }
public string Key { get; set; }
public string Value { get; set; }
}
static void Add(KeyValue newKeyValue)
{
int index = Hash(newKeyValue.Key, hashTable.Length);
newKeyValue.Next = hashTable[index];
hashTable[index] = newKeyValue;
}
static KeyValue FindByKey(string key)
{
int index = Hash(key, hashTable.Length);
KeyValue keyValue = hashTable[index];
while (keyValue != null)
{
if (keyValue.Key == key)
return keyValue;
keyValue = keyValue.Next;
}
return keyValue;
}
static void Main(string[] args)
{
Add(new KeyValue() { Key = "01", Value = "Adana" }); // collision
Add(new KeyValue() { Key = "10", Value = "Balıkesir" }); // collision
Add(new KeyValue() { Key = "06", Value = "Ankara" }); // collision
Add(new KeyValue() { Key = "60", Value = "Tokat" }); // collision
Add(new KeyValue() { Key = "34", Value = "İstanbul" });
Add(new KeyValue() { Key = "35", Value = "İzmir" });
KeyValue keyValue = FindByKey("01");
if (keyValue != null)
Console.WriteLine(keyValue.Key + ":" + keyValue.Value);
else
Console.WriteLine("Key Bulunamadı.");
Console.ReadKey();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment