深入探究：Linux下C语言中的Hash函数 (linux c hash函数)
引言
随着数据量的不断增加，使用Hash表来存储和查找数据的需求越来越多。在C语言中，Hash函数作为Hash表的一部分，具有非常重要的作用。本文将深入探究Linux下C语言中的Hash函数的实现原理和常用的Hash函数。
一、什么是Hash函数
Hash函数又称为哈希函数，是一种将任意长度的消息压缩到固定长度的消息摘要的函数。Hash函数通常用于确保数据的完整性和安全性，例如密码加密、数字签名等。在Hash表中，Hash函数用于将一个关键字映射到一个数字上，这个数字可以被用作Hash表中的下标，从而快速查找和存储数据。
二、Hash函数的实现原理
在C语言中，Hash函数的实现主要分为以下几个步骤：
1. 将一个字符串转换为一个数字，通常用ASCII码值或者Unicode码值作为基础计算。
2. 对转换后的数字进行压缩或者哈希，得到一个小于或等于指定范围的数字，用作Hash表中的下标。
3. 碰撞处理，当不同的关键字得到了相同的下标时，需要进行碰撞处理，例如链式法或者开放定址法。
具体实现方式可以参见下面的代码：
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码值作为基础计算，对每个字符的ASCII码值乘以31再加上前面计算得到的结果，最后取模得到一个指定范围内的数字。这个函数并没有进行碰撞处理，所以在实际应用中需要加入相应的处理方式。
三、常用的Hash函数
1. PJW Hash
PJW Hash是一种比较常用的Hash函数，它使用了移位和异或运算来进行哈希计算。PJW Hash的具体实现方式可以参见下面的代码：
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函数，它使用了33和131等质数来进行哈希计算。BKDR Hash的具体实现方式可以参见下面的代码：
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是一种比较简单的Hash函数，它使用了多项式Hash算法来进行哈希计算。AP Hash的具体实现方式可以参见下面的代码：
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语言中的Hash函数的实现原理和常用的Hash函数。Hash函数在实际开发中具有非常重要的作用，它能够快速地查找和存储数据。同样，在实际应用中，我们还需要注意Hash函数的碰撞处理问题，以确保Hash表的准确性和稳定性。
相关问题拓展阅读：
Makefile.am 规则和实例详解
编写Linux C 程序的时候，自己来写Makefile着实的让人很头疼，如果是简单的项目自己写写也就罢了，但是如果遇到大项目自己写Makefile，那是要弄死人的，所以最近在研究Autotools工具自动生成Makefile，在用到autotools工具生成Makefile的时候，还是有一部分需要自己来完成的，那就是Makefile.am文件。
项目中写在源文件里的Makefile.am是一种比我们了解的Makefile更高层次的编译规则，它可以和编写的configure.in（了解更多configure.in的规则请阅读《 configure.ac (configure.in)详解 》）文件一起通过调用automake命令，来生成Makefile.in文件，然后再调用./configure，将Makefile.in文件自动的生成Makefile文件。所以Makefile.am文件是要自动生成Makefile必不可少的元素，下面鹏博客就来和大家着重的学习下Makefile.am的写法和规则。
先来说下Makefile.am中常见的文件编译类型，详细的编译类型和全局变量鹏博客会在下面在图表中列出：
PROGRAMS表示可执行文件
SOURCES表示源文件
HEADERS头文件。
LIBRARIES表示库文件
LTLIBRARIES这也是表示库文件，前面的LT表示libtool。
DATA数据文件，不能执行。
SCRIPTS 脚本文件，这个可以被用于执行。如：example_SCRIPTS，如果用这样的话，需要我们自己定义安装目录下的example目录，很容易的，往下看。
一、基本写法
下面就直接引入一个例子进行详细讲解，如下：
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
上面就是一个Makefile.am示例文件，这个文件是用于生成client可执行应用程序，引用了两个静态库和MC等动态库的连接。
先来看个图表一（列出了可执行文件、静态库、头文件和数据文件，四种书写Makefile.am文件个一般格式。）：
对于可执行文件和静态库类型，如果只想编译，不想安装到系统中，可以用noinst_PROGRAMS代替bin_PROGRAMS，noinst_LIBRARIES代替lib_LIBRARIES。以此类推。
根据这个图表一来分析下具体内容：
AUTOMAKE_OPTIONS ：这个是用来设定automake的选项。automake主要是帮助开发GNU软件的人员维护软件套件，一般在执行automake时会检查目录下是否存在标准GNU套件中应具备的文件档案，例如NEWS、AUTHOR、ChangeLog等，设成foreign时，automake会改用一般软件套件标准来检查，而gnu是缺省设置，该级别下将尽可能地检查包是否服从GNU标准，gnits是严格标准，不推荐。
bin_PROGRAMS ：表示要生成的可执行应用程序文件，这里的bin表示可执行文件在安装时需要被安装到系统中，如果只是想编译。不想被安装到系统中，可以用noinst_PROGRAMS来代替。
那么整个之一行 bin_PROGRAMS=client 详细表示什么意思那，解释如下：
PROGRAMS知道这是一个可执行文件。
client表示编译的目标文件。
bin表示目录文件被安装到系统的目录。
如程序和图片所示，包括头文件，静态库的定义等等都是这种形式，如lib_LIBRARIES=util，表示将util库安装到lib目录下。
继续解释文件内容：
client_SOURCES ：表示生成可执行应用程序所用的所有源文件源文件，多个就空格隔开，我们注意到client_是由前面的bin_PROGRAMS指定的，如果前面是生成example, 那么这里也就变成example_SOURCES，其它的规则类似标识也是一样。
client_CPPFLAGS ：这个和我们写Makefile的时候意思是一样的，都表示C语言的预处理器参数，这里指定了DCONFIG_DIR，以后在程序中，就可以直接使用CONFIG_DIR,不要把这个和另一个CFLAGS混淆，后者表示编译器参数。
client_LDFLAGS ：表示在连接时所需要的库文件选项标识。这个也就是对应一些如-l,-shared等选项。
noinst_HEADERS ：表示该头文件只是参加可执行文件的编译，而不用安装到安装目录下。如果需要安装到系统中，可以用include_HEADERS来代替。
INCLUDES ：表示连接时所需要的头文件。
client_LDADD ：表示连接时所需要的库文件,这里表示需要两个库文件的支持，下面会看到这个库文件又是怎么用Makefile.am文件后成的。
如图表二：
全局变量 ，可能有人注意到文件中的$(top_builddir)等全局变量，其实这个是Makefile.am系统定义的一个基本路径变量，表示生成目标文件的最上层目录，如果这个Makefile.am文件变成其它的Makefile.am文件，那么这个就表示其它的目录，而不是这个当前目录。我们还可以使用$(top_srcdir)，这个表示工程的最顶层目录，其实也是之一个Makefile.am的入口目录，因为Makefile.am文件可以被递归性的调用。
如图表三：（在Makefile.am中尽量使用相对路径，系统预定义了两个基本路径）
$(sysconfdir) ：在系统安装工具的时候，我们经常能遇到配置安装路径的命令，如：./configure –prefix=/install/apache 其实在调用这个之后，就定义了一个变量$(prefix), 表示安装的路径，如果没有指定安装的路径，会被安装到默认的路径，一般都是/usr/local。在定义$(prefix)，还有一些预定义好的目录,其实这一些定义都可以在顶层的Makefile文件中可以看到，如下面一些值：
bindir = $(prefix)/bin。
libdir = $(prefix)/lib。
datadir=$(prefix)/share。
sysconfdir=$(prefix)/etc。
includedir=$(prefix)/include。
这些量还可以用于定义其它目录，例如我想 将client.h安装到include/client目录下 ，这样写Makefile.am文件：
clientincludedir=$(includedir)/client
clientinclude_HEADERS=$(top_srcdir)/client/client.h
这就达到了我的目的，相当于定义了一个安装类型，这种安装类型是将文件安装到include/client目录下。
我们自己也可以 定义新的安装目录下的路径 ，如我在应用中简单定义的：
devicedir = ${prefix}/device
device_DATA = package
这样的话，package文件会作为数据文件安装到device目录之下，这样一个可执行文件就定义好了。注意，这也相当于定义了一种安装类型：devicedir，所以你想怎么安装就怎么安装，后面的XXXXXdir，dir是固定不变的。
二、配置静态库
下面我们来说下编译静态库和编译动态库，我们说下静态库，下面这个例子比较简单。直接指定 XXXX_LTLIBRARIES或者XXXX_LIBRARIES就可以了。同样如果不需要安装到系统，将XXXX换成noinst就可以。
一般推荐使用libtool库编译目标，因为automake包含libtool，这对于跨平台可移植的库来说，是一个很好的事情。
看例子如下：
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，两个都表示库文件。前者表示libtool库，用法上基本是一样的。如果需要安装到系统中的话，用lib_LTLIBRARIES。
.la 为libtool自动生成的一些共享库，vi编辑查看，主要记录了一些配置信息。可以用如下命令查看*.la文件的格式 $file *.la
.a 为静态库,是好多个.o合在一起,用于静态连接
如果想编译 .a 文件，那么上面的配置就改成如下结果：
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@
注意：静态库编译连接时需要其它的库的话，采用XXXX_LIBADD选项，而不是前面的XXXX_LDADD。编译静态库是比较简单的，因为直接可以指定其类型。
三、配置动态库
如果想要编译XXX.so动态库文件，需要用到_PROGRAMS类型，有一个关于安装路径的问题，如果希望将动态库安装到lib目录下，按照前面所说的，只需要写成lib_PROGRAMS就可以了，lib表示安装的路径，但是automake不允许这样直接定义，所以可以采用下面的办法，同样是将动态库安装到lib目录下：
projectlibdir=$(libdir)//新建一个目录，就是该目录就是lib目录
projectlib_PROGRAMS=project.so
project_so_SOURCES=.C
project_so_LDFLAGS=-shared -fpic//GCC编译动态库的选项
这个动态库的编译写法是鹏博客网上总结的，希望有要的人自己来验证下。
四、SUBDIRS功能用法
SUBDIRS 这是一个很重要的词，我们前面生成了一个目标文件，但是一个大型的工程项目是由许多个可执行文件和库文件组成，也就是包含多个目录，每个目录下都有用于生成该目录下的目标文件的Makefile.am文件，但顶层目录是如何调用，才能使下面各个目录分别生成自己的目标文件呢？就是SUBDIRS关键词的用法了。
看一下我的工程项目，这是顶层的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对sessions和utils这两上目标文件有依赖关系，就在client之前需要处理这两个目标文件。
EXTRA_DIST ：将哪些文件一起打包。
五、打包处理
Automake会自动的打包 ，自动打包的内容如下：
所有程序的源文件。
所有子目录里的的Makefile.am文件。
Makefile.am中包含的文件。
./configure所要读取的文件。
EXTRA_DIST所指定的文件。
dist和nodist指定的文件，也可将其中一个源文件指定为不打包：
例如： nodist_client_SOURCES = client.c
六、最后
这里是鹏博客总结的一些比较实用的Makefile.am的写法和规则，看完了这篇文章已经可以很详细的理解这个文件的内容，写起来也应该不会陌生，但automake还有许多其他的规则需要掌握，鹏博客将会继续全面的总结关于autotools 的一些规则和写法，希望对大家有用处。也欢迎大家指出问题，帮我完善这个博客，希望大家支持！
automake的Makefile.am Makefile.am写法
linux c hash函数的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于linux c hash函数,深入探究：Linux下C语言中的Hash函数,Makefile.am 规则和实例详解的信息别忘了在本站进行查找喔。
