Created
March 30, 2012 14:57
-
-
Save imphasing/2252108 to your computer and use it in GitHub Desktop.
HashTable
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
| using System; | |
| using System.Collections.Generic; | |
| namespace HashTable | |
| { | |
| class HashTable<TKey, TValue> | |
| { | |
| private int count; | |
| private int size; | |
| private List<KeyValuePair<TKey, TValue>>[] values; | |
| public HashTable() | |
| { | |
| this.count = 0; | |
| // initial size of 400 | |
| this.size = 400; | |
| this.values = new List<KeyValuePair<TKey, TValue>>[this.size]; | |
| } | |
| // Hash the key and find the array index for the backing store | |
| private int GetIndex(TKey key) | |
| { | |
| int index = Math.Abs(key.GetHashCode() % size); | |
| return index; | |
| } | |
| public void Add(TKey key, TValue value) | |
| { | |
| if (this.ContainsKey(key)) | |
| throw new InvalidOperationException("Given key already exists in this HashTable"); | |
| /* | |
| * Resize the backing store if we've exceeded capacity, leave the old array just hanging around because | |
| * it's just an array of references that will be garbage collected. | |
| */ | |
| if (this.count == this.size) | |
| { | |
| int nextSize = size += size; | |
| var nextValues = new List<KeyValuePair<TKey, TValue>>[nextSize]; | |
| var oldValues = this.values; | |
| this.values = nextValues; | |
| this.size = nextSize; | |
| this.count = 0; | |
| foreach (var bucket in oldValues) | |
| { | |
| if (bucket != null) | |
| { | |
| foreach (var kvp in bucket) | |
| { | |
| this.Add(kvp.Key, kvp.Value); | |
| } | |
| } | |
| } | |
| } | |
| int index = this.GetIndex(key); | |
| if (values[index] == null) | |
| values[index] = new List<KeyValuePair<TKey, TValue>>(); | |
| var bucketEntry = new KeyValuePair<TKey, TValue>(key, value); | |
| values[index].Add(bucketEntry); | |
| this.count++; | |
| } | |
| public TValue Get(TKey key) | |
| { | |
| int index = this.GetIndex(key); | |
| var bucket = values[index]; | |
| // search through the bucket to find our actual kvp | |
| int bucketLocation = bucket.FindIndex(x => x.Key.Equals(key)); | |
| if (bucketLocation == -1) | |
| throw new KeyNotFoundException("Given key was not found in this HashTable"); | |
| return bucket[bucketLocation].Value; | |
| } | |
| public void Remove(TKey key) | |
| { | |
| int index = this.GetIndex(key); | |
| var bucket = values[index]; | |
| // Find the key in the bucket and remove it | |
| int bucketLocation = bucket.FindIndex(x => x.Key.Equals(key)); | |
| if (bucketLocation == -1) | |
| throw new KeyNotFoundException("Given key was not found in this HashTable"); | |
| bucket.RemoveAt(bucketLocation); | |
| } | |
| public bool ContainsKey(TKey key) | |
| { | |
| int index = this.GetIndex(key); | |
| var bucket = values[index]; | |
| // If the bucket isn't null and there's a kvp in the bucket, this key exists | |
| if (bucket != null && bucket.Count > 0) | |
| { | |
| int bucketLocation = bucket.FindIndex(x => x.Key.Equals(key)); | |
| if (bucketLocation != -1) | |
| return true; | |
| } | |
| return false; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment