日期:2014-05-20  浏览次数:20815 次

诡异的Hashtable
工作之余,本人想验证测试Hashtable迭代时是按什么顺序输出的.结果却令人费解.
废话不说,先贴代码.
C# code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //测试A
            Hashtable hashA = new Hashtable();
            hashA.Add("first", "顺序1");
            hashA.Add("third", "顺序2");
            hashA.Add("second", "顺序3");
            Console.WriteLine("HashtableA");
            foreach (string key in hashA.Keys)
            {
                Console.WriteLine("key:{0}--value:{1}", key, hashA[key].ToString());
            }
            //结果
            // key:first--value:顺序1
            // key:third--value:顺序2
            // key:second--value:顺序3
            //断言A:Hashtable的迭代与添加键值对时的先后关系有关。

            //测试B
            Hashtable hashB = new Hashtable();
            hashB.Add("1", "顺序1");
            hashB.Add("3", "顺序2");
            hashB.Add("2", "顺序3");
            Console.WriteLine("HashtableB");
            foreach (string key in hashB.Keys)
            {
                Console.WriteLine("key:{0}--value:{1}", key, hashB[key].ToString());
            }
            //结果
            // key:1--value:顺序1
            // key:2--value:顺序3
            // key:3--value:顺序2
            //断言B:居然按键的顺序输出的?推翻断言A.

            //测试C
            Hashtable hashC = new Hashtable();
            hashC.Add("1", "顺序1");
            hashC.Add("6", "顺序2");
            hashC.Add("3", "顺序3");
            Console.WriteLine("HashtableB");
            foreach (string key in hashC.Keys)
            {
                Console.WriteLine("key:{0}--value{1}", key, hashC[key].ToString());
            }
            //结果
            // key:6--value:顺序2
            // key:1--value:顺序1
            // key:3--value:顺序3
            //断言C:无语中....猜测会不会按HashCode输出的,决定输出HashCode看看

            Console.WriteLine("输出各个key的HashCode");

            Console.WriteLine("1: {0}","1".GetHashCode());
            Console.WriteLine("2: {0}", "2".GetHashCode());
            Console.WriteLine("3: {0}", "3".GetHashCode());
            Console.WriteLine("6: {0}", "6".GetHashCode());
            //结果
            //1: -842352753
            //2: -842352754
            //3: -842352755
            //6: -842352758

            //再输出以组合字符串的key
            Console.WriteLine("输出各个HashA中key的HashCode");
            Console.WriteLine("first: {0}", "first".GetHashCode());
            Console.WriteLine("third: {0}", "third".GetHashCode());
            Console.WriteLine("second: {0}", "second".GetHashCode());
            //结果
            //first: -1920740948
            //third: -1952578413
            //second: -792817032
            //直接昏菜。。
            //备注:经测试,使用int型作为key时,迭代时一定会按key的降序输出value.
        }
    }
}


诡异:Hashtable进行迭代时,到底是按什么输出的?

------解决方案--------------------
根据 http://msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx#datastructures20_2_topic5

hash function不是简单的 H(key) = GetHash(key)
而是
H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize
或者
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize



------解决方案--------------------
探讨
根据 http://msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx#datastructures20_2_topic5