本文分為三個部分：一 Hash Table概論二 Linux源代碼中的Hash List三 Linux源代碼中的Hash Table一 Hash Table概論
字符串的算法一般大公司都會考到，我們首先要想到高效的hash。如百度查找一組字符串是否出現在某個文本中，這個不是考什么kmp，他們想聽到的是hash。趨勢科技考的是從某個文本中刪除一組字符串，我想也是要hash吧。
1 概述
鏈表查找的時間效率為O(N)，二分法為log2N，B+ Tree為log2N，但Hash鏈表查找的時間效率為O(1)。
設計高效算法往往需要使用Hash鏈表，常數級的查找速度是任何別的算法無法比擬的，Hash鏈表的構造和沖突的不同實現方法對效率當然有一定的影響，然 而Hash函數是Hash鏈表最核心的部分，本文嘗試分析一些經典軟件中使用到的字符串Hash函數在執行效率、離散性、空間利用率等方面的性能問題。
2 經典字符串Hash函數介紹
先提一個簡單的問題，如果有一個龐大的字符串數組，然后給你一個單獨的字符串，讓你從這個數組中查找是否有這個字符串并找到它，你會怎么做？有一個方法最簡單，老老實實從頭查到尾，一個一個比較，直到找到為止，我想只要學過程序設計的人都能把這樣一個程序作出來，但要是有程序員把這樣的程序交給用戶，我只能用無語來評價，或許它真的能工作，但...也只能如此了。最合適的算法自然是使用HashTable（哈希表），先介紹介紹其中的基本知識，所謂Hash，一般是一個整數，通過某種算法，可以把一個字符串"壓縮" 成一個整數，這個數稱為Hash.
HDOJ-1800題目分析
除去馬甲，本題的本質是——求相同級別（level）的人最多是幾個。
如果level的范圍不大的話（64位整數可以表示）——本題很簡單，簡單貪心
本題的難點：level的范圍較大，需用大數或者字符串比較（去首0）
效率較高、編程簡單的方法：Hash!此外，字典樹也是不錯的選擇
#include "stdio.h"
#include "memory.h"
#define MAXN 10000
inline int ELFhash(char *key)
{
unsigned long h = 0;
unsigned long g;
while( *key )
{
h =( h<< 4) + *key++;
g = h & 0xf0000000L;
if( g ) h ^= g >> 24;
h &= ~g;
}
return h;
}
int hash[MAXN],count[MAXN];
int maxit,n;
inline void hashit(char *str)
{
int k,t;
while( *str == '0' ) str++;
k = ELFhash(str);
t = k % MAXN;
while( hash[t] != k && hash[t] != -1 )
t = ( t + 5 ) % MAXN;
if( hash[t] == -1 )
count[t] = 1,hash[t] = k;
else if( ++count[t] > maxit )
maxit = count[t];
}
int main()
{
char str[100];
while(scanf("%d",&n)!=EOF)
{
memset(hash,-1,sizeof(hash));
for(maxit=1,gets(str);n>0;n--) //此處的gets是吸收掉之前輸入個數后的回車
{
gets(str);
hashit(str);
}
printf("%d\n",maxit);
}
}
延伸： 在C語言中，接受輸入單個字符的函數如scanf、getchar()等都有一個毛病，就是程序接受完用戶輸入的字符后并沒有清空鍵盤輸入緩沖區（或者說標準輸入流），，因此當用戶輸完字符和回車后，回車字符還留在標準輸入流中，而gets函數又恰好從緩沖區的當前字符開始接收輸入，這樣，它接收的到第一個字符就是上次輸入遺留下來的回車符號，于是程序又會把它作為結束輸入的標志，不再接受用戶的鍵盤輸入。 而C++的輸入流就改正了這個毛病，接受完后自動清空輸入流。
==================================================
#用的是開放定址法處理沖突，線性探測再散列確定增量
#include
#include
#include
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY 0 // 0為無記錄標志
#define N 10 // 數據元素個數
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
typedef int KeyType; // 設關鍵字域為整型
struct ElemType // 數據元素類型
{
KeyType key;
int ord;
};
int hashsize[]={11,19,29,37}; // 哈希表容量遞增表，一個合適的素數序列
int m=0; // 哈希表表長，全局變量
struct HashTable
{
ElemType *elem; // 數據元素存儲基址，動態分配數組
int count; // 當前數據元素個數
int sizeindex; // hashsize[sizeindex]為當前容量
};
Status InitHashTable(HashTable &H)// 操作結果: 構造一個空的哈希表
{ int i;
H.count=0; // 當前元素個數為0
H.sizeindex=0; // 初始存儲容量為hashsize[0]
m=hashsize[0];
H.elem=(ElemType*)malloc(m*sizeof(ElemType));
if(!H.elem)
exit(OVERFLOW); // 存儲分配失敗
for(i=0;i<>
H.elem[i].key=NULLKEY; // 未填記錄的標志
return OK;
}
void DestroyHashTable(HashTable &H)// 初始條件: 哈希表H存在。操作結果: 銷毀哈希表H
{ free(H.elem);
H.elem=NULL;
H.count=0;
H.sizeindex=0;
}
unsigned Hash(KeyType K)// 一個簡單的哈希函數(m為表長，全局變量)
{ return K%m;
}
void collision(int &p,int d) // 線性探測再散列
{
p=(p+d)%m;// 開放定址法處理沖突
}
Status SearchHash(HashTable H,KeyType K,int &p,int &c)// 在開放定址哈希表H中查找關鍵碼為K的元素,若查找成功,以p指示待查數據
{ p=Hash(K); // 求得哈希地址
while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))
{ // 該位置中填有記錄．并且關鍵字不相等
c++;
if(c<>
collision(p,c); // 求得下一探查地址p
else
break;
}
if EQ(K,H.elem[p].key)
return SUCCESS; // 查找成功，p返回待查數據元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置
}
Status InsertHash(HashTable &,ElemType); // 對函數的聲明
void RecreateHashTable(HashTable &H) // 重建哈希表
{ int i,count=H.count;
ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
p=elem;
printf("重建哈希表\n");
for(i=0;i if((H.elem+i)->key!=NULL
本文來自CSDN博客，轉載請標明出處：
http://blog.csdn.net/hell2pradise/archive/2009/08/12/4437041.aspx
二： Linux內核中Hash List的使用其代碼位于include/linux/list.h中，3.0內核中將其數據結構定義放在了include/linux/types.h中
哈希表的數據結構定義如圖：
- struct hlist_head{
- struct hlist_node *first;
- }
- struct hlist_node {
- struct hlist_node *next,**pprev;
- }
1>
頭節點和其他節點結構不一致。
hlist_head表示哈希表的頭結點。哈希表中每一個entry(list_entry)所對應的都是一個鏈表。
hlist_head結構體只有一個域，即first。First指針指向該hlist鏈表的第一個結點。
思考：為什么采用單向鏈表，即頭結點中沒有prev變量？散列表的目的是為了方便快速的查找，所以散列表通常是一個比較大的數組，否則“沖突”的概率會非常大，這樣就失去了散列表的意義。如何來做到既能維護一張大表，又能不占用過多的內存呢?此時只能對于哈希表的每個entry(表頭結點)它的結構體中只能存放一個指針。【簡言之，節省空間】
2> hlist_node結構體有兩個域，next和pprev。(1)next指向下個hlist_node結點，倘若改結點是鏈表的最后一個節點，next則指向NULL
(2)pprev是一個二級指針，它
指向前一個節點的next指針。
思考：*****為什么要采用pprev，而不采用一級指針？********由于hlist不是一個完整的循環鏈表，在list中，表頭和結點是同一個數據結構，直接用prev是ok的。在hlist中，表頭中沒有prev，只有一個first。
1>為了能統一地修改表頭的first指針，即表頭的first指針必須修改指向新插入的結點，hlist就設計了pprev。list結點的pprev不再是指向前一個結點的指針，而是指向前一個節點（可能是表頭）中的next(對于表頭則是first)指針,從而在表頭插入的操作中可以通過一致的node->pprev訪問和修改前結點的next（或first）指針。
2>還解決了數據結構不一致，hlist_node巧妙的將pprev指向上一個節點的next指針的地址，由于hlist_head和hlist_node指向的下一個節點的指針類型相同，就解決了通用性。
參考：http://blog.csdn.net/tigerjibo/article/details/8450995
三 Linux源代碼中的Hash Table這一部分是由 第二部分引出來的，以內核代碼2.6.26為例
在文件error.c (net\9p)中有一個定義
static struct hlist_head hash_errmap[ERRHASHSZ];
- int p9_error_init(void)
- {
- struct errormap *c;
- int bucket;
-
- /* initialize hash table */
- for (bucket = 0; bucket < ERRHASHSZ; bucket++)
- INIT_HLIST_HEAD(&hash_errmap[bucket]);
-
- /* load initial error map into hash table */
- for (c = errmap; c->name != NULL; c++) {
- c->namelen = strlen(c->name);
- /*Hash function 是由自己來確定的*/
- bucket = jhash(c->name, c->namelen, 0) % ERRHASHSZ;
- INIT_HLIST_NODE(&c->list);
- hlist_add_head(&c->list, &hash_errmap[bucket]);
- }
-
- return 1;
- }
你也可以自己來通過 創建一個新的module來利用上內核中的代碼，例子請參考：
http://fanrenhao.blog.51cto.com/3961213/1033529
構建一個文件hlist-module.c，
- #include <linux/init.h>
- #include <linux/module.h>
- #include <linux/list.h>
-
- struct q_coef
- {
- u8 coef;
- u8 index;
- struct hlist_node hash;
- };
-
- #define HASH_NUMBER 15
- u8 coef[HASH_NUMBER] = {
- 0x01, 0x02, 0x04, 0x08,0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13,
- };
- struct q_coef q_coef_list[HASH_NUMBER];
-
- struct hlist_head hashtbl[HASH_NUMBER];
-
- static inline int hash_func(u8 k)
- {
- int a, b, p, m;
- a = 104;
- b = 52;
- p = 233;
- m = HASH_NUMBER;
- return ((a * k + b) % p) % m;
- }
-
- static void hash_init(void)
- {
- int i, j;
- for (i = 0 ; i < HASH_NUMBER ; i++) {
- INIT_HLIST_HEAD(&hashtbl[i]);
- INIT_HLIST_NODE(&q_coef_list[i].hash);
- q_coef_list[i].coef = coef[i];
- q_coef_list[i].index = i + 1;
- }
- for (i = 0 ; i < HASH_NUMBER ; i++) {
- j = hash_func(q_coef_list[i].coef);
- hlist_add_head(&q_coef_list[i].hash, &hashtbl[j]);
- }
- }
-
- static void hash_test(void)
- {
- int i, j;
- struct q_coef *q;
- struct hlist_node *hn;
- for (i = 0 ; i < HASH_NUMBER ; i++) {
- j = hash_func(coef[i]);
- hlist_for_each_entry(q, hn, &hashtbl[j], hash)
- if (q->coef == coef[i])
- printk("found: coef=0x%02x index=%d\n", q->coef, q->index);
- }
- }
- static int htest_init (void)
- {
- hash_init();
- hash_test();
- return -1;
- }
-
- static void htest_exit (void)
- {
- }
-
- module_init(htest_init);
- module_exit(htest_exit);
-
- MODULE_LICENSE("Dual BSD/GPL");
Makefile如下：
- # Makefile2.6
- obj-m += hlist-module.o # ??hellomod ???????
- CURRENT_PATH := $(shell pwd) #?????????
- LINUX_KERNEL := $(shell uname -r) #Linux??????????
- LINUX_KERNEL_PATH := /usr/src/linux-headers-$(LINUX_KERNEL) #Linux??????????
- all:
- make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) modules #?????
- clean:
- make -C $(LINUX_KERNEL_PATH) M=$(CURRENT_PATH) clean #??
然后make，先把dmesg清空一下
$sudo dmesg --clear
然后$sudo insmod hlist_module.ko這個一直顯示有錯誤，不過不影響你看結果ubuntu12:~/program/example/module2$ sudo insmod hlist_module.koinsmod: error inserting 'hlist_module.ko': -1 Operation not permitted看結果$dmesgyyyy@mren-ubuntu12:~/program/example/module2$ dmesg [1318688.795697] found: coef=0x01 index=1[1318688.795701] found: coef=0x02 index=2[1318688.795703] found: coef=0x04 index=3[1318688.795705] found: coef=0x08 index=4[1318688.795707] found: coef=0x10 index=5[1318688.795709] found: coef=0x20 index=6[1318688.795711] found: coef=0x40 index=7[1318688.795713] found: coef=0x80 index=8[1318688.795715] found: coef=0x1d index=9[1318688.795717] found: coef=0x3a index=10[1318688.795719] found: coef=0x74 index=11[1318688.795721] found: coef=0xe8 index=12[1318688.795723] found: coef=0xcd index=13[1318688.795725] found: coef=0x87 index=14[1318688.795727] found: coef=0x13 index=15[1318688.795728] i is 15.
