哈希查找：又称散列查找

哈希表：根据关键字k，使用哈希函数i=f(k)，计算出存储位置。

（1）哈希函数是一个映像，将关键字集合映射到地址集合上；

（2）哈希函数是压缩映像，可能产生冲突，即k1 != k2, 而f(k1)=f(k2)，只能改进哈希函数减少冲突。

因此，一是要使用合适的哈希函数，二是选择冲突处理方法。

 

使用数组存储：

给定数列：{ 22,41,53,46,30,13,1,67 }

哈希函数：H(key) = key MOD 8 

线性探测解决冲突：Hi=(H(key)+di) MOD m ,di=1,2,…,m-1

使用链表：

编程：使用链表实现哈希表的创建、查询和删除。

#include 
      
       #include 
       
        #include 
        
         using namespace std;#define HASH_TABLE_LEN  100  typedef struct _HashNode{    int key;    int data;    _HashNode *next;}HashNode,*HashNodePtr;typedef struct _HashRoot{    HashNode *next;}HashRoot,*HashRootPtr;//哈希表：表中每个元素是指向HashNode的一个指针HashRootPtr HashTable[HASH_TABLE_LEN];//添加节点时，动态分配空间HashNodePtr InitHashNode(void){    HashNodePtr node;    node = (HashNode *)malloc(sizeof(HashNode));    node->next = NULL;    return node;}//初始化哈希表，表中每个HashNode指针都指向NULLHashRootPtr InitHashTableHeader(void){    HashRootPtr node;    node = (HashRootPtr)malloc(sizeof(HashRootPtr));    node->next = NULL;    return node;}void InitHashTable(void){    for (int i=0; i
         
          next = NULL;    }}//哈希函数：根据关键字获得在哈希表中的位置int GetHashPosition(int key){    int pos = 0;      pos = key % HASH_TABLE_LEN;      return pos;  }//添加节点void AddHashNode(HashNodePtr new_node){    HashNodePtr node;    int pos = 0;    new_node->next = NULL;    pos = GetHashPosition(new_node->key);    //如果哈希表当前位置还没有值    if (HashTable[pos]->next == NULL)    {        HashTable[pos]->next = new_node;    }    //若根据哈希函数计算得到的位置相同，并且已经有节点，添加在该节点之后    else    {        node = HashTable[pos]->next;        while(node->next != NULL)        {            node = node->next;        }        node->next = new_node;    }}//查找节点：root=1，说明是根节点HashNodePtr SearchHashNode(int key, int *root){    HashNodePtr node;    int pos = 0;    pos = GetHashPosition(key);    node = HashTable[pos]->next;    //空，说明该位置没有节点，没有关键字为key的节点    if (node == NULL)    {        return 0;    }    //key是根节点    if (node->key == key)    {        *root = 1;        return node;    }    //key不是根节点    else    {        *root = 0;        while(node->next != NULL)        {            if (node->key == key)            {                return node;            }             else            {                node = node->next;            }        }        return 0;    }}//删除节点void DeleteHashNode(int key){    int pos = GetHashPosition(key);    HashNodePtr node, node_former;    node = HashTable[pos]->next;    //空，说明该位置没有节点，没有关键字为key的节点    if(node == NULL)    {        cout<<"Current node does not exist!"<
          
           key == key)        {            HashTable[pos]->next = node ->next;            free(node);        }        else        {                    //key不是根节点，遍历该支链，保存该节点、该节点前面的节点            while(node != NULL && node->key != key)            {                node_former = node;                node = node->next;            }            if(node->key == key)            {                node_former->next = node->next;                free(node);            }        }    }    }int GetNodeNumberOfHashTable(void){    HashNodePtr node;    int num = 0;    for(int i=0; i
           
            next; while(node != NULL) { num++; node = node->next; } } return num;}void PrintHashTable(void){ cout<<"Current Hash Table:"<
            
             next; if (node == NULL) { continue; } else { while(node != NULL) { cout<
             
              key<<' '<
              
               data<
               
                next; } } }}void main(){ HashNodePtr node; InitHashTable(); node = InitHashNode(); node->key = 1; node->data = 11; AddHashNode(node); node = InitHashNode(); node->key = 2; node->data = 22; AddHashNode(node); node = InitHashNode(); node->key = 3; node->data = 33; AddHashNode(node); node = InitHashNode(); node->key = 4; node->data = 44; AddHashNode(node); node = InitHashNode(); node->key = 104; node->data = 144; AddHashNode(node); node = InitHashNode(); node->key = 5; node->data = 55; AddHashNode(node); node = InitHashNode(); node->key = 105; node->data = 155; AddHashNode(node); PrintHashTable(); int key = 4; int root = 0; node = SearchHashNode(key, &root); cout<
                
                 data<
                
               
              
             
            
           
          
         
        
       
      

 

参考资料：http://wenku.baidu.com/view/7dc7080bf78a6529647d5339