Tables


A Table is an unordered collection of T with support for hashed searches by a separate key type K. When declaring a Table, it is expected that the key K derives from IEquatable of T. It is also expected that the data type T derives from IEquatable of T. To illustrate how a hash table works, consider the following example.

// Calculus -- Project Table

using System;
using Calculus;

class Key : IEquatable<T>
{
    public string KeyString;

    public Key(string StringIn) { KeyString = StringIn; }

    public virtual bool Equals(T Data) { return KeyString == Data.Key; }

    public override int GetHashCode() { return KeyString.GetHashCode(); }

    public override string ToString() { return KeyString; }
}

class T : IEquatable<T>
{
    public string Key;
    public int Data;

    public T(string KeyIn, int DataIn) {Key = KeyIn; Data = DataIn;}

    public virtual bool Equals(T Compare) { return Key.Equals(Compare.Key); }

    public override int GetHashCode() {return Key.GetHashCode(); }

    public override string ToString() { return "(" + Key + "," + Data + ")"; }
}

class Program
{
    static void Main()
    {
        Table<Key, T> Table = new Table<Key, T>() {new T("String1", 1),
                                                   new T("String2", 2),
                                                   new T("String3", 3) };

        T Found = Table[new Key("String2")]; // Perform a hashed search for a key

        Console.WriteLine("Found == {0}", Found);

        Console.WriteLine("Hash Table == {0}", Table);
    }
}

The key class Key is a wrapper for string. Note that it provides a virtual method Equals, which determines when a key K is equal to a type T. The type T contains a string and an integer, with the string being the key field. The class Key also overrides GetHashCode() to provide a sensible hash code. This is a requirement. The class T derives from IEquatable and provides the method Equals. The class T also overrides GetHashCode(), which is required so that a hash table can be built.

In Main(), a hash tree is created and loaded with three entries. Then a hashed search of the tree is conducted and the result printed. All works as expected.

It is possible to simplify the notation of the search. Rather than supply a wrapper for 'string', it is possible to use strings directly. The next program does this.

// Calculus -- Project Table2

using System;
using Calculus;

class T : IEquatable<T>
{
    public string Key;
    public int Data;

    public T(string KeyIn, int DataIn) { Key = KeyIn; Data = DataIn; }

    public virtual bool Equals(T Compare) { return Key.Equals(Compare.Key); }

    public override int GetHashCode() { return Key.GetHashCode(); }

    public override string ToString() { return "(" + Key + "," + Data + ")"; }
}

class KeyComparer : IEqualityComparer<string,T>
{
    public virtual bool Equals(string Key, T Data) { return Key.Equals(Data.Key); }

    public virtual int GetHashCode(string s) { return s.GetHashCode(); }
}

class Program
{
    static void Main()
    {
        Table<string, T> Table = new Table<string, T>(new KeyComparer())  {new T("String1", 1),
                                                                           new T("String2", 2),
                                                                           new T("String3", 3) };

        T Found = Table["String2"]; // Perform a hashed search for a key

        Console.WriteLine("Found == {0}", Found);

        Console.WriteLine("Hash Table == {0}", Table);
    }
}

The class KeyComparer provides an equality comparison between the class string and the class T. Then the search notation is simplified and made faster.

Performance

The class Table represents binary hash tables. The generic Table<K,T> resembles the generic Tree<K,T>. The difference is that Tree is an ordered collection and Table is an unordered collection. To see how these classes perform, consider the program below.

// Calculus -- Project Table3
//     -- Table vs Tree

using System;
using Calculus;

class T : IEquatable<T>,
          IComparable<T>
{
    public string Key;
    public int Data;

    public T(string KeyIn, int DataIn) { Key = KeyIn; Data = DataIn; }

    public virtual bool Equals(T Compare) { return Key.Equals(Compare.Key); }

    public virtual int CompareTo(T Compare) { return Key.CompareTo(Compare.Key); }

    public override int GetHashCode() { return Key.GetHashCode(); }

    public override string ToString() { return Key; }
}

class KeyEqualityComparer : IEqualityComparer<string, T>
{
    public virtual bool Equals(string Key, T Data) { return Key.Equals(Data.Key); }

    public virtual int GetHashCode(string s) { return s.GetHashCode(); }
}

class KeyComparer : IComparer<string, T>
{
    public int Compare(string s, T t) { return s.CompareTo(t.ToString()); }
}

enum Limits { Maximum = 100000 };

class Program
{
    static void Main()
    {
        Table<string, T> Table = new Table<string, T>(new KeyEqualityComparer());

        DateTime BuildStart = DateTime.Now;

        for (int i=0; i<(int)Limits.Maximum; i++)
            Table.Add( new T("String" + i.ToString(), i));

        DateTime BuildEnd = DateTime.Now;

        Console.WriteLine("Hash table build time: {0}", BuildEnd - BuildStart);

        DateTime SearchStart = DateTime.Now;

        for (int i = 0; i < (int)Limits.Maximum; i++)
        {
            T Found = Table["String" + i.ToString()];
        }

        DateTime SearchEnd = DateTime.Now;

        Console.WriteLine("Hash table search time: {0}", SearchEnd - SearchStart);
        
        Tree<string, T> Tree = new Tree<string, T>(new KeyComparer());

        DateTime TBuildStart = DateTime.Now;

        for (int i = 0; i < (int)Limits.Maximum; i++)
            Tree.Add(new T("String" + i.ToString(), i));

        DateTime TBuildEnd = DateTime.Now;

        Console.WriteLine("Tree build time: {0}", TBuildEnd - TBuildStart);

        DateTime TSearchStart = DateTime.Now;

        for (int i = 0; i < (int)Limits.Maximum; i++)
        {
            T Found = Tree["String" + i.ToString()];
        }

        DateTime TSearchEnd = DateTime.Now;

        Console.WriteLine("Tree search time: {0}", TSearchEnd - SearchStart);
    }
}

The results of the comparison are shown below.

Hash table build time: 00:00:00.1130759
Hash table search time: 00:00:00.0489658
Tree build time: 00:00:00.2501231
Tree search time: 00:00:00.5591980

As shown by the figures, hash tables can be an order of magnitude faster than binary trees on string searches.