- public class DoubleHash {
- const int DEFAULT_INITIAL_BUCKETS = 100;
-
- public DoubleHash () : this (DEFAULT_INITIAL_BUCKETS) {}
-
- public DoubleHash (int size)
- {
- count = size;
- buckets = new Entry [size];
- }
-
- int count;
- Entry [] buckets;
- int size = 0;
-
- class Entry {
- public object key1;
- public object key2;
- public int hash;
- public object value;
- public Entry next;
-
- public Entry (object key1, object key2, int hash, object value, Entry next)
- {
- this.key1 = key1;
- this.key2 = key2;
- this.hash = hash;
- this.next = next;
- this.value = value;
- }
- }
-
- public bool Lookup (object a, object b, out object res)
- {
- int h = (a.GetHashCode () ^ b.GetHashCode ()) & 0x7FFFFFFF;
-
- for (Entry e = buckets [h % count]; e != null; e = e.next) {
- if (e.hash == h && e.key1.Equals (a) && e.key2.Equals (b)) {
- res = e.value;
- return true;
- }
- }
- res = null;
- return false;
- }
-
- public void Insert (object a, object b, object value)
- {
- // Is it an existing one?
-
- int h = (a.GetHashCode () ^ b.GetHashCode ()) & 0x7FFFFFFF;
-
- for (Entry e = buckets [h % count]; e != null; e = e.next) {
- if (e.hash == h && e.key1.Equals (a) && e.key2.Equals (b))
- e.value = value;
- }
-
- int bucket = h % count;
- buckets [bucket] = new Entry (a, b, h, value, buckets [bucket]);
-
- // Grow whenever we double in size
- if (size++ == count) {
- count <<= 1;
- count ++;
-
- Entry [] newBuckets = new Entry [count];
- foreach (Entry root in buckets) {
- Entry e = root;
- while (e != null) {
- int newLoc = e.hash % count;
- Entry n = e.next;
- e.next = newBuckets [newLoc];
- newBuckets [newLoc] = e;
- e = n;
- }
- }
-
- buckets = newBuckets;
- }
- }
- }
-