hash表

1.基本概念

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

2.hash冲突

比如

f(x) = x % 5;          //哈希函数

int hashTble[5];     //哈希表

int value[5];         //存放数据的数组

1. 先忘value[0]存入 'A' [对应ascii码为65] ，  value[1]存入'F' [对应ascii码为70]
2. f(65) = 0;  那么hashTable[0] = 0;
3. f(70) = 0; 那么hashTable[1] = 0;

这就产生了冲突 （hanhTable的0和1是指向的一样的位置）

• 解决方法：让存入hash表的值不一样

3.hash的简单实现

需要实现以下几个接口：

• struct hash *hash_create(void);     //创建一个hash表

• void hash_destroy(struct hash *ht);    //销毁hash表

• int hash_insert(struct hash *ht, const char* key, void *data); //在hash表ht插入一个元素（key, data）

• void *hash_lookup(struct hash *ht, const char* key);  //在hash表ht中，通过key得到value的指针

以下摘自linuxptp的hash实现

/**
 * @file hash.c
 * @brief Implements a simple hash table.
 * @note Copyright (C) 2015 Richard Cochran 
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
#include 
#include 
 
#include "hash.h"
 
#define HASH_TABLE_SIZE 200
 
struct node {
	char *key;
	void *data;
	struct node *next;
};
 
struct hash {
	struct node *table[HASH_TABLE_SIZE];
};
 
static unsigned int hash_function(const char* s)
{
	unsigned int i;
 
	for (i = 0; *s; s++) {
		i = 131 * i + *s;
	}
	return i % HASH_TABLE_SIZE;
}
 
//创建hash表
struct hash *hash_create(void)
{
	struct hash *ht = calloc(1, sizeof(*ht));
	return ht;
}
 
//清除hash表
void hash_destroy(struct hash *ht, void (*func)(void *))
{
	unsigned int i;
	struct node *n, *next, **table = ht->table;
 
	for (i = 0; i < HASH_TABLE_SIZE; i++) {
		for (n = table[i] ; n; n = next) {
			next = n->next;
			if (func) {
				func(n->data);
			}
			free(n->key);
			free(n);
		}
	}
 
	free(ht);
}
 
//向hash表插入元素
int hash_insert(struct hash *ht, const char* key, void *data)
{
	unsigned int h;
	struct node *n, **table = ht->table;
// 通过hash函数，得到key对应的value【value是hash表的位置下标】
	h = hash_function(key);
//避免得到的value值
	for (n = table[h] ; n; n = n->next) {
		if (!strcmp(n->key, key)) {
			/* reject duplicate keys */
			return -1;
		}
	}
//为插入的新元素（链表节点）分配内存
	n = calloc(1, sizeof(*n));
	if (!n) {
		return -1;
	}
//为链表节点赋值
	n->key = strdup(key);
	if (!n->key) {
		free(n);
		return -1;
	}
	n->data = data;
	n->next = table[h];
//将这个新元素的内存地址存入hash表
	table[h] = n;
	return 0;
}
//通过key在hash表ht中得到data
void *hash_lookup(struct hash *ht, const char* key)
{
	unsigned int h;
	struct node *n, **table = ht->table;
 
	h = hash_function(key);
 
	for (n = table[h] ; n; n = n->next) {
		if (!strcmp(n->key, key)) {
			return n->data;
		}
	}
	return NULL;
}

比较关键的逻辑就是:hash_insert函数，主要分为几步

1. 通过hash_function()得到key对应的value，即在hashTable的位置
2. 把传入的key,data存入一个node
3. 把hashTable[value]赋值为node的内存地址

通过hash_lookup()找到key对应的data

1. 先通过hash_function()算出value,即在hashTable的位置
2. 通过hashTable[value]，找到key对应的那个node
3. 通过node可找到key对应的data
4. 返回data作为hash_lookup()的返回值