建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
引言
專(zhuān)注于為中小企業(yè)提供做網(wǎng)站、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)神農(nóng)架林區(qū)免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了1000+企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過(guò)網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
隨著數(shù)據(jù)量的不斷增加，使用Hash表來(lái)存儲(chǔ)和查找數(shù)據(jù)的需求越來(lái)越多。在C語(yǔ)言中，Hash函數(shù)作為Hash表的一部分，具有非常重要的作用。本文將深入探究Linux下C語(yǔ)言中的Hash函數(shù)的實(shí)現(xiàn)原理和常用的Hash函數(shù)。
一、什么是Hash函數(shù)
Hash函數(shù)又稱(chēng)為哈希函數(shù)，是一種將任意長(zhǎng)度的消息壓縮到固定長(zhǎng)度的消息摘要的函數(shù)。Hash函數(shù)通常用于確保數(shù)據(jù)的完整性和安全性，例如密碼加密、數(shù)字簽名等。在Hash表中，Hash函數(shù)用于將一個(gè)關(guān)鍵字映射到一個(gè)數(shù)字上，這個(gè)數(shù)字可以被用作Hash表中的下標(biāo)，從而快速查找和存儲(chǔ)數(shù)據(jù)。
二、Hash函數(shù)的實(shí)現(xiàn)原理
在C語(yǔ)言中，Hash函數(shù)的實(shí)現(xiàn)主要分為以下幾個(gè)步驟：
1. 將一個(gè)字符串轉(zhuǎn)換為一個(gè)數(shù)字，通常用ASCII碼值或者Unicode碼值作為基礎(chǔ)計(jì)算。
2. 對(duì)轉(zhuǎn)換后的數(shù)字進(jìn)行壓縮或者哈希，得到一個(gè)小于或等于指定范圍的數(shù)字，用作Hash表中的下標(biāo)。
3. 碰撞處理，當(dāng)不同的關(guān)鍵字得到了相同的下標(biāo)時(shí)，需要進(jìn)行碰撞處理，例如鏈?zhǔn)椒ɑ蛘唛_(kāi)放定址法。
具體實(shí)現(xiàn)方式可以參見(jiàn)下面的代碼：
unsigned int hash_func(const char *key, unsigned int size) {
unsigned int hashCode = 0;
for(int i = 0; key[i] != ‘\0’; i++) {
hashCode = (hashCode * 31 + key[i]) % size;
}
return hashCode;
}
在上面的代碼中，我們使用了ASCII碼值作為基礎(chǔ)計(jì)算，對(duì)每個(gè)字符的ASCII碼值乘以31再加上前面計(jì)算得到的結(jié)果，最后取模得到一個(gè)指定范圍內(nèi)的數(shù)字。這個(gè)函數(shù)并沒(méi)有進(jìn)行碰撞處理，所以在實(shí)際應(yīng)用中需要加入相應(yīng)的處理方式。
三、常用的Hash函數(shù)
1. PJW Hash
PJW Hash是一種比較常用的Hash函數(shù)，它使用了移位和異或運(yùn)算來(lái)進(jìn)行哈希計(jì)算。PJW Hash的具體實(shí)現(xiàn)方式可以參見(jiàn)下面的代碼：
unsigned int PJWHash(const char* str) {
unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4);
unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8);
unsigned int HighBits = (unsigned int)(0xFFFFFFFF)
unsigned int hashValue = 0;
unsigned int test = 0;
for(int i = 0; str[i] != ‘\0’; i++){
hashValue = (hashValue
if((test = hashValue & HighBits) != 0){
hashValue = ((hashValue ^ (test >> ThreeQuarters)) & (~HighBits));
}
}
return hashValue;
}
2. BKDR Hash
BKDR Hash是一種比較常用的Hash函數(shù)，它使用了33和131等質(zhì)數(shù)來(lái)進(jìn)行哈希計(jì)算。BKDR Hash的具體實(shí)現(xiàn)方式可以參見(jiàn)下面的代碼：
unsigned int BKDRHash(const char* str) {
unsigned int seed = 31;
unsigned int hash = 0;
while (*str){
hash = hash * seed + (*str++);
}
return hash;
}
3. AP Hash
AP Hash是一種比較簡(jiǎn)單的Hash函數(shù)，它使用了多項(xiàng)式Hash算法來(lái)進(jìn)行哈希計(jì)算。AP Hash的具體實(shí)現(xiàn)方式可以參見(jiàn)下面的代碼：
unsigned int APHash(const char* str){
unsigned int hash = 0;
for(int i = 0; str[i] != ‘\0’; i++){
if((i % 2) == 0){
hash ^= ((hash > 3));
} else {
hash ^= (~((hash > 5)));
}
}
return hash;
}
四、
在本文中，我們深入探究了Linux下C語(yǔ)言中的Hash函數(shù)的實(shí)現(xiàn)原理和常用的Hash函數(shù)。Hash函數(shù)在實(shí)際開(kāi)發(fā)中具有非常重要的作用，它能夠快速地查找和存儲(chǔ)數(shù)據(jù)。同樣，在實(shí)際應(yīng)用中，我們還需要注意Hash函數(shù)的碰撞處理問(wèn)題，以確保Hash表的準(zhǔn)確性和穩(wěn)定性。
成都網(wǎng)站建設(shè)公司-創(chuàng)新互聯(lián)為您提供網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)頁(yè)設(shè)計(jì)及定制高端網(wǎng)站建設(shè)服務(wù)！
Makefile.am 規(guī)則和實(shí)例詳解
編寫(xiě)Linux C 程序的時(shí)候，自己來(lái)寫(xiě)Makefile著實(shí)的讓人很頭疼，如果是簡(jiǎn)單的項(xiàng)目自己寫(xiě)寫(xiě)也就罷了，但是如果遇到大項(xiàng)目自己寫(xiě)Makefile，那是要弄死人的，所以最近在研究Autotools工具自動(dòng)生成Makefile，在用到autotools工具生成Makefile的時(shí)候，還是有一部分需要自己來(lái)完成的，那就是Makefile.am文件。
項(xiàng)目中寫(xiě)在源文件里的Makefile.am是一種比我們了解的Makefile更高層次的編譯規(guī)則，它可以和編寫(xiě)的configure.in（了解更多configure.in的規(guī)則請(qǐng)閱讀《 configure.ac (configure.in)詳解 》）文件一起通過(guò)調(diào)用automake命令，來(lái)生成Makefile.in文件，然后再調(diào)用./configure，將Makefile.in文件自動(dòng)的生成Makefile文件。所以Makefile.am文件是要自動(dòng)生成Makefile必不可少的元素，下面鵬博客就來(lái)和大家著重的學(xué)習(xí)下Makefile.am的寫(xiě)法和規(guī)則。
先來(lái)說(shuō)下Makefile.am中常見(jiàn)的文件編譯類(lèi)型，詳細(xì)的編譯類(lèi)型和全局變量鵬博客會(huì)在下面在圖表中列出：
PROGRAMS表示可執(zhí)行文件
SOURCES表示源文件
HEADERS頭文件。
LIBRARIES表示庫(kù)文件
LTLIBRARIES這也是表示庫(kù)文件，前面的LT表示libtool。
DATA數(shù)據(jù)文件，不能執(zhí)行。
SCRIPTS 腳本文件，這個(gè)可以被用于執(zhí)行。如：example_SCRIPTS，如果用這樣的話(huà)，需要我們自己定義安裝目錄下的example目錄，很容易的，往下看。
一、基本寫(xiě)法
下面就直接引入一個(gè)例子進(jìn)行詳細(xì)講解，如下：
AUTOMAKE_OPTIONS = foreign
bin_PROGRAMS = client
client_SOURCES = key.c connect.c client.c main.c session.c hash.c
client_CPPFLAGS = -DCONFIG_DIR=\“$(sysconfdir)\” -DLIBRARY_DIR=\”$(pkglibdir)\”
client_LDFLAGS = -export-dynamic -lmemcached
noinst_HEADERS = client.h
INCLUDES = -I/usr/local/libmemcached/include/
client_LDADD = $(top_builddir)/sx/libsession.la \
$(top_builddir)/util/libutil.la
上面就是一個(gè)Makefile.am示例文件，這個(gè)文件是用于生成client可執(zhí)行應(yīng)用程序，引用了兩個(gè)靜態(tài)庫(kù)和MC等動(dòng)態(tài)庫(kù)的連接。
先來(lái)看個(gè)圖表一（列出了可執(zhí)行文件、靜態(tài)庫(kù)、頭文件和數(shù)據(jù)文件，四種書(shū)寫(xiě)Makefile.am文件個(gè)一般格式。）：
對(duì)于可執(zhí)行文件和靜態(tài)庫(kù)類(lèi)型，如果只想編譯，不想安裝到系統(tǒng)中，可以用noinst_PROGRAMS代替bin_PROGRAMS，noinst_LIBRARIES代替lib_LIBRARIES。以此類(lèi)推。
根據(jù)這個(gè)圖表一來(lái)分析下具體內(nèi)容：
AUTOMAKE_OPTIONS ：這個(gè)是用來(lái)設(shè)定automake的選項(xiàng)。automake主要是幫助開(kāi)發(fā)GNU軟件的人員維護(hù)軟件套件，一般在執(zhí)行automake時(shí)會(huì)檢查目錄下是否存在標(biāo)準(zhǔn)GNU套件中應(yīng)具備的文件檔案，例如NEWS、AUTHOR、ChangeLog等，設(shè)成foreign時(shí)，automake會(huì)改用一般軟件套件標(biāo)準(zhǔn)來(lái)檢查，而gnu是缺省設(shè)置，該級(jí)別下將盡可能地檢查包是否服從GNU標(biāo)準(zhǔn)，gnits是嚴(yán)格標(biāo)準(zhǔn)，不推薦。
bin_PROGRAMS ：表示要生成的可執(zhí)行應(yīng)用程序文件，這里的bin表示可執(zhí)行文件在安裝時(shí)需要被安裝到系統(tǒng)中，如果只是想編譯。不想被安裝到系統(tǒng)中，可以用noinst_PROGRAMS來(lái)代替。
那么整個(gè)之一行 bin_PROGRAMS=client 詳細(xì)表示什么意思那，解釋如下：
PROGRAMS知道這是一個(gè)可執(zhí)行文件。
client表示編譯的目標(biāo)文件。
bin表示目錄文件被安裝到系統(tǒng)的目錄。
如程序和圖片所示，包括頭文件，靜態(tài)庫(kù)的定義等等都是這種形式，如lib_LIBRARIES=util，表示將util庫(kù)安裝到lib目錄下。
繼續(xù)解釋文件內(nèi)容：
client_SOURCES ：表示生成可執(zhí)行應(yīng)用程序所用的所有源文件源文件，多個(gè)就空格隔開(kāi)，我們注意到client_是由前面的bin_PROGRAMS指定的，如果前面是生成example, 那么這里也就變成example_SOURCES，其它的規(guī)則類(lèi)似標(biāo)識(shí)也是一樣。
client_CPPFLAGS ：這個(gè)和我們寫(xiě)Makefile的時(shí)候意思是一樣的，都表示C語(yǔ)言的預(yù)處理器參數(shù)，這里指定了DCONFIG_DIR，以后在程序中，就可以直接使用CONFIG_DIR,不要把這個(gè)和另一個(gè)CFLAGS混淆，后者表示編譯器參數(shù)。
client_LDFLAGS ：表示在連接時(shí)所需要的庫(kù)文件選項(xiàng)標(biāo)識(shí)。這個(gè)也就是對(duì)應(yīng)一些如-l,-shared等選項(xiàng)。
noinst_HEADERS ：表示該頭文件只是參加可執(zhí)行文件的編譯，而不用安裝到安裝目錄下。如果需要安裝到系統(tǒng)中，可以用include_HEADERS來(lái)代替。
INCLUDES ：表示連接時(shí)所需要的頭文件。
client_LDADD ：表示連接時(shí)所需要的庫(kù)文件,這里表示需要兩個(gè)庫(kù)文件的支持，下面會(huì)看到這個(gè)庫(kù)文件又是怎么用Makefile.am文件后成的。
如圖表二：
全局變量 ，可能有人注意到文件中的$(top_builddir)等全局變量，其實(shí)這個(gè)是Makefile.am系統(tǒng)定義的一個(gè)基本路徑變量，表示生成目標(biāo)文件的最上層目錄，如果這個(gè)Makefile.am文件變成其它的Makefile.am文件，那么這個(gè)就表示其它的目錄，而不是這個(gè)當(dāng)前目錄。我們還可以使用$(top_srcdir)，這個(gè)表示工程的最頂層目錄，其實(shí)也是之一個(gè)Makefile.am的入口目錄，因?yàn)镸akefile.am文件可以被遞歸性的調(diào)用。
如圖表三：（在Makefile.am中盡量使用相對(duì)路徑，系統(tǒng)預(yù)定義了兩個(gè)基本路徑）
$(sysconfdir) ：在系統(tǒng)安裝工具的時(shí)候，我們經(jīng)常能遇到配置安裝路徑的命令，如：./configure –prefix=/install/apache 其實(shí)在調(diào)用這個(gè)之后，就定義了一個(gè)變量$(prefix), 表示安裝的路徑，如果沒(méi)有指定安裝的路徑，會(huì)被安裝到默認(rèn)的路徑，一般都是/usr/local。在定義$(prefix)，還有一些預(yù)定義好的目錄,其實(shí)這一些定義都可以在頂層的Makefile文件中可以看到，如下面一些值：
bindir = $(prefix)/bin。
libdir = $(prefix)/lib。
datadir=$(prefix)/share。
sysconfdir=$(prefix)/etc。
includedir=$(prefix)/include。
這些量還可以用于定義其它目錄，例如我想 將client.h安裝到include/client目錄下 ，這樣寫(xiě)Makefile.am文件：
clientincludedir=$(includedir)/client
clientinclude_HEADERS=$(top_srcdir)/client/client.h
這就達(dá)到了我的目的，相當(dāng)于定義了一個(gè)安裝類(lèi)型，這種安裝類(lèi)型是將文件安裝到include/client目錄下。
我們自己也可以 定義新的安裝目錄下的路徑 ，如我在應(yīng)用中簡(jiǎn)單定義的：
devicedir = ${prefix}/device
device_DATA = package
這樣的話(huà)，package文件會(huì)作為數(shù)據(jù)文件安裝到device目錄之下，這樣一個(gè)可執(zhí)行文件就定義好了。注意，這也相當(dāng)于定義了一種安裝類(lèi)型：devicedir，所以你想怎么安裝就怎么安裝，后面的XXXXXdir，dir是固定不變的。
二、配置靜態(tài)庫(kù)
下面我們來(lái)說(shuō)下編譯靜態(tài)庫(kù)和編譯動(dòng)態(tài)庫(kù)，我們說(shuō)下靜態(tài)庫(kù)，下面這個(gè)例子比較簡(jiǎn)單。直接指定 XXXX_LTLIBRARIES或者XXXX_LIBRARIES就可以了。同樣如果不需要安裝到系統(tǒng)，將XXXX換成noinst就可以。
一般推薦使用libtool庫(kù)編譯目標(biāo)，因?yàn)閍utomake包含libtool，這對(duì)于跨平臺(tái)可移植的庫(kù)來(lái)說(shuō)，是一個(gè)很好的事情。
看例子如下：
noinst_LTLIBRARIES = libutil.la
oinst_HEADERS = inaddr.h util.h compat.h pool.h xhash.h url.h device.h
ibutil_la_SOURCES = access.c config.c datetime.c hex.c inaddr.c log.c device.c pool.c rate.c sha1.c stanza.c str.c xhash.c
ibutil_la_LIBADD = @LDFLAGS@
之一行的noinst_LTLIBRARIES，這里要注意的是LTLIBRARIES，另外還有LIBRARIES，兩個(gè)都表示庫(kù)文件。前者表示libtool庫(kù)，用法上基本是一樣的。如果需要安裝到系統(tǒng)中的話(huà)，用lib_LTLIBRARIES。
.la 為libtool自動(dòng)生成的一些共享庫(kù)，vi編輯查看，主要記錄了一些配置信息?？梢杂萌缦旅畈榭?.la文件的格式 $file *.la
.a 為靜態(tài)庫(kù),是好多個(gè).o合在一起,用于靜態(tài)連接
如果想編譯 .a 文件，那么上面的配置就改成如下結(jié)果：
noinst_LTLIBRARIES = libutil.a
oinst_HEADERS = inaddr.h util.h compat.h pool.h xhash.h url.h device.h
ibutil_a_SOURCES = access.c config.c datetime.c hex.c inaddr.c log.c device.c pool.c rate.c sha1.c stanza.c str.c xhash.c
ibutil_a_LIBADD = @LDFLAGS@
注意：靜態(tài)庫(kù)編譯連接時(shí)需要其它的庫(kù)的話(huà)，采用XXXX_LIBADD選項(xiàng)，而不是前面的XXXX_LDADD。編譯靜態(tài)庫(kù)是比較簡(jiǎn)單的，因?yàn)橹苯涌梢灾付ㄆ漕?lèi)型。
三、配置動(dòng)態(tài)庫(kù)
如果想要編譯XXX.so動(dòng)態(tài)庫(kù)文件，需要用到_PROGRAMS類(lèi)型，有一個(gè)關(guān)于安裝路徑的問(wèn)題，如果希望將動(dòng)態(tài)庫(kù)安裝到lib目錄下，按照前面所說(shuō)的，只需要寫(xiě)成lib_PROGRAMS就可以了，lib表示安裝的路徑，但是automake不允許這樣直接定義，所以可以采用下面的辦法，同樣是將動(dòng)態(tài)庫(kù)安裝到lib目錄下：
projectlibdir=$(libdir)//新建一個(gè)目錄，就是該目錄就是lib目錄
projectlib_PROGRAMS=project.so
project_so_SOURCES=xxx.C
project_so_LDFLAGS=-shared -fpic//GCC編譯動(dòng)態(tài)庫(kù)的選項(xiàng)
這個(gè)動(dòng)態(tài)庫(kù)的編譯寫(xiě)法是鵬博客網(wǎng)上總結(jié)的，希望有要的人自己來(lái)驗(yàn)證下。
四、SUBDIRS功能用法
SUBDIRS 這是一個(gè)很重要的詞，我們前面生成了一個(gè)目標(biāo)文件，但是一個(gè)大型的工程項(xiàng)目是由許多個(gè)可執(zhí)行文件和庫(kù)文件組成，也就是包含多個(gè)目錄，每個(gè)目錄下都有用于生成該目錄下的目標(biāo)文件的Makefile.am文件，但頂層目錄是如何調(diào)用，才能使下面各個(gè)目錄分別生成自己的目標(biāo)文件呢？就是SUBDIRS關(guān)鍵詞的用法了。
看一下我的工程項(xiàng)目，這是頂層的Makefile.am文件
EXTRA_DIST = Doxyfile.in README.win32 README.protocol contrib UPGRADE
devicedir = ${prefix}/device
device_DATA = package
SUBDIRS = etc man
ifUSE_LIBSUBST
SUBDIRS += subst
endif
SUBDIRS += tools io sessions util client dispatch server hash storage s
SUBDIRS表示在處理目錄之前，要遞歸處理哪些子目錄，要注意處理的順序。比如配置中的client對(duì)sessions和utils這兩上目標(biāo)文件有依賴(lài)關(guān)系，就在client之前需要處理這兩個(gè)目標(biāo)文件。
EXTRA_DIST ：將哪些文件一起打包。
五、打包處理
Automake會(huì)自動(dòng)的打包 ，自動(dòng)打包的內(nèi)容如下：
所有程序的源文件。
所有子目錄里的的Makefile.am文件。
Makefile.am中包含的文件。
./configure所要讀取的文件。
EXTRA_DIST所指定的文件。
dist和nodist指定的文件，也可將其中一個(gè)源文件指定為不打包：
例如： nodist_client_SOURCES = client.c
六、最后
這里是鵬博客總結(jié)的一些比較實(shí)用的Makefile.am的寫(xiě)法和規(guī)則，看完了這篇文章已經(jīng)可以很詳細(xì)的理解這個(gè)文件的內(nèi)容，寫(xiě)起來(lái)也應(yīng)該不會(huì)陌生，但automake還有許多其他的規(guī)則需要掌握，鵬博客將會(huì)繼續(xù)全面的總結(jié)關(guān)于autotools 的一些規(guī)則和寫(xiě)法，希望對(duì)大家有用處。也歡迎大家指出問(wèn)題，幫我完善這個(gè)博客，希望大家支持！
automake的Makefile.am Makefile.am寫(xiě)法
linux c hash函數(shù)的介紹就聊到這里吧，感謝你花時(shí)間閱讀本站內(nèi)容，更多關(guān)于linux c hash函數(shù),深入探究：Linux下C語(yǔ)言中的Hash函數(shù),Makefile.am 規(guī)則和實(shí)例詳解的信息別忘了在本站進(jìn)行查找喔。
四川成都云服務(wù)器租用托管【創(chuàng)新互聯(lián)】提供各地服務(wù)器租用，電信服務(wù)器托管、移動(dòng)服務(wù)器托管、聯(lián)通服務(wù)器托管，云服務(wù)器虛擬主機(jī)租用。成都機(jī)房托管咨詢(xún)：13518219792
創(chuàng)新互聯(lián)（www.cdcxhl.com）擁有10多年的服務(wù)器租用、服務(wù)器托管、云服務(wù)器、虛擬主機(jī)、網(wǎng)站系統(tǒng)開(kāi)發(fā)經(jīng)驗(yàn)、開(kāi)啟建站+互聯(lián)網(wǎng)銷(xiāo)售服務(wù)，與企業(yè)客戶(hù)共同成長(zhǎng)，共創(chuàng)價(jià)值。
文章標(biāo)題：深入探究：Linux下C語(yǔ)言中的Hash函數(shù)(linuxchash函數(shù))
路徑分享：http://fisionsoft.com.cn/article/dpsgehd.html
