散列

数据处理中数据匹配常用到Qmap和QHash。

QHash查找速度上显著于QMap

QHash以任意的方式进行存储，而QMap则是以key顺序进行存储。

散列表的实现常叫做散列（hashing），以常数平均时间插入、删除、查找。

散列原理：当输入一个关键字后，根据散列函数将其散列到表中一个位置，当位置冲突时，在该位置形成一个链表（分离链接法）；

散列实现：关键字%表的大小；

注意事项：表的大小一般应为素数，才能保证关键字尽量分散。（prime number：m不能被2 ~ √m 整除）

当关键字是数字时，直接与表的容量求余即可；

当关键字为字符串时，将其ASCII码值求和再与表的容量求余。但当表容量很大，而关键字很小时，就不能表尽其用。

一种可行的hashing实现方法如下：

int hash (const char *key , int tableSize)
{
     unsigned int hashVal = 0;
     while(*key != '')
     hashVal = (hashVal << 5) + *key++;
     return hashVal % tableSize;
}

解决冲突问题（分离链接法）：

声明：

struct listNode
{
       elementType  element;
       listNode     *next;
}
typedef listNode node;
struct hashTable
{
       int   tableSize;
       node  *theLists;   //theLists是数组，存放指向listNode结构指针  node*
}

分离链接散列表初始化：

hashTable initializeTable(int tableSize)  //tableSize为数据总量
{
        hashTable  *H;
        if(tableSize < minTableSize)
        {
              cout << "table size is too small" << endl;
              return NULL;
        }
        H = (hashTable*) New hashTable;
        if(H == NULL)
             cout << "out of space" << endl;
        H->tableSize = nextPrime(tableSize); //大于数据总量tableSize的最小素数设置为链表大小

        H->theLists = (node*)New node[H->tableSize];
        if(H->theLists == NULL)
             cout << "out of space"<< endl; 
        for(long i = 0; i < tableSize; i++)   //设置表头
             H->theLists[i]->next = NULL;
       
        return H;
}

分离链接散列表find：

node* find(elementType key , hashTable *H)
{
        node *P;
        node *L;
        L = H->theLists[hash(key , H->tableSize)];
        P = L->next;
        while(P != NULL && P->element != key)     //未找到就返回NULL
                 P = P->next;
        return P;
}

如elementType为字符串，则使用strcmp(str1 , str2)，当s1== s2时，返回值= 0。

while(p !=NULL && (! strcmp(key , H->tableSize))) 
      p = p->next;

分离链接散列表insert：（类似链表插入，前端插入方便就在前端插入）

void insert (elementType key , hashTable *H)
{
       node *tem , *newCell , *L;
       //判断key是否在散列表中，若在，不操作；若不在，则前端插入
       tem = find(key , H);      //tem == NULL，未找到key
       if(tem == NULL)
       {
           newCell = (node *)New node;
           if(newCell == NULL)
           {
               cout << "out of space" << endl;
               return NULL;
           }
           else
           {
                 L = H->theLists[hash(key , H->tableSize)];
                 newCell->element = key;
                 newCell->next = L->next;
                 L->next = newCell;
           }
       }      
}