哈希技术既是一种存储方式，也是一种查找方法
哈希算法的实现步骤：
- 初始化创建Hash表（散列表）
- 给定哈希函数构建Hash表
- 选择合适的冲突处理方法解决地址冲突
- 在Hash表上 Add 或 Del 关键字
- Hash_Add
- Hash_Del
- 在Hash表的基础上执行哈希查找 --- Hash_Find
- 给定关键字k，根据构建Hash表的哈希函数H计算出关键字k的地址H(k)
- 若表中该位置为空，则查找失败
- 否则，比较关键字，若相等，查找成功，否则根据构造表时所采用的冲突处理方法来找下一个地址，直至找到关键字＝k的元素（成功）或者空位置（失败）
建立Hash表的步骤
1. 哈希函数构造方法：（常见的6种）
- (1)直接定址法：
函数公式：f(key)=a*key+b (a,b为常数)
这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道关键字的分布情况，适合查找表较小并且连续的情况。 - (2)除留余数法：
函数公式：f(key)=key mod p (p<=m)m为哈希表表长。
这种方法是最常用的哈希函数构造方法。 - (3) 数字分析法：
比如我们的11位手机号码“136XXXX7887”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意通，136是移动神州行，153是电信等。中间四们是HLR识别号，表示用户归属地。最后四们才是真正的用户号。
若我们现在要存储某家公司员工登记表，如果用手机号码作为关键字，那么极有可能前7位都是相同的，所以我们选择后面的四们作为哈希地址就是不错的选择。 - (4)平方取中法：
故名思义，比如关键字是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为哈希地址。 - (5)折叠法：
折叠法是将关键字从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
比如我们的关键字是9876543210，哈希表表长三位，我们将它分为四组，987|654|321|0 ，然后将它们叠加求和987+654+321+0=1962，再求后3位即得到哈希地址为962，哈哈，是不是很有意思。 - (6)随机数法：
函数公式：f(key)= random(key)。
这里random是随机函数，当关键字的长度不等是，采用这种方法比较合适。
2. 哈希函数冲突解决方法：（常见的2种）
设计得最好的哈希函数也不可能完全避免冲突，当我们在使用哈希函数后发现两个关键字key1!=key2，但是却有f(key1)=f(key2)，即发生冲突。
-
S1：开放定址法：(用此法来构造散列表可能会造成数据堆积)
开放定址法就是一旦发生了冲突，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总是能找到，然后将记录插入。这种方法是最常用的解决冲突的方法。 -
S2：链地址法：
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法
CODE : 实现哈希函数为“除法取余法”，解决冲突为“开放地址线性探测法”的代码实现. http://blog.csdn.net/xiaoping8411/article/details/7706376
[补充] 哈希查找的产生有这样一种背景
有些数据本身是无法排序的(如图像)，有些数据是很难比较的(如图像)。如果数据本身是无法排序的，就不能对它们进行比较查找。如果数据是很难比较的，即使采用折半查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数(它的哈希值)，并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组
哈希表的拓展补充
- 除上面介绍的几个简单常用的散列函数，工业界比较著名的哈希函数（算法）包括
MD4，MD5，SHA-1，它们都是以MD4为基础设计的 - 计算Hash查找成功的平均查找长度ASL时，平均的概念是对当前表中非空元素而言，并非是整个表长
- 计算查找失败的平均查找长度ASL时，平均的概念是针对整个表长
复用性高的代码实现：
[注]
Hash函数： 除留取余
解决冲突： 拉链法
示意图
processon上有
hash.h
typedef DL_NODE_S HASH_NODE_S; /*hash table node*/
typedef DL_HEAD_S HASH_LIST_S; /*hash confic list*/
typedef struct tagDL_NODE
{
struct tagDL_NODE* pstNext; /* the next element */
struct tagDL_NODE** ppstPre; /* the address of previous element's pstNext */
}DL_NODE_S;
typedef struct tagDL_HEAD
{
DL_NODE_S * pstFirst; /* the first element */
}DL_HEAD_S;
typedef struct tagHASH_TABLE
{
ULONG ulSize;
ULONG (*pfHash)(const VOID*)
HASH_LIST_S *pstBckt;
}HASH_TABLE_S;
/*******************************************************************/
#define container_of(ptr, type, member) ({ \
const typeof( ((type*)0)->member) * __mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type, member) ); })
#define HASH_ENTRY(ptr, type, member) container_of(ptr, type, member)
/* 遍历Hash桶 */
#define HASH_TBL_FOREACH(pstTbl, uiIndex) \
for ((ulIndex)=0; (ulIndex) < (pstTbl)->ulSize; (ulIndex)++)
#define HASH_GET_INDEX(pstTbl, pKey) ((pstTbl)->pfHash(pKey))
#define HASH_IS_VALID_INDEX(pstTbl, ulIndex) ( (ulIndex) < (pstTbl)->ulSize )
/* 获取Hash桶的链头 */
#define HASH_GET_LIST(pstTbl, ulIndex) (&(pstTbl)->pstBckt[ulIndex])
#define HASH_IS_HASHED(pstNode) (NULL != (pstNode)->ppstpre )
VOID HASH_Add(INOUT HASH_TABLE_S * pstTbl,
IN HASH_NODE_S * pstNode,
IN const VOID * pKey)
{
HASH_LIST_S * pstList;
ULONG ulIndex;
ulIndex = HASH_GET_INDEX (pstTbl , pKey);
pstList = HASH_GET_LIST (pstTbl, ulIndex);
HASH_ListAdd(pstList, pstNode); // 此为双向链表增加节点的操作
return;
}
VOID HASH_Del(INOUT HASH_NODE_S * pstNode)
{
HASH_ListDel ( pstNode ); //双向链表删除节点的操作
return;
}
通用Hash接口
/* 创建Hash表，哈希表大小ulsize，并挂 Hash回调函数（根据Key计算索引：index = hash(key)） */
HASH_TABLE_S *HASH_Create(IN ULONG ulSize, In ULONG(*pfHash)(const VOID *), IN UINT uiTag)
{
HASH_TABLE_S * pstTbl;
ULONG ulLen,i;
if (0 == ulSize || NULL == pfHash)
{
return NULL;
}
ulLen = sizeof(HASH_TABLE_S) + sizeof(HASH_LIST_S) * ulSize;
pstTbl = (HASH_TABLE_S *) malloc(ulLen);
if (NULL != pstTbl)
{
memset(pstTbl, 0, ulLen);
pstTbl->pstBckt = (HASH_LIST_S *)(pstTbl + 1); // 指向大小为ulSize的动态空间，指针类型为HASH_LIST_S *
pstTbl->ulSize = ulSize;
pstTbl->pfHash = pfHash;
for (i = 0; i < ulSize; i++)
{
DL_Init (&( (pstTbl->pstBckt)[ i ] ));
}
}
return pstTbl;
}
/* pfFree ： Free哈希表节点回调函数 */
VOID HASH_Destory(IN HASH_TABLE_S * pstTbl, IN VOID (*pfFree)(HASH_NODE_S*))
{
HASH_NODE_S *pstNode;
HASH_NODE_S *pstNext;
ULONG ulIndex;
if (NULL == pstTbl)
{
return;
}
if (NULL ！＝ pfFree)
{
HASH_SCAN_TBL_SAFE(pstTbl, ulIndex, pstNode, pstNext)
{
(*pfFree)(pstNode);
}
}
free(pstTbl);
return;
}
/* Hash节点关键字比较回调函数 */
HASH_NODE_S *HASH_Find(IN const HASH_TABLE_S *pstTbl,
IN const VOID * pKey,
IN LONG (*pfKeyCmp)(const HASH_NODE_S *, const VOID*) )
{
HASH_NODE_S * pstNode;
ULONG ulIndex;
if ( (NULL == pstTbl) || (NULL == pKey) || (NULL == pfKeyCmp) )
{
return NULL;
}
ulIndex = HASH_GET_INDEX(pstTbl, pKey); // 获取Hash桶Index
if (!HSAH_IS_VALID_INDEX(pstTbl, ulIndex))
{
return NULL;
}
HASH_SCAN_BCKT(pstTbl, ulIndex, pstNode)
{
if (0 == (*pfKeyCmp)(pstNode, pKey))
{
break;
}
}
}
CODE
Hash桶的实现代码：
/***************************************************************************/
/* identity user HASH table*/
typedef struct tagIDENTITY_USER_TABLE
{
UINT uiUserCount; /* user count */
HASH_TABLE_S *pstUserHashTbl; /* user HASH table */
}IDENTITY_USER_TABLE_S;
/* identity user hash node truct */
typedef struct tagIDENTITY_USER_NODE
{
HASH_NODE_S stHashNode; /* HASH node */
IDENTITY_USER_S *pstIdentityUser; /* 身份识别用户结构 */
}IDENTITY_USER_NODE_S;
/* 根据key获取索引 */
_identityHashUser()
{
}
/* 全局User哈希表指针 */
IDENTITY_USER_TABLE_S *g_pstUserHashTbl = NULL;
/* 初始化 全局User哈希表 */
STATIC ULONG _identity_CreateUserTable(VOID)
{
IDENTITY_USER_TABLE_S * pstUserHashStruct = NULL;
HASH_TABLE_S * pstUserHashTbl = NULL;
pstUserHashStruct = (IDENTITY_USER_TABLE_S *)malloc(sizeof(IDENTITY_USER_TABLE_S ));
if (NULL == pstUserHashStruct)
{
return ERROR_FAILED;
}
pstUserHashTbl = HASH_Create(IDENTITY_USER_HASH_BUCKET_SIZE, _identityHashUser);
if (NULL != pstUserHashTbl)
{
memset(pstUserHashStruct , 0, sizeof(IDENTITY_USER_TABLE_S ));
pstUserHashStruct ->uiUserCount = 0;
pstUserHashStruct ->pstUserHashTbl = pstUserHashTbl;
g_pstUserHashTbl = pstUserHashStruct;
return ERROR_SUCCESS;
}
free(pstUserHashStruct);
return ERROR_FAILED;
}
/* 释放 全局User哈希表 */
STATIC VOID _identity_DestoryUserTable(VOID)
{
/* 释放Hash桶*/
if (NULL != g_pstUserHashTbl)
{
free(g_pstUserHashTbl);
g_pstUserHashTbl = NULL;
}
return;
}
/*用户删除Hash节点回调函数 */
VOID _identityUserHashFreeCbk(HASH_NODE_S *pstHashNode)
{
IDENTITY_USER_NDOE_S *pstUserDataNode;
Assert(NULL != pstHashNode);
pstUserDataNode = HASH_ENTRY(pstHashNode, IDENTITY_USER_NODE_S, stHashNode);
HASH_Del(&(pstUserDataNode ->stHashNode));
/* 释放用户空间 */
if (NULL != pstUserDataNode)
{
free(pstUserDataNode);
}
return;
}
ULONG IDENTITY_data_Init()
{
ULONG ulErrCode = ERROR_SUCCESS;
/* 初始化Hash表 */
ulErrCode = _identity_CreateUserTable();
return ulErrCode
}
VOID IDENTITY_data_Fini()
{
/* 销毁Hash表节点 */
Hash_Destory(g_pstUserHashTbl ->pstUserHashTbl, _identityUserHashFreeCbk);
/* 释放HASH表结构*/
_identity_DestoryUserTable();
return;
}
其他补充
随着硬件价格的下降，当前互联网服务提供商通常采用服务器集群来提高服务的质量，这就带来了数据的分布式存储问题。
如何快速定位数据在集群中的存储位置，关系到集群的性能如下介绍几种常见的分布式存储方式
- 普通集群：将固定的key映射到固定的结点中，结点只存放各自key的数据，此法将key和结点的关系作为一张单独的表格进行维护
有一个结点宕机，结点上的数据需要迁移，表格也需要重新维护
问题：查一个Key值需要遍历整个表格，直到找到存放Key值的结点！查找速度慢- Hash集群
- 一致性哈希：是一种哈希算法，简单来说，在移除或添加一个结点时，它能够尽可能小的改变已存在Key的映射关系
