跟线性数组和链表不同，HashTable是快速查找的数据结构。本文中的HashTable使用链表处理数组。

该HashTable可以指定table的长度，提供了遍历的方法。包括table的长度的选择也比较讲究。

	cp_int32 nPrime[MAX_HASH_PRIME_ARRAY_NUM] = {
		17,   
		37,   
		79,   
		163,  
		331,  
		673,  
		1361  
	};

下面是具体的代码贴出来，共大家参考。

代码中有个接口是查到多个key使用到了动态数组dyArray，参考上一篇点击打开链接

//
//  cpPlatform.h
//  dataStruct
//
//  Created by hherima on 14-7-29.
//  Copyright (c) 2014年 . All rights reserved.
//

#ifndef dataStruct_cpPlatform_h
#define dataStruct_cpPlatform_h

enum
{
    CP_FALSE  =   0,
    CP_TRUE    =  !CP_FALSE
};


#define  F_MALLOC_TYPE(s) (s*)f_malloc(sizeof(s))
#define  FREEFUN free
#define  MIN_PRE_ALLOCATE_SIZE 10  //The initial size of the dynamic array.
#define  MEMSETFUN      memset
#define  REALLOCFUN     realloc
#define  MALLOCFUN      malloc
#define  MEMCMPFUN      memcmp
#define  MEMCPYFUN      memcpy


typedef unsigned char cp_bool;
typedef signed int cp_int32;
typedef char cp_int8;
typedef unsigned int cp_uint32;


#endif

下面是hashtable的数据结构头文件

//
//  hashStruct.h
//  dataStruct
//
//  Created by hherima on 14-7-29.
//  Copyright (c) 2014年 . All rights reserved.
//

#ifndef dataStruct_hashStruct_h
#define dataStruct_hashStruct_h
#include <stdlib.h>
#include "cpPlatform.h"
#include "dyArray.h"

struct Node
{
    cp_int8* m_pKey; //the hash key.
    cp_int32 m_nKeyLength; // the length of the hash key in bytes.
    void* m_pVal;//hash_node value
    struct Node* m_pNext;
};//hash table，use link list to process conflict

struct HashTable
{
    cp_int32 m_nLength; //hash table's length.
    cp_int32 m_nEleNum; //hash table's element count.
    struct Node **m_ppHead;//the hash table's array to record all key's value.
};

cp_int32 GetHashFileNum(cp_int8* pKey, cp_int32 nKeyLength);

struct Node* HashFindOne(cp_int8* pKey,cp_int32 nKeyLength,struct HashTable *pTable);//search

cp_int32 HashFindMultkeyredund(cp_int8* pKey,cp_int32 nKeyLength,struct HashTable *pTable,struct DynamicArray *pdestArray);
void HashInsertOne(cp_int8* pKey,cp_int32 nKeyLength,void* pVal,struct HashTable *pTable);//insert
void HashInsertOneKeyredund(char* pKey,cp_int32 nKeyLength,void* pVal,struct HashTable *pTable);

void HashDelOne(struct HashTable * pTable,void (*pFreeFunc) (void *),cp_int8 *pKey,cp_int32 nKeyLength);

struct HashTable * HashTableCreate(cp_int32 nKeyNum);
struct Node* HashGetFirst(struct HashTable *pTable);
struct Node* HashGetNext(struct HashTable *pTable,cp_int8* pKey,cp_int32 nKeyLength);

cp_int32 HashGetLength(struct HashTable *pTable);
void HashTableVisit(struct HashTable * pTable,void (*pVisitFunc) (void *,void *),void *pAgent);
void HashTableReset(struct HashTable * pTable,void (*pFreeFunc) (void *));

void HashTableDestroy(struct HashTable * pTable,void (*pFreeFunc) (void *));

cp_int32 HashGetValue(cp_int8* pKey,cp_int32 nKeyLength,cp_int32 nTableLength);

#endif

//
//  hashStruct.c
//  dataStruct
//
//  Created by hherima on 14-7-29.
//  Copyright (c) 2014年 . All rights reserved.
//
#include "hashStruct.h"

#define MAX_HASH_PRIME_ARRAY_NUM    7
/**************************************************************************************************
 function name:
 HashGetValue
 description:
 the hash arithmetic to get the position of the certain key.
 parameter:
 pKey: the exclusive symbol which is related to a data block in hash table.
 nKeyLength: the key string's length.
 nTableLength: the hash table's length.
 return value:
 the position of the certain key.
 ***************************************************************************************************/

cp_int32 HashGetValue(cp_int8* pKey,cp_int32 nKeyLength,cp_int32 nTableLength)
{
	cp_uint32 h = 0;
	cp_uint32 g = 0;
    
	if(!pKey || nKeyLength<1 || nTableLength<1) //if the input parameter is invalid, return.
    {
        return -1;
    }
	while(nKeyLength--) // get each charactor and use it to compute hash value.
	{
		h = (h<<4) + *pKey++;
		g = h & 0xF0000000L;
		if(g)
		{
			h ^= g>>24;
		}
		h &= ~g;
	}
	return h % nTableLength;
}

/**************************************************************************************************
 function name:
 HashFindOne
 description:
 search the position's node of the certain key.
 parameter:
 pKey: the exclusive symbol which is related to a data block in hash table.
 nKeyLength: the key string's length.
 pTable: the hash table.
 return value:
 the node pointer or null.
 ***************************************************************************************************/

struct Node* HashFindOne(cp_int8* pKey,cp_int32 nKeyLength,struct HashTable *pTable)//search
{
    cp_int32 nPos = 0;
	struct Node* pCur = NULL;
    
    //if the input parameter is invalid, return.
	if(!pTable || !pKey || nKeyLength<1)
    {
        return NULL;
    }
    nPos = HashGetValue(pKey,nKeyLength,pTable->m_nLength);
    if(nPos>=0)
    	pCur = pTable->m_ppHead[nPos];
    //cur = table->head[hash_get_value(key,key_length,table->length)];
	while(pCur) // if has link list, visit all the list to find the right one.
	{
		if(pCur->m_nKeyLength == nKeyLength && MEMCMPFUN(pCur->m_pKey,pKey,nKeyLength) == 0)
		{
			return pCur;
		}
		pCur = pCur->m_pNext;
	}
	return NULL;
}

/**************************************************************************************************
 function name:
 HashFindMultkeyredund
 description:
 search the node of the certain key, there will be several one.
 parameter:
 pKey: the exclusive symbol which is related to several data block in hash table.
 nKeyLength: the key string's length.
 pTable: the hash table.
 pdestArray: the dynamic array which is used to save results and need be initilalized.
 return value:
 the node pointer or null.
 ***************************************************************************************************/

cp_int32 HashFindMultkeyredund(cp_int8* pKey,cp_int32 nKeyLength,struct HashTable *pTable,struct DynamicArray *pDestArray) //search ,the key is redundant.
{
	int nResNum = 0;
	struct Node* pCur = NULL;
    
    //if the input parameter is invalid, return.
	if(!pTable || !pKey || nKeyLength<1 || !pDestArray)
    {
        return -1;
    }
    pCur = pTable->m_ppHead[HashGetValue(pKey,nKeyLength,pTable->m_nLength)];
	while(pCur) //if has link list, visit all the list and find the right one.
	{
		if(pCur->m_nKeyLength == nKeyLength && MEMCMPFUN(pCur->m_pKey,pKey,nKeyLength) == 0)
		{
			DyArrayAppend(pDestArray, pCur->m_pVal); // put the right one to array.
			nResNum++;
			//return cur;
		}
		pCur = pCur->m_pNext;
	}
	return nResNum;
}

/**************************************************************************************************
 function name:
 hashExpand
 description:
 expand the array when it's too small.THIS FUNCTION CAN'T BE USED BECAUSE HASH VALUE IS
 CHANGED WHEN TABLE LENGTH CHANGED.
 parameter:
 pTable: the hash table.
 nNeed: the needed new size.
 return value:
 if succeed,return the true, else, return false.
 ***************************************************************************************************/

cp_bool HashExpand(struct HashTable * pTable, cp_int32 nNeed)
{
	cp_int32 i;
    struct Node ** pData = http://www.mamicode.com/NULL;>