HashTable 构建与思考

1)

typedef struct hashnode_struct{

struct hashnode_struct *next;

const char *key;

void *val;

}* hashnode, _hashnode;

 

_hashnode obj;

hashnode p = &obj;  p是一个指针

 

HashTable.c:201: warning: control reaches end of non-void function

它的意思是：控制到达非void函数的结尾。就是说你的一些本应带有返回值的函数到达结尾后可能并没有返回任何值。这时候，最好检查一下是否每个控制流都会有返回值。

assignment makes pointer from integer without a cast

 

 

 

◆犯了一个愚蠢的错误:

◆   int i=1; i<<2;  得出的值为4, 但是i本身的值还是1，4是表达式i<<2的值 我一直以为i被修改了

 

 

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h> 

#ifndef __GHASH_H_
#define __GHASH_H_

#define D_HASHSIZE 512
typedef struct ST_Node
{
   char * key;
   char * value;
   struct ST_Node * next;
} Node;



void HashInit();
Node *  HashInsert(char * key, char * value);
int  HashRemove(char * key);
Node *  HashSearch(char * key);
void FreeGHash();
void HashTraversal();

#endif
 


static Node* hashtab[D_HASHSIZE];
 

void HashInit()
{
 	 int i=0;
 	 for(i=0; i<D_HASHSIZE; i++)
 	 {
	  	hashtab[i]=NULL;
     }
}

Node *  HashInsert(char * key,char * value)
{
 	 Node * np;
 	 unsigned int hashval;
 	 if((np=HashSearch(key))==NULL) /*如果没有相同的key则直接插入*/
 	 {
         np=(Node *)malloc(sizeof(Node));
         if(NULL==np || NULL ==(np->key = strdup(key))  	 /*strdup:复制一个字符串副本*/
					 || NULL ==(np->value = strdup(value)) 
		   )
         {
             return NULL;
         }
         hashval = _Hash(key);
         np->next = (Node *)hashtab[hashval]; /*解决不同的key算出相同hash值的collision*/
         hashtab[hashval] = np;
     }
     else	/*如果有则覆盖*/
     {
	  	 free(np->value); 
	  	 if((np->value=strdup(value))== NULL)
	  	 {
		    return NULL;
         }
 	 }
 	 return np;
}


int  HashRemove(char * key)
{
	Node * np = NULL;
	np = HashSearch(key);
    if(np == (Node *)hashtab[_Hash(key)]) /*如果是数组所指向的链表的头指针则让数组指向next*/
    {
        freeNode(np);
        hashtab[_Hash(key)] = np->next;
    }

	  
	return 0; /*正常返回0*/
}

/*
	确保_Hash(key) 值相同
	&& key字符串也相同
	return: 所定位的指针
*/
Node *  HashSearch(char * key)
{
    Node  *np;

    for(np = (Node *)hashtab[_Hash(key)]; /*定位HashTable所指向的链表 进行循环比较*/
        np != NULL;
        np = np->next)
      if(strcmp(key, np->key) == 0) 
           return np;
    return NULL;
}

void FreeGHash()
{ 
 	 for(int i=0; i<D_HASHSIZE; i++)
 	 {
	     if(hashtab[i]!=NULL)
	     {
		    Node * tmp;
		    Node * deln;
		    for(tmp=hashtab[i]; tmp!=NULL; tmp=hashtab[i])
		    {
			     hashtab[i]=tmp->next;
			     freeNode(tmp);
			}
		 }
     }
}

void HashTraversal()
{
     printf("Print Hash:\n");
     int i=0;
     for(i=0; i<D_HASHSIZE; i++)
     {
         if(hashtab[i] !=NULL )
         {
            printf("%d---",i);
            Node * tmp;
            for(tmp=hashtab[i]; tmp!=NULL; tmp=tmp->next)
            {
                 printf("%s ==> %s;",tmp->key,tmp->value);
            }
            printf("\n");
         }
     }
}   

static unsigned int _Hash(char *key)
{
    return _ELFHash(key)%D_HASHSIZE;
}

// ELF Hash Function
static unsigned int _ELFHash(char *str)
{
       unsigned int hash = 0;
       unsigned int x = 0;

       while (*str)
      {
           hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash
           if ((x = hash & 0xF0000000L) != 0)
           {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。

           //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位
           hash ^= (o >> 24);
           //清空28-31位。
           hash &= ~x;	/*将hash的值5-31 原封保留*/
           }
       }

      //返回一个符号位为0的数，即丢弃最高位，以免函数外产生影响。(我们可以考虑，如果只有字符，符号位不可能为负)
     return (hash & 0x7FFFFFFF);

}

static void freeNode(Node * item)
{
   free(item->key);
   free(item->value);
   free(item);
}
 
 
int test2(void)
{
//  Node *nodePtr;

    HashInit();

    HashInsert("tom", "18");
    HashInsert("jerry", "20");
    HashInsert("spike", "22");

    HashTraversal();

    printf("\nupdate spike age:\n");
    HashInsert("spike", "0");
    HashTraversal();


    printf("\nremove tom:\n");
    HashRemove("tom");
    HashTraversal();

    return 0;


}

 
int main(void)
{
	 test2(void);
	 return 0; 
}

 

  

       while (*str)
      {
           hash = (hash << 4) + (*str++);//hash左移4位，当前字符ASCII存入hash
           if ((x = hash & 0xF0000000L) != 0)
           {//如果最高的四位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出，因此要有如下处理。

			   //该处理，如果对于字符串(a-z 或者A-Z)就会仅仅影响5-8位，否则会影响5-31位，因为C语言使用的算数移位
			   hash ^= (x >> 24);  
			   /**
					因为x除了5-8位为!0其余全部为0
					hash ^ 0X000000F0 ===>hash中除了5-8位其余位均无影响,
											相当于位与1操作（&0X111111) 效果是一样的
											其余的值原封保留
											
					
			   */
			   
			   //清空28-31位。
			   hash &= ~x;	
			   /*
					:(x虽然右移了24位但是x的值并未改变) 
				   x取之与hash的高4位，用之hash的高4位(x = hash & 0xF0000000L)
                   x取反后与hash进行&操作，则会把hash的高4位清0
			   */
           }
       }

 

 

一个数和0进行异或运算 == 这个数和1进行位运算