哈希查找：又称散列查找
哈希表：根据关键字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 <stdio.h> #include <iostream> #include <stdlib.h> 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指针都指向NULL HashRootPtr InitHashTableHeader(void) { HashRootPtr node; node = (HashRootPtr)malloc(sizeof(HashRootPtr)); node->next = NULL; return node; } void InitHashTable(void) { for (int i=0; i<HASH_TABLE_LEN; ++i) { HashTable[i] = InitHashTableHeader(); HashTable[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!"<<endl; } else { //key是根节点 if (node->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<HASH_TABLE_LEN; ++i) { node = HashTable[i]->next; while(node != NULL) { num++; node = node->next; } } return num; } void PrintHashTable(void) { cout<<"Current Hash Table:"<<endl; HashNodePtr node; int num = GetNodeNumberOfHashTable(); for (int i=0; i<HASH_TABLE_LEN; ++i) { node = HashTable[i]->next; if (node == NULL) { continue; } else { while(node != NULL) { cout<<node->key<<' '<<node->data<<endl; node = node->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<<node->data<<endl; key = 15; DeleteHashNode(key); PrintHashTable(); }
参考资料：http://wenku.baidu.com/view/7dc7080bf78a6529647d5339