讨论：对组集合 和 哈希表，性能比较如何？

Question

是不是使用哈希表开销要比对组集合大？to  junqiang(上帝，宽恕我吧)：你这么说的就不对了，不可能把所有事情都丢给计算机的升级换代。假如我这个选择是整个程序框架的核心代码，就体现的比较重大了，对系统性能的总体表现起着关键作用。刚刚昨晚写了一个无关紧要的的程序，当时比较累，编程时根本没有想太多事情。
我居然用一个DataAdapter一次Fill到一个DataTable里，
没什么？
我的机器是P4 1.7G 256DDR，一下子就玩完了。表有image大字段！

Answer 1

to  windinwing(潇笑) :哈希表的还是需要自己为Key订做一个哈希算法效率才高。而且不错哈希表索引是无开销的，
但计算索引的过程也要开销，如果算法不好还可能有键冲突。而且不知道哈希的空间开销如何。

Answer 2

说一下Hash Table这个数据结构，它叫哈希表，也有人叫它散列表，其工作原理是不是顺序访问，也不是随机访问，而是通过一个散列函数对其key进行计算，算出在内存中这个key对应的value的地址，而对其进行访问。好处是不管面对多大的数据，只需要一次计算就能找到其地址，非常的快捷，那么弊端是什么呢？当两个key通过散列函数计算出来的地址是同一个地址的时候，麻烦就来了，会产生碰撞，其的解决方法非常的麻烦，这里就不详细谈其解决方法了，否则估计再写个四，五章也未必谈得清楚，不过如果大家对其感兴趣的话，欢迎讨论。
　　嗯，我们将用散列表来对游戏中的物件进行索引，具体怎么做呢？首先，在内存池中申请一块两倍大于游戏中物件总数的内存，为什么是两倍大呢？防止散列表碰撞。然后我们选用物件的名称作为散列表的索引key，然后就可以开始设计散列函数了。下面来看个例子：　　static int T[] =
　　{
　　　　1, 87, 49, 12, 176, 178, 102, 166, 121, 193, 6, 84, 249, 230, 44, 163,
　　　　14, 197, 213, 181, 161, 85, 218, 80, 64, 239, 24, 226, 236, 142, 38, 200,
　　　　110, 177, 104, 103, 141, 253, 255, 50, 77, 101, 81, 18, 45, 96, 31, 222,
　　　　25, 107, 190, 70, 86, 237, 240, 34, 72, 242, 20, 214, 244, 227, 149, 235,
　　　　97, 234, 57, 22, 60, 250, 82, 175, 208, 5, 127, 199, 111, 62, 135, 248,
　　　　174, 169, 211, 58, 66, 154, 106, 195, 245, 171, 17, 187, 182, 179, 0, 243,
　　　　132, 56, 148, 75, 128, 133, 158, 100, 130, 126, 91, 13, 153, 246, 216, 219,
　　　　119, 68, 223, 78, 83, 88, 201, 99, 122, 11, 92, 32, 136, 114, 52, 10,
　　　　138, 30, 48, 183, 156, 35, 61, 26, 143, 74, 251, 94, 129, 162, 63, 152,
　　　　170, 7, 115, 167, 241, 206, 3, 150, 55, 59, 151, 220, 90, 53, 23, 131,
　　　　125, 173, 15, 238, 79, 95, 89, 16, 105, 137, 225, 224, 217, 160, 37, 123,
　　　　118, 73, 2, 157, 46, 116, 9, 145, 134, 228, 207, 212, 202, 215, 69, 229,
　　　　27, 188, 67, 124, 168, 252, 42, 4, 29, 108, 21, 247, 19, 205, 39, 203,
　　　　233, 40, 186, 147, 198, 192, 155, 33, 164, 191, 98, 204, 165, 180, 117, 76,
　　　　140, 36, 210, 172, 41, 54, 159, 8, 185, 232, 113, 196, 231, 47, 146, 120,
　　　　51, 65, 28, 144, 254, 221, 93, 189, 194, 139, 112, 43, 71, 109, 184, 209,
　　};　　// s是需要进行索引的字符串指针，maxn是字符串可能的最大长度，返回值是相对地址。
　　inline int whashstr(char *s, int maxn)
　　{
　　　　register unsigned char oh, h;
　　　　register unsigned char *p;
　　　　register int i;　　　　if (!*s)
　　　　　　return 0;
　　　　p = (unsigned char *) s;
　　　　oh = T[*p]; h = (*(p++) + 1) & 0xff;
　　　　for (i = maxn - 1; *p && --i >= 0; )
　　　　{
　　　　　　oh = T[oh ^ *p]; h = T[h ^ *(p++)];
　　　　}
　　　　return (oh << 8) + h;
　　}　　具体的算法就不说了，上面的那一大段东西不要问我为什么，这个算法的出处是CACM 33-6中的一个叫Peter K.Pearson的鬼子写的论文中介绍的算法，据说速度非常的快。有了这个散列函数，我们就可以通过它来对世界里面的任意物件进行非常快的寻址了。http://bbs.getdns.net/NowTopic.aspx?forum=23&forumpage=1&topic=11035 

Answer 3

谢谢，windinwing(潇笑) ，到过你说的网站，看了你的文章，写的很好，得益菲浅你的文章也说到 了，
该散列表的需要2倍物件个数的空间，
而且物件的排放是不紧凑的（散列嘛），
那说明无论何时都要预备着所须空间，即使用不着，更何况有时我们甚至不知道需要多大的空间,然后我们又需要处理动态增长问题。
（好象这类问题在.net 下已经没有人再去忧心）而C++下键值对集合的一个实现std::map<>采用平衡二叉树的存储策略，物件查找速度较快，性能很稳定。而且没有无用空间开销，(可惜要存储Key)。所以在数据量少、不确定的时候，（现在我面对的问题就是）对他们的选择很是犹豫。潇笑，你能在谈多一点，帮我解惑么？我已经在你的网站注册了，id=hyifeng，多多指教啊，
你的文章写得很好，好久没有看到过这么有活力的文章了。
谢谢先。

Answer 4

TO: hyifeng(进步！进步！) 
  有些文章是我转帖的啊， 说的我好没面子 
   游戏中当然了，因为查找用的非常频繁 ，  private struct bucket;  哈希类
  .net中实现方式应该不太一样了
  private bucket[] buckets;
 public virtual void Add(object key, object value)
{ this.Insert(key, value, 1);
 
} private void Insert(object key, object nvalue, bool add)
{ uint num1;
uint num2;
uint num3;
int num4;
int num5;
int num6;
object[] array1;
if (key == null)
{
 throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
 
}
if (this.count >= this.loadsize)
{
 this.expand();
 
}
else
{ if ((this.occupancy > this.loadsize) && (this.count > 100))
{
 this.rehash();
 
}
 
}
num3 = this.InitHash(key, this.buckets.Length, &(num1), &(num2));
num4 = 0;
num5 = -1;
 
L_0065:
 num6 = (num1 % this.buckets.Length);
if (((num5 == -1) && (this.buckets[num6].key == this.buckets)) && (this.buckets[num6].hash_coll < 0))
{
 num5 = num6;
 
}
if ((this.buckets[num6].key == null) || ((this.buckets[num6].key == this.buckets) && ((((long) this.buckets[num6].hash_coll) & ((ulong) -2147483648)) == ((long) 0))))
{
 if (num5 != -1)
{
 num6 = num5;
 
}
this.buckets[num6].val = nvalue;
this.buckets[num6].key = key;
this.buckets[num6].hash_coll = (this.buckets[num6].hash_coll | num3);
this.count = (this.count + 1);
this.version = (this.version + 1);
return; 
}
if ((((long) (this.buckets[num6].hash_coll & 2147483647)) == ((ulong) num3)) && this.KeyEquals(key, this.buckets[num6].key))
{
 if (add)
{
 array1 = new object[2];
array1[0] = this.buckets[num6].key;
array1[1] = key;
throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", array1));
 
}
this.buckets[num6].val = nvalue;
this.version = (this.version + 1);
return; 
}
if ((num5 == -1) && (this.buckets[num6].hash_coll >= 0))
{
 this.buckets[num6].hash_coll = (this.buckets[num6].hash_coll | -2147483648);
this.occupancy = (this.occupancy + 1);
 
}
num1 = (num1 + num2);
num4 = (num4 + 1);
if ((num4 + 1) < this.buckets.Length)
{
 goto L_0065;
 
}
if (num5 != -1)
{
 this.buckets[num5].val = nvalue;
this.buckets[num5].key = key;
this.buckets[num5].hash_coll = (this.buckets[num5].hash_coll | num3);
this.count = (this.count + 1);
this.version = (this.version + 1);
return; 
}
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_HashInsertFailed"));
 
}private uint InitHash(object key, int hashsize, [out] ref uint seed, [out] ref uint incr)
{ uint num1;
num1 = (this.GetHash(key) & 2147483647);
seed = num1;
incr = (1 + (((seed >> 5) + 1) % (hashsize - 1)));
return num1; 
} 
protected virtual int GetHash(object key)
{ if (this.hcp != null)
{
 return this.hcp.GetHashCode(key); 
}
return key.GetHashCode(); 
} 
 protected IHashCodeProvider hcp { get; set; }

Answer 5

如果可以确定 集合元素在1 之 50（基本上） 之间，你仍然回采用 hashtable 吗？

Answer 6

我最近在用C#写游戏服务器呀 ， 所以帖写文章自已找的时候也方便些了
   我觉得在少量数据下使用什么都无所谓了，那么一点的性能影响根本看不出来的
   
   我觉得哈希应该用在占用较多资源的实例对象上了， 
     比如以下代码  一个主循环监听连入的网络请求 ..
    private Hashtable   m_SessionTable = null; /// <summary>
/// 主消息循环
/// </summary>
private void Run()
                   {
               ........  
        Socket clientSocket = Game_Listener.AcceptSocket(); //监听套接字 
             .............
string sessionID = clientSocket.GetHashCode().ToString();//取得客户连接的哈希值         Game_Session session = new Game_Session(clientSocket,this,sessionID,logWriter);   //实例会话对象

Thread clientThread = new Thread(new ThreadStart(session.StartProcessing));  //会话线程  AddSession(sessionID,session,logWriter); //增加ID,Session，第三个参数是记录日志用      //然后启动线程等其他处理
                   } internal void AddSession(string sessionID,Game_Session session,_LogWriter logWriter)
{ 
m_SessionTable.Add(sessionID,session); if(m_LogCmds)
{
logWriter.AddEntry("----- 系统: 'Session:'" + sessionID + " 连线 " + DateTime.Now);
}
}
     
       通过哈希表检索对象 internal bool IsUserLoggedIn(string userName)
{
lock(m_SessionTable)//访止意外，先锁定
{
foreach(Game_Session sess in m_SessionTable.Values)
{
if(sess.UserName == userName)
{
return true;
}
}
}

return false;
}   可能过通过事件等传递到其他对象 .当然用数组也可以实现了public event LogEventHandler SessionLog = null;
private void Game_Server_SessionLog(object sender,Xiaoxiao.GameServer.Log_EventArgs e)
{   Game_Session session = (Game_Session)sender;  ........
}
   主要是哈希用起来方便吧 只需Remove(); add();就是了
   如果经常更改的数组，用哈希好了，或包含实例对象的，
  
    我的理解是哈希表本身并不代表什么， 只是保存了键值对，用于快速索引
   而数组本身就是一种类弄。  前者在更改和检索时很方便，会有一些额外的
   开销 .  但很小      我的理解

Answer 7

http://game.getdns.net/c.JPG  
  就这个例子的  呵   多谢支持了  提供一个FTP资源交流用
 ftp://games:[email protected]

Answer 8

OK,
谢谢潇笑)，ftp://games:[email protected] 里好眩 ^-^如果没有人发言就结了。