哈希表的原理
哈希表的存储原理
什么是哈希？
哈希相当于一个人的名字，可以通过名字可以找到这个人
什么是哈希碰撞？
假设一个班级里边有50个人，有两个人的名字都叫张成荣，那么这就是哈希碰撞
为什么会出现哈希碰撞？
假设对于一段文字进行哈希运算，得到的哈希值是123456789
对于另外一段文字进行哈希运算，也可能得到哈希值是123456789
深层原因体现了哈希算法的局限性
哈希的用法
举个例子：
一个学校有40个班级
每个班级平均30个人
那么查找张成荣这个人应该如何查找呢？
传统思维：
两层for循环嵌套
哈希思维：
每个学生入校的时候，对这个人的名字进行哈希运算，得到哈希值123456789
对哈希值进行40的模除运算
得到1~40的结果
结果为1的去1班，为2的去2班
那么查找的时候，就可以首先对张成荣进行哈希和模除运算，得到张成荣所在的班级，然后再在班里边进行名字的比对查找，提高效率
哈希的实例用法(NSDictionary的c语言实现)：
hash_map.h头文件
//
//hash_map.h
//hash_map
/**
NSDictionary的c语言实现
**/
//Created by rong on 2017/11/5.
//Copyright © 2017年 zcr. All rights reserved.
//
#ifndef hash_map_h
#define hash_map_h
#include
//哈希链表
structhash_map;
//创建
structhash_map* hash_map_create(void);
//删除map对象
voidhash_map_clear(structhash_map* map);
//添加数据
//keyvalue
voidhash_map_add(structhash_map* map,constchar* key ,void* value);
//删除key
voidhash_map_remove(structhash_map* map,constchar* key);
//获取hashmap中指定key对应的值
void* hash_map_find(structhash_map* map,constchar* key);
//打印hashmap
voidhash_map_print(structhash_map* map);
#endif/* hash_map_h */
hash_map.m文件
//
//hash_map.c
//hash_map
//
//Created by rong on 2017/11/5.
//Copyright © 2017年 zcr. All rights reserved.
//
#include
#include
#include
#include"hash_map.h"
#define HASH_ARRAY_MAX256
#definemy_malloc malloc
#definemy_free free
structhash_node{
charkey[64];
void* value;
structhash_node* next;//指向下一个hash节点的指针
};
structhash_map{
structhash_node* hash_array[HASH_ARRAY_MAX];
};
#pragma mark - hash_node
staticstructhash_node* hash_node_create(char* key,void* value){
structhash_node* node = (structhash_node*)my_malloc(sizeof(structhash_node));
memset(node,0,sizeof(structhash_node));
strcpy(node->key, key);
node->value= value;
returnnode;
}
staticvoidhash_node_free(structhash_node* node){
my_free(node);
}
#pragma mark - hash_map
//hash算法
unsignedintSDBMHash(char*str)
{
unsignedinthash =0;
while(*str)
{
// equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash <<6) + (hash <<16) - hash;
}
return(hash &0x7FFFFFFF);
}
//根据key进行哈希运算，然后模运算获取key值
staticintkey_gethashvalue(char*key){
//哈希
inthash =SDBMHash(key);
//模运算
intkeyhash = hash%HASH_ARRAY_MAX;
returnkeyhash;
}
structhash_map* hash_map_create(void){
structhash_map*map = (structhash_map*)my_malloc(sizeof(structhash_map));
memset(map,0,sizeof(structhash_map));
returnmap;
}
voidhash_map_add(structhash_map* map,constchar* key ,void* value){
intv =key_gethashvalue((char*)key);
//将新的节点加入到map中
structhash_node* newNode =hash_node_create((char*)key, value);
newNode->next= map->hash_array[v];//将新建的node指向原来的头节点
map->hash_array[v]=newNode;//头节点指针指向新的指针
return;
}
voidhash_map_remove(structhash_map* map,constchar* key){
intv =key_gethashvalue((char*)key);
structhash_node** walk = &(map->hash_array[v]);
//单链表的删除操作！！！
while(*walk) {
if(strcmp((*walk)->key, (char*)key)==0) {//名字相同
structhash_node*node_remove = *walk;
*walk = node_remove->next;
node_remove->next=NULL;
hash_node_free(node_remove);
}else{
walk = &((*walk)->next);
}
}
}
void* hash_map_find(structhash_map* map,constchar* key){
intv =key_gethashvalue((char*)key);
structhash_node* walk= map->hash_array[v];
while(walk) {
if(strcmp(walk->key, key)) {
returnwalk->value;
}
walk = walk->next;
}
returnNULL;
}
voidhash_map_remove_object_for_key(structhash_map* map,char* key){
intv =key_gethashvalue(key);
structhash_node** walk = &(map->hash_array[v]);
while(*walk) {
if(strcmp((*walk)->key, (constchar*)key)==0) {
//删除节点
structhash_node*tmpnode = *walk;
*walk = tmpnode->next;
tmpnode->next=NULL;
hash_node_free(tmpnode);
}else{
walk = &((*walk)->next);
}
}
}
voidhash_map_clear(structhash_map* map){
//释放所有节点
for(inti =0; i
structhash_node* head = map->hash_array[i];
while(head) {
structhash_node* node =head;
head = node->next;
node->next=NULL;//删除链表节点的时候直接释放这块内存不可以吗，为什么还要指向空呢？
hash_node_free(node);
}
}
memset(map,0,sizeof(structhash_map));
}
voidhash_map_print(structhash_map* map){
for(inti =0; i
structhash_node* head = map->hash_array[i];
while(head) {
structhash_node* node = head;
printf("node key=%s value=%s \n",node->key,(char*)node->value);
head = node->next;
}
}
}
main.h
//
//main.c
//hash_map
/*
NSDictionary的原理和实现
NSDictionary的原理：哈希链表
*/
//Created by rong on 2017/11/5.
//Copyright © 2017年 zcr. All rights reserved.
//
#include
#include"hash_map.h"
intmain(intargc,constchar* argv[]) {
structhash_map* map =hash_map_create();
hash_map_add(map,"name","zhangchengrong");
hash_map_add(map,"bid","com.jalon.test");
hash_map_print(map);
//删除key
hash_map_remove_object_for_key(map,"bid");
hash_map_print(map);
//清空hash表
//hash_map_clear(map);
//hash_map_print(map);
return0;
}
网友评论