学步园

  哈希表是种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。

　　对哈希表的使用者一一人来说，这是一瞬间的事。哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

　　哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

　　而且，也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。

然而如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

  下面在哈希表在SIP电话中用于存储当前在前用户的信息（用户信息已经在初始化是保存在全局变量的一个链表中,文中有说明，在线用户需要时刻和控制台进行交互（比如通话、占线）所有要求速度快），废话不多说直接分析代码吧～

头文件：

#ifndef _HASH_H
#define _HASH_H

#define OK 		1
#define ERROR 	0

#define HASH_SIZE             256

typedef struct _hashNode /*采用双向链表存储*/
{	
	struct _hashNode * next;
	struct _hashNode * prev;
	
} tHashNode;
tHashNode * vSipUserLocation[ HASH_SIZE ];/*槽*/

#endif

哈希表算法（字符串处理）

int hashString (const char *str)
{
    unsigned int h=0;
    int len;
    int i;

    len = strlen(str);
    if (len <= 0 || len > HASH_SIZE)
        return -1;

    for (i = 0; i < len; i++) {
        h = ( h << 5 ) - h + *(str + i);
    }

    return h % HASH_SIZE;
}
哈希槽的初始化

int hashInit(tHashNode **pList, unsigned int size)
{    
    if ( !pList )
        return ERROR;    
    memset(pList, '\0', size);
    return OK;
}

插入节点
int  hashAddNode ( tHashNode ** pList,  tHashNode * pNode,  char *hash, func  pCmpFunc  ) 
{
    int index;
    tHashNode *tempNode = NULL;
    int ret;

    if ( !pList || !pNode || !hash )
        return ERROR;
 
    index = hashString( hash ) ;
    if ( index < 0 )
        return ERROR;

    /* 首个节点     */
    tempNode =  pList [ index ] ;
    if( !tempNode ) { 
        pList [ index ] = pNode;
        pNode->next = NULL ;
        pNode->prev = NULL;
        return OK ;
    }
    /* 遍历是否有相同的节点 函数Pcmpfunc（）是比较指针是否指向相同的内存地址*/
    if( pCmpFunc ) {
        for( ; tempNode != NULL ; tempNode = tempNode->next )
        {
            if((ret = pCmpFunc(tempNode, pNode, 0)) == 0)
                break;
        }
 
        if ( ret == 0 )
            return OK ;
    }

    /*为找到相同的节点，插入到第一个节点位置 */
    tempNode = pList [ index ] ;
    pList [ index ]  = pNode ;
    pNode->next = tempNode;
    pNode->prev = NULL;
    tempNode->prev = pNode;
 
    return OK ;
}

 关于插入节点中的参数应用，在代码中调用函数如下:

typedef struct _Callee {	
    tHashNode pNode;
    char name[24];
    struct _Callee *next;
}Callee

 Callee *p ;

p 是指向一个全局变量 （链表，存放系统设置的所有用户的信息）中的一个节点，保存用户信息（我这里进行了修改，只显示一部分内容）。而哈希表存放的是当前在线用户，当用户注册是需要加入哈希表中。

hashAddNode(vSipUserLocation, (tHashNode *)p, p->name, issamecallee)

下面是和别人沟通：

A：

这个问题我也遇到了，因为tSipCallee *p ,这个p指向的是存储tSipCalle结构的内存地址，这个地址指向的内存是一块连续的空间，比如大小是n，那么我们可以很随意的取这n个字节中的一段内容，也就是说sizeof(tHashNode)<=sizeof(Callee)，把n中的前m（<=n）个字节当成tHashNode 的内容，也就是说可以把这m个字节当成一个tHashNode结构体
但是如果sizeof(tHashNode)>sizeof(Callee),那就不行了，会造成访问越界的情况

B：

定义这个结构体的时候已经包含这个 tHasgNode pNode;
太抽象了～

A：对哈，我给你画个图你就明白了

B：看来你看得挺多了，刚开始我迷糊在(tHashNode *)p ，强制类型转换，不就把P中前2个字节内容覆盖掉了！

A：

你看看这个结构，tSipCallee在内存中的存放方法，强制转换的意思就是“我”只想使用前一段字节：sizeof（tHashNode），后面是什么我不管。

通过data查找节点

tHashNode * hashGetNode(tHashNode ** pList, char *hash,  func  pCmpFunc, void * cmpArg)
{
    int index;
    tHashNode *tempNode = NULL;

    if ( !pList ||  !hash || !pCmpFunc )
        return NULL;
    index = hashString( hash ) ;
    if ( index < 0 )
        return NULL;

    tempNode =  pList [ index ] ;
    while (tempNode ) {/*查找参数 cmoArg是否在节点tempNode中保存）
        if ( pCmpFunc ( tempNode, NULL, cmpArg ) == 0 ) {
            break;
        }
        tempNode = tempNode->next;
    }
    return tempNode;
}

获得当前列内容：

tHashNode * hashGetSlot(tHashNode ** pList, const char *hash )
{
    int index;
    if ( !pList || !hash )
        return NULL;
    index = hashString( hash );
    if( index < 0 )
        return NULL;
    return pList[ index ];
}

删除节点

int hashRemoveNode(tHashNode ** pList, tHashNode * pNode, char *hash)
{
    int index;
    
    if ( !pList || !pNode || !hash )
        return ERROR ; 

    index = hashString( hash ) ;
    if ( index < 0 )
        return ERROR;
  
    if(!pNode->prev) { /* 第一个节点 */
        pList[index] = pNode->next;
        if(pNode->next)
            pNode->next->prev = NULL;		
    }else if ( !pNode->next ) { /* 下一个节点 */
        pNode->prev->next = NULL;
    }else {
        pNode->prev->next = pNode->next;
        pNode->next->prev = pNode->prev;
    }
    return OK;		
}

哈希表是处理大量数据中因处理速度比较快，应用非常广泛。但是也不难理解，只有认真阅读代码，