ArrayList和Hashtable

最近看数据结构的时候在想为什么.Net的Hashtable的key和value都是object，而且没有泛型的版本。直道自己动手练习，才发觉其中奥妙。没有泛型的原因简而言之就是用泛型的话Collision就不好处理了。（不好处理不等于不能处理，就是处理起来明显太麻烦了。)
为Hashtable做铺垫的ArrayList（这个是我蓄意写的泛型版本）：
一点就能看，不想看别点

    class MyArrayList< T >
    {
        private const int INIT_SIZE = 2;

        public int Length { get; private set; }
        public int Capacity { get; private set; }

        private T[] array;

        public MyArrayList():this(INIT_SIZE)
        {
        }

        private MyArrayList(int size)
        {
            array = new T[size];
            this.Length = 0;
            this.Capacity = size;
        }

        public T this[int i] {
            get
            {
                if (i < 0 || i > this.Length - 1)
                    throw new IndexOutOfRangeException();

                return this.array[i];
            }
        }

        private void CheckCapcity()
        {
            if (this.Length >= this.Capacity)
            {
                if (this.Length == int.MaxValue)
                    throw new OverflowException();

                int i = this.Length - 1;

                if (this.Length < int.MaxValue / 2)
                {
                    this.Capacity *= 2;
                }
                else
                {
                    this.Capacity = int.MaxValue;
                }
                Debug.Print("Expand to {0}", this.Capacity);
                T[] newArray = new T[this.Capacity];
                while (i >= 0)
                {
                    newArray[i] = array[i];
                    i--;
                }
                this.array = newArray;

                GC.Collect();
            }
        }

        public void Add(T t)
        {
            this.CheckCapcity();
            this.array[this.Length++] = t;
        }

        public T[] ToArray()
        {
            T[] a = new T[this.Length];
            for (int i = 0; i < this.Length; i++)
            {
                a[i] = this.array[i];
            }
            return a;
        }

        public void Remove(int position)
        {
            if (position < 0 || position >= this.Length)
            {
                throw new IndexOutOfRangeException();
            }

            for (int i = position; i < this.Length - 1; i++)
            {
                this.array[i] = this.array[i + 1];
            }
            this.Length--;
        }

        public void Clear()
        {
            for (int i = 0; i < this.Length; i++)
            {
                this.array = null;
            }

            this.Length = 0;
        }
    }

以下为一个Hashtable：

    class MyHashtable
    {
        private MyArrayList< object > keys;
        private ValueChain[] values;

        private class ValueChain
        {
            public object Value { get; set; }
            public object Key { get; set; }
            public ValueChain next;

            public ValueChain(object key, object value)
            {
                this.Key = key;
                this.Value = value;
                this.next = null;
            }
        }

        //Apparently this is way too samll, it can ensure that Collision happens.
        private const int SIZE = 4;
        private MyHashtable(int size)
        {
            this.keys = new MyArrayList< object >();
            this.values = new ValueChain[size];
        }

        public object[] Keys
        {
            get
            {
                return this.keys.ToArray();
            }
        }

        public object[] Values
        {
            get
            {
                MyArrayList< object > values = new MyArrayList< object >();
                foreach (object k in this.Keys)
                {
                    values.Add(this[k]);
                }
                return values.ToArray();
            }
        }

        public object this[object k]
        {
            get
            {
                int h = hash(k);
                if (this.values[h] == null)
                {
                    throw new IndexOutOfRangeException();
                }
                else
                {
                    ValueChain p = this.values[h];
                    while (p != null)
                    {
                        if (p.Key == k)
                            return p.Value;
                        p = p.next;
                    }
                    throw new IndexOutOfRangeException();
                }
            }
            set
            {
                this.Add(k, value);
            }
        }

        public MyHashtable()
            : this(SIZE)
        {

        }

        public void Add(object key, object value)
        {
            int h = hash(key);
            ValueChain  v = new ValueChain(key, value);
            if (values[h] == null)
            {
                values[h] = v;
                keys.Add(key);
            }
            else
            {
                ValueChain p = values[h];
                ValueChain q = null;
                while (p != null)
                {
                    if (p.Key == key)
                    {
                        p.Value = value;
                        return;
                    }
                    q = p;
                    p = p.next;
                }
                q.next = v;
                keys.Add(key);
                Debug.Print("Collision: {0}", key);
            }
        }

        private int hash(object key)
        {
            //Obviously, this is a dumb idea.
            return Math.Abs(key.GetHashCode()) % SIZE;
        }
    }

很明显的一点就是在比较Key的时候泛型就不管用了，这个时候要么用IComparable和IComparer两个接口，要么就用object一了百了。显然图省事就是object啦~