• 拉链法解决哈希表冲突
2020-03-21 14:02:14

将所有哈希函数结果相同的节点连接在同一个单链表中。

#include <string>
#include<stdio.h>
#include<vector>
struct ListNode
{
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
int int_func(int val, int table_len)
{
return val % table_len;
}
void insert(ListNode* hash_table[], ListNode* node, int table_len)
{
int hash_key = int_func(node->val, table_len);
node->next = hash_table[hash_key];
hash_table[hash_key] = node;
}
bool search(ListNode * hash_table[], int value, int table_len)
{
int hash_key = int_func(value, table_len);
{
{
return true;
}
}
return false;
}
int main()
{
const int TABLE_LEN = 11;
ListNode* hash_table[TABLE_LEN] = {0};
std::vector<ListNode*> hash_node_vec;
int test[8] = {1,1,4,9,20,30,150,500};
for (int i = 0; i < sizeof(test)/sizeof(test[0]); i++)
{
hash_node_vec.push_back(new ListNode(test[i]));
}
for (int i = 0; i < hash_node_vec.size(); i++)
{
insert(hash_table, hash_node_vec[i], TABLE_LEN);
}
printf("Hash table:\n");
for (int  i = 0; i < TABLE_LEN; i++)
{
printf("[%d]:",i);
{
}
printf("\n");
}
printf("\n");
printf("Test search: \n");
for (int i = 0; i < 10; i++)
{
if (search(hash_table,i, TABLE_LEN))
{
printf("%d is in the hash table. \n",i);
}
else
{
printf("%d is not in the hash table.\n", i);
}
}
return 0;
}

运行结果为：

Hash table:
[0]:
[1]:->1->1
[2]:
[3]:
[4]:->4
[5]:->500
[6]:
[7]:->150
[8]:->30
[9]:->20->9
[10]:

Test search:
0 is not in the hash table.
1 is in the hash table.
2 is not in the hash table.
3 is not in the hash table.
4 is in the hash table.
5 is not in the hash table.
6 is not in the hash table.
7 is not in the hash table.
8 is not in the hash table.
9 is in the hash table.
更多相关内容
• //整数哈希函数 } void insert(ListNode* hash_table[], ListNode* node, int table_len) { int hash_key = hash_func(node->val, table_len); node->next = hash_table[hash_key];//使用头插插入结点 hash_...
#include<iostream>
#include<vector>

using namespace std;

struct ListNode{
int val;
ListNode* next;
ListNode(int x) :val(x), next(NULL){}
};

int hash_func(int key, int table_len)
{
return key%table_len;//整数哈希函数
}

void insert(ListNode* hash_table[], ListNode* node, int table_len)
{
int hash_key = hash_func(node->val, table_len);
node->next = hash_table[hash_key];//使用头插法插入结点
hash_table[hash_key] = node;
}

bool search(ListNode* hash_table[], int value, int table_len)
{
int hash_key = hash_func(value, table_len);
{
return true;
}

return false;
}

int main()
{
const int TABLE_LEN = 11;
ListNode* hash_table[TABLE_LEN] = { 0 };
vector<ListNode*> hash_node_vec;
int test[8] = { 1, 1, 4, 9, 20, 30, 150, 500 };
for(int i = 0; i < 8; ++i)
hash_node_vec.push_back(new ListNode(test[i]));

for(int i = 0; i < hash_node_vec.size(); ++i)
insert(hash_table, hash_node_vec[i], TABLE_LEN);

printf("Hash table:\n");

for(int i = 0; i < TABLE_LEN; ++i)
{
printf("[%d]", i);
{
}
printf("\n");
}
printf("\n");
printf("Test Search:\n");

for(int i = 0; i < 10; ++i)
{
if(search(hash_table, i, TABLE_LEN))
printf("%d in.\n", i);
else
printf("%d is not in.\n", i);
}
return 0;
}


展开全文
• 本文探讨拉链表解决哈希冲突的方式和几种常见的散列函数。  首先，什么是散列表？  对于一个数组，我们在O(1)时间复杂度完成可以完成其索引的查找，现在我们想要存储一个key value的键值对，我们可以根据key生成...

本文探讨拉链表解决哈希冲突的方式和几种常见的散列函数。

首先，什么是散列表

对于一个数组，我们在O(1)时间复杂度完成可以完成其索引的查找，现在我们想要存储一个key value的键值对，我们可以根据key生成一个数组的索引，然后在索引存储这个key value键值对。我们把根据key生成索引这个函数叫做散列函数。显而易见，不同的key有可能产生相同的索引，这就叫做哈希碰撞，也叫哈希冲突。一个优秀的哈希函数应该尽可能避免哈希碰撞。

而对于本文就将介绍如何拉链法解决哈希冲突的方法，以及常用的哈希函数。

拉链法

这种方法的关键是把同一个散列槽（在我们这里就是数组的每一个槽）中的所有元素放到一个链表中。

我们拿到一个索引首先计算其在散列函数作用下映射出来的索引，如果索引没有元素，直接插入；如果有元素，但是key值和我们要插入的数据不一样，我们就把key value键值对插入链表头；如果存在和我们要插入数据相同key的键值对，我们就把value进行更换。

我们画一张图来表示拉链法put时候发生的情况：

1、没有发生哈希碰撞的时候

2、发生哈希碰撞但是key值不同

3、发生哈希碰撞并且key值相同

下面我们使用一个不会动态开辟新空间的静态哈希表来做一个简单示范，使用的是Java代码：

import java.util.Iterator;

interface HashFunctionHost {
//接口约定根据index确定的hash值
public <K,V> double hashFunction(HashTable<K,V> hashTable,K x);
}
public class HashTable<K, V> {
public static class Entry<K, V>{
private K key;
private V value;
public Entry(K key, V value){
this.key = key;
this.value = value;
}
public K getKey(){
return key;
}
public V getValue(){
return value;
}
}
private HashFunctionHost hashFunctionHost;
private int capacity;
public static final int DEFAULT_SIZE = 10;
public static final HashFunctionHost DEFAULT_HASH_FUNCTION_HOST = new DivisionHashFunctionHost();
@SuppressWarnings("unchecked")
public HashTable(int size, HashFunctionHost hashFunctionHost){
for(int i = 0 ; i < size ; i++)
this.hashFunctionHost = hashFunctionHost;
capacity = 0;
}
public HashTable() {
this(DEFAULT_SIZE, DEFAULT_HASH_FUNCTION_HOST);
}
private Entry<K,V> getEntry(K key){
int index = (int) hashFunctionHost.hashFunction(this, key);
Iterator<Entry<K, V>> iterator = elements[index].iterator();
while(iterator.hasNext()){
//找到了重复的key则直接修改entry中key对应的value
Entry<K, V> temp = iterator.next();
if(key.equals(temp.getKey())){
return temp;
}
}
return null;
}
public void put(K key ,V value){
int index = (int) hashFunctionHost.hashFunction(this,key);
Entry<K, V> newEntry = new Entry<K,V>(key,value);
//没有哈希冲突
if(elements[index].size()==0){
capacity++;
}
//发生了哈希碰撞则需要遍历链表判断k值是不是已经存在了
else{
Entry<K,V> entry = getEntry(key);
if(entry != null){
entry.value = value;
return;
}
//执行到这里说明没有发现重复的key 插在链表头部
}
}
public boolean delete(K key){
int index = (int) hashFunctionHost.hashFunction(this, key);
Iterator<Entry<K, V>> iterator = elements[index].iterator();
while(iterator.hasNext()){
Entry<K, V> entry = iterator.next();
if(entry.getKey()==key){
iterator.remove();
return true;
}
}
return false;
}
public V get(K key){
Entry<K, V> entry = getEntry(key);
if(entry == null)
return null;
return entry.getValue();
}
public int bucketNum(){
return elements.length;
}
public int size(){
return capacity;
}
}

实际上实现起来也很简单，但是请注意一些细节：

①、首先对于一个散列表，这里我们可以自己传入一个哈希函数来完成我们的映射，但是Java不提供函数指针怎么办？《Effective Java》一书说到过这个问题，我们可以使用一个宿主类来包含这个我们想要传递的方法，通过传递宿主类来起来传递方法的作用，也就是我们代码中的接口HashFunctionHost的实现类。

②、在遍历数组中的链表的时候，我们不要使用for循环加上链表的get()方法，而是使用Iterator。看底层源码我们就可以发现get()方法实际上会从头遍历一遍链表，直到找到对应元素，也就是说我们会做很多的无用遍历，这是我们不能接受的。相反Iterator就不是这样，对于访问Iterator下一个元素的复杂度是O(1)。

③、我们在put的时候有三种情况，分别是没有哈希冲突，直接插入有哈希冲突，但是没有相同的key，插入到链表头部有哈希冲突，而且存在相同key，我们就需要修改那个key对应的value

④、在比较key的时候使用equals而不是==，这个不用多说了，equals比较的应该是值，==比较的是内存地址。如果我们想要在key值相等的时候就对value做出替换，那么我们可能要用的是equals而不能用==，并且要对存入散列表的对象的equals方法进行重写。

散列函数

上面的哈希表实现过程我们就看到了我们实现了一个默认的散列函数，我们下面来讨论其他的散列函数。

首先我们需要思考一个好的散列函数需要有的特点：每个关键字都尽量等可能地散列到m个槽中地任何一个，并且和其他关键的散列无关。

下面我们就来介绍常用的几种散列函数。因为我们使用的是Java，因此我们先声明一个接口，表示散列函数的宿主类需要实现这个接口：

interface HashFunctionHost {
//接口约定根据index确定的hash值
public <K,V> double hashFunction(HashTable<K,V> hashTable,K x);
}


1、除法散列法

这种方法是我们上面哈希表的默认哈希函数，也是jdk中HashMap和HashTable的哈希函数。

现在我们有一个关键字k和散列槽的个数m，我们可以通过取k除以m的余数来将关键字映射到m个槽，用数学公式表示就是：

h(k) = k mod m

这个方法运算很快，比较只是以此模运算。然而在m的选择上有一些技巧，我们应该选择不太靠近2的整数次幂的素数m，这个时候哈希碰撞会很少。我们使用Java代码来实现这种散列函数：

public class DivisionHashFunctionHost implements HashFunctionHost {

@Override
public <K,V> double hashFunction(HashTable<K,V> hashTable, K x) {

return Math.abs(x.hashCode())%hashTable.bucketNum();
}
}

由于一些对象的hashCode可能会出现负值，所以我加上了一个绝对值。

2、乘法散列法

乘法散列函数的计算分为几个步骤，用关键字k乘以一个常数A提取kA的小数部分，然后用槽的个数m乘以这个值最后向下取整

这种散列函数对m选择不是很关键，但是常数A对其影响较大，一般我们认为黄金分割率（美妙的大自然），也就是（√5 - 1）/2，大约是0.6180339887是一个很理想的值。

下面是我的实现代码：

public class MultiplicationHashFunctionHost implements HashFunctionHost {

private double constant;
public static final double DEFAULT_CONSTANT = 0.6180339887;
public MultiplicationHashFunctionHost(double constant) {
if(constant<=0 || constant>=1)
throw new IllegalArgumentException("非法参数constant:没有位于(0,1)区间");
this.constant = constant;
}
public MultiplicationHashFunctionHost() {
this(DEFAULT_CONSTANT);
}
@Override
public <K, V> double hashFunction(HashTable<K, V> hashTable, K x) {
return (int)((constant*x.hashCode()-(int)(constant*x.hashCode()))*hashTable.size());
}
}

3、全域散列法

我觉得这种算法更像是一种散列函数的综合。当一个使用者恶意地把n个关键字放入一个槽中的时候，复杂度会变成O(n)，这不是我们想看到的，因此衍生出了这种思路。

我们随机选择散列函数，使得关键字k和关键字l不相等的时候，发生哈希碰撞的概率不大于1/m，用户不能控制关键字与槽的映射，从而使得平均性能很好。毕竟我都random了，你如何确定关键字k与槽的映射。

这更像是一种散列函数的综合的思想，我就不给出代码实现了。

以上，有问题或者对我观点不认同欢迎评论。

展开全文
• Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。 实现...

### 哈希冲突

若两个不相等的 key 产生了相等的 哈希值 ，这时则需要采用 哈希冲突 。

### 拉链法

Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

实现步骤

*得到一个 key
*计算 key 的 hashValue
*根据 hashValue 值定位到 data[hashValue] 。( data[hashValue] 是一条链表)
*若 data[hashValue] 为空则直接插入
*不然则添加到链表末尾

这里需要注意的是， 哈希函数 必须保证 哈希值 的 均匀分布 ，若全部集中在一条链表中，则 时间复杂度 和顺序链表相同。

还有一点则是数组的大小，若你能估计数据的大小，则直接指定即可，否则就需要 动态扩充 数组。

//拉链法实现
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
char *name;//字段名
char *desc;//描述
struct node *next;
}node;

#define HASHSIZE 100 //hash表长度
static node* hashtable[HASHSIZE];//定义一个hash数组，该数组的每个元素是一个hash结点指针,并且由于是全局静态变量,默认初始化为NULL

unsigned int hash(char *s)
{//哈希函数
unsigned int h=0;
for(;*s;s++)
h=*s+h*31;//将整个字符串按照特定关系转化为一个整数，然后对hash长度取余
return h%HASHSIZE;
}

node* lookup(char *str)
{
unsigned int hashvalue = hash(str);
node* np = hashtable[hashvalue];
for( ; np!=NULL; np = np->next)
{//这里是链地址法解决的冲突,返回的是第一个链表结点
if(!strcmp(np->name, str))//strcmp相等的时候才返回0
return np;
}
return NULL;
}

char* search(char* name)
{//对hash表查找特定元素(元素是字符串）
node* np=lookup(name);
if(np==NULL)
return NULL;
else
return np->desc;
}

node* malloc_node(char* name, char* desc)
{//在堆上为结点分配内存，并填充结点
node *np=(node*)malloc(sizeof(node));
if(np == NULL)
return NULL;
np->name = name;
np->desc = desc;
np->next = NULL;
return np;
}

int insert(char* name, char* desc)
{
unsigned int hashvalue;
hashvalue = hash(name);
//头插法，不管该hash位置有没有其他结点，直接插入结点
node* np = malloc_node(name, desc);
if (np == NULL) return 0;//分配结点没有成功，则直接返回
np->next = hashtable[hashvalue];
hashtable[hashvalue] = np;
return 1;
}

/* A pretty useless but good debugging function,
which simply displays the hashtable in (key.value) pairs
*/
void displayHashTable()
{//显示hash表元素（不包括空）
node *np;
unsigned int hashvalue;
for(int i=0; i < HASHSIZE; ++i)
{
if(hashtable[i] != NULL)
{
np = hashtable[i];
printf("\nhashvalue: %d (", i);
for(; np != NULL; np=np->next)
printf(" (%s.%s) ", np->name, np->desc);
printf(")\n");
}
}
}

void cleanUp()
{//清空hash表
node *np,*tmp;
for(int i=0;i < HASHSIZE; ++i)
{
if(hashtable[i] != NULL)
{
np = hashtable[i];
while(np != NULL)
{
tmp = np->next;
free(np->name);
free(np->desc);
free(np);
np = tmp;
}
}
}
}

int main()
{
char* descs[]={"Kobe","Bryant","USA","26300788","Value1","Value2"};

for(int i=0; i < 6; ++i)
insert(names[i], descs[i]);
printf("we should see %s\n",search("k110"));
insert("phone","9433120451");//这里计算的hash是冲突的，为了测试冲突情况下的插入
printf("we have %s and %s\n",search("k101"),search("phone"));
displayHashTable();
cleanUp();
return 0;
}

本文分享自微信公众号 - 国产程序员（Monday_lida），作者：Monday

原文出处及转载信息见文内详细说明，如有侵权，请联系 yunjia_community@tencent.com 删除。

原始发表时间：2019-02-22

本文参与腾讯云自媒体分享计划，欢迎正在阅读的你也加入，一起分享。

展开全文
• 哈希表 将所有的数据，确定在某个范围内，对整体情况进行记录。 时间复杂度O(n2)->O(n) 如：在100个数据元素中查找各个数字出现的个数，数字范围为1~10 分析：100个整型数据，范围是1~10 首先，建立一个长度为10...
• 在工业界，主要用拉链法解决哈希冲突，称之为哈希桶的概念。请实现一个简单的哈希表，将如下信息，插入到哈希表中。 哈希表的哈希桶数量设置为10，以员工编号为input来计算哈希后的key，哈希函数使用取余法，编码...
• 哈希表是一种存储记录的连续内存通过哈希函数的应用，通过哈希函数的应用，可以快速存取与查找数据。所谓哈希法（Hashing），就是将本身的键（Key）通过特定的数学函数运算或使用其他的方转化成对应的数据存储地址。...
• 哈希表，是根据关键字值(Key)直接进行访问的数据结构，它通过把关键字映射到表中一个位置(数组下标)来直接访问，以加快查找关键值的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表 给定表M，存在函数f...
• 一、简介为了解决线性探构造哈希表所出现的大量哈希冲突，我们采用了另外一种方法，便是开链。而在SGI版本的STL中调用的也正是哈希桶的实现方法。注意：开链实现哈希表的时候会出现很多很多的错误，比如各种模板...
• 哈希表理解为一个顺序表，顺序表里面存储的是一个链表(拉链法解决碰撞） 注：(hash & 0x7FFFFFFF)的作用：让hash值一直保持为正。 Because -1 % 10 == -1 which you certainly don’t want for indexing into...
• 以vector为容器（可自动扩展），供用户多次输入（而不是在源代码中设置数组）来建立散列，以拉链法解决冲突（头插入建链），可进行多次搜索
• 哈希表实现
• 哈希表存储结构： 1.开放寻址法 2.拉链法 哈希表的主要作用： ...我们可以用开放寻址法或者拉链法解决这个问题 首先我们先定义哈希函数：h(a) = b，指我们将a映射成b 拉链法： 开一个数组， 举个例子： 维护一个集
• 目录 开放定址 ...创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种： 开放定址 这种方法也称再散列
• 哈希表
• 哈希表处理冲突的方式主要有两种一种是拉链法，另一种是开放寻址法
• 上篇博客我们说到了，什么是哈希冲突，其实就是再采用哈希函数对输入域进行映射到哈希表的时候，因为哈希表的位桶的数目远小于输入域的关键字的个数，所以，对于输入域的关键字来说，很可能会产生这样一种情况，也...
• 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组...
• 关于哈希函数的选取，可以参见这篇文章，另外常见的字符串哈希函数及c++代码实现可以看这里 主要有：常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对...
• 创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。 二、拉链法 基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找...
• 哈希表（Hash table 又叫散列表）是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。通常，我们把这个关键字称为Key值，对应的值称为Value值。关键值和Value值是一种一一对应的关系（也就是映射关系...
• 虽然我们不希望发生冲突，但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度，而且事先并不知道关键字的具体取值时。... 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(...
• ## hash表拉链法解决冲突

万次阅读 多人点赞 2017-03-07 18:34:03
也称为 哈希表 。是字典的一种抽象。比如说你要查一个字，通过这个字的拼音首字母，找到这个字的页码，然后翻到那页找就行了。这种方法直接把查找 时间复杂度 降到了常数。但是要牺牲一定的计算索引的时间。计算...
• 哈希表解决冲突的方法 链地址法（拉链法）：将数组中每个位置存储的元素改成一个链表 开放地址法：寻找空白单元格来存储重复数据，寻找空白单元格的方法： 线性探测： 插入：步长为1，一点点寻找...
• 拉链法和线性探测法解决哈希冲突 转自：http://www.tuicool.com/articles/QNjAbaf   前言 前面学习到的几种算法比如 红黑树 ， 二叉搜索树 ，查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一...
• 首先，要明白哈希冲突，我们需要明白什么是哈希表。 一、哈希表 概念： 哈希表（又叫散列表）是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以...
• 算法竞赛模板，详细讲解哈希表模板（开放寻址法、拉链法、字符串哈希值代码）

...