Last active
August 29, 2015 14:25
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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