Skip to content

Instantly share code, notes, and snippets.

@stanroze
Last active August 29, 2015 14:25
Show Gist options
  • Save stanroze/24b58c15292bafc5de61 to your computer and use it in GitHub Desktop.
Save stanroze/24b58c15292bafc5de61 to your computer and use it in GitHub Desktop.
Stupid dictionary implementation. Does not resize, does not implement anything other than Add.
public class StupidDictionary<T>
{
private readonly int _numOfBuckets = 3;
private readonly bool _quiet;
private readonly int _capacity;
private int _totalCollisions;
private int[] _buckets;
private Slot[] _slots;
private int _lastIndex;
private decimal _count;
public StupidDictionary(int capacity, int numberOfBuckets, bool quiet = false)
{
_capacity = capacity;
_numOfBuckets = numberOfBuckets;
_quiet = quiet;
_buckets = new int[_numOfBuckets];
_slots = new Slot[capacity];
_lastIndex = 0;
}
public bool Add(int key, T item)
{
//dumbest key ever
int hash = key;
int bucketIndex = (hash & 0x7FFFFFFF) %_numOfBuckets; //should be some dumb index
if (!_quiet)
{
Console.WriteLine("Adding: Key: {0} Hash: {1} Bucket: {3} Value: {2}", key, hash, item, bucketIndex);
}
int i;
int collision = 0;
for (i = _buckets[bucketIndex] - 1; i >= 0; i = _slots[i].Next)
{
if (!_quiet)
{
Console.WriteLine("Collision {1} for key {0}", key, ++collision);
}
_totalCollisions++;
//yes, I know hashcode and key are exactly the same in this implementation trololol
//but in a real implementation they wouldn't be
if (_slots[i].HashCode == hash && key == _slots[i].Key)
{
Console.WriteLine("Key already exists. {0}", key);
return false;
}
}
int index;
index = _lastIndex;
_lastIndex++;
_slots[index].HashCode = hash;
_slots[index].Value = item;
_slots[index].Key = key;
_slots[index].Next = _buckets[bucketIndex] - 1;
_buckets[bucketIndex] = index + 1;
_count++;
return true;
}
private struct Slot
{
public T Value;
public int Key;
public int Next;
public int HashCode { get; set; }
}
public override string ToString()
{
var stringbldr = new StringBuilder();
for (int i = 0; i < _lastIndex; i++)
{
stringbldr.AppendFormat("Key: {0,5} Value: {1} \r\n", _slots[i].Key, _slots[i].Value);
}
stringbldr.AppendFormat("Stupidest Dictionary Ever \r\n Total Capacity: {0} \r\n Number of Buckets: {1} \r\n Collisions: {2} \r\n", _capacity, _numOfBuckets, _totalCollisions);
return stringbldr.ToString();
}
}
public static int Main(String[] args)
{
var fillUpDictionary = 10000;
var dumbestDictionaryEver = new StupidDictionary<Guid>(capacity: fillUpDictionary, numberOfBuckets: 3, quiet: true);
//use the same seed to generate same random numbers each run
var rndm = new Random(1024);
var stopwatch = Stopwatch.StartNew();
for (int i = 0; i < fillUpDictionary; i++)
{
var key = rndm.Next();
dumbestDictionaryEver.Add(key, Guid.NewGuid());
}
stopwatch.Stop();
Console.WriteLine(dumbestDictionaryEver);
Console.WriteLine("Total time: {0}", stopwatch.Elapsed.ToString("c"));
Console.ReadKey();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment