学步园

/*********************************************************************
                                     哈希表的实现
     建立哈希表是为了消除通过遍历比较来搜索键带来的时间浪费。如果想在
一个表中直接地找到记录，记录的存储位置和它的关键字之间建立一个确定的对
应关系f()，使每个关键字和结构中一个唯一的存储位置相对应。这便是哈希表
的快速查找原理。
     哈希表的构造方法(即寻找键和结构数组间的函数关系)有：ASCII转换直接
相加法，取模法(表长为质数较优)，平方取中法，拆项法，折叠法，随机数法等。
     哈希表冲突的处理方法：开放定址法(线性探测再散列，二次探测再散列，
伪随机探测再散列)；再哈希法；创建链表法；建立公共溢出区等.
     由于哈希函数和哈希表冲突的处理方法是哈希表效率的关键，所以一定要根
据不同应用场合慎重选择。

     搜索哈希表的时间复杂度与记录数n无关,所以适合处理记录数量很大的数据.
                                                 Leo,2011/10/19
                                        

                             
************************************************************************/

 /*        以下仅为实现哈希表的描述,代码不保证能运行         */

 

 

typedef Hash{
        ListElem    HashArray[MAXHASHTABLE];
        int         count;
        }HashTable;
       

/*CreateHash:create a table not any entry        */
void CreateHash(HashTable ht)
{
    int i;
    for(i=0;i<MAXHASHTABLE;i++)
        ht->HashArray[i]=ONELEM;
    ht->count=0;
}

 

 

/*SearchHash:Search a entry from a HashTable
    pre:HashTable have been Create;
    post:return the key position in HashTable.
    uses: Hash() to get a position in the table.
*/
Boolean SearchHash(KeyType key,HashTable *ht)
{
    Position    pos;
    int         index;
    int         count;
    pos=Hash(key);
    if(ht->HashArray[pos].key == key)
        return TRUE;
    else for(index=1,count=1;count < MAXHASHTABLE;count++)
            {
             pos=(pos+index)/MAXHASHTABLE;
             if(ht->HashArray[pos].key == key)
                return TRUE;
             index+=2;
            }
    return FALSE;
}

/*InsertHash:insert a elem to a hashtable
    pre:the hashtable have been create.
    post:the entry has been inserted to the table,and return the position
         where it inserted.
    uses:Hash() to get a position in the table.     */

Position InsertHash(ListElem entry;HashTable ht)
{
    Position    pos;
    int         index;
    int         count;
    pos=Hash(entry.key);
    index=count=1;
    while(ht->HashArray[pos].key != ONELEM)/* if have entry in  HashArray[pos]*/
        {
         pos=(pos+index)/MAXHASHTABLE;
         index+=2;
         if(++count >= MAXHASHTABLE)
            return UNFIND;
        }
    ht->count++;
    return pos;
}