精华内容
下载资源
问答
  • 本文探讨拉链解决哈希冲突的方式和几种常见的散列函数。  首先,什么是散列表?  对于一个数组,我们在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;
    import java.util.LinkedList;
    
    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 LinkedList<Entry<K,V>>[] elements;
        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){
            elements = new LinkedList[size];
            for(int i = 0 ; i < size ; i++)
                elements[i] = new LinkedList<Entry<K,V>>();
            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){
                elements[index].add(newEntry);
                capacity++;
            }
            //发生了哈希碰撞则需要遍历链表判断k值是不是已经存在了
            else{
                Entry<K,V> entry = getEntry(key);
                if(entry != null){
                    entry.value = value;
                    return;
                }
                //执行到这里说明没有发现重复的key 插在链表头部
                elements[index].addFirst(newEntry);
            }
        }
        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与槽的映射。

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


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

    展开全文
  • https://blog.csdn.net/qq_35580883/article/details/79150509
    展开全文
  • /* ... * All rights reserved. * 文件名称:项目3.cbp ...相比线性探查,拉链法适用于大数据,它是把所有的同义词用单链表链接起来,利用哈希函数求出每个关键字的地址,同一地址的利用链表存放在一起。
    /*
    * Copyright (c)2015,烟台大学计算机与控制工程学院
    * All rights reserved.
    * 文件名称:项目3.cbp
    * 作    者:朱希康
    * 完成日期:2015年12月18日
    * 版 本 号:v1.0
    * 问题描述:已知一个关键字序列为if、while、for、case、do、break、else、struct、union、int、double、float、char、long、bool,共15个字符串,哈希函数H(key)为关键字的第一个字母在字母表中的序号,哈希表的表长为26。
    * 输入描述:无
    * 程序输出:哈希表及平均查找长度
    */

    #include <stdio.h>
    #include <string.h>
    #include <malloc.h>
    #define N 15
    #define M 26
    typedef struct node   //定义哈希链表的节点类型
    {
        char *key;
        struct node *next;
    } LNode;
    
    typedef struct
    {
        LNode *link;
    } HTType;
    
    int H(char *s)   //实现哈希函数
    {
        return ((*s-'a'+1)%M);
    }
    
    //构造哈希表
    void Hash(char *s[], HTType HT[])
    {
        int i, j;
        LNode *q;
        for(i=0; i<M; i++)   //哈希表置初值
            HT[i].link=NULL;
        for(i=0; i<N; i++)   //存储每一个关键字
        {
            q=(LNode*)malloc(sizeof(LNode));   //创建新节点
            q->key = (char*)malloc(sizeof(strlen(s[i])+1));
            strcpy(q->key, s[i]);
            q->next=NULL;
            j=H(s[i]);    //求哈希值
            if(HT[j].link==NULL)   //不冲突,直接加入
                HT[j].link=q;
            else        //冲突时,采用前插法插入
            {
                q->next = HT[j].link;
                HT[j].link=q;
            }
        }
    }
    
    //输出哈希表
    void DispHT(HTType HT[])
    {
        int i;
        LNode *p;
        printf("哈希表\n");
        printf("位置\t关键字序列\n");
        printf("---------------------\n");
        for(i=0; i<M; i++)
        {
            printf(" %d\t", i);
            p=HT[i].link;
            while(p!=NULL)
            {
                printf("%s ", p->key);
                p=p->next;
            }
            printf("\n");
        }
        printf("---------------------\n");
    }
    
    //求查找成功情况下的平均查找长度
    double SearchLength1(char *s[], HTType HT[])
    {
        int i, k, count = 0;
        LNode *p;
        for(i=0; i<N; i++)
        {
            k=0;
            p=HT[H(s[i])].link;
            while(p!=NULL)
            {
                k++;   //p!=NULL,进入循环就要做一次查找
                if(strcmp(p->key, s[i])==0)   //若找到,则退出
                    break;
                p=p->next;
            }
            count+=k;
        }
        return 1.0*count/N;   //成功情况仅有N种
    }
    
    //求查找不成功情况下的平均查找长度
    double SearchLength2(HTType HT[])
    {
        int i, k, count = 0;  //count为各种情况下不成功的总次数
        LNode *p;
        for(i=0; i<M; i++)
        {
            k=0;
            p=HT[i].link;
            while(p!=NULL)
            {
                k++;
                p=p->next;
            }
            count+=k;
        }
        return 1.0*count/M;   //不成功时,在表长为M的每个位置上均可能发生
    }
    int main()
    {
        HTType HT[M];
        char *s[N]= {"if", "while", "for", "case", "do", "break", "else", "struct", "union", "int", "double", "float", "char", "long", "bool"};
        Hash(s, HT);
        DispHT(HT);
        printf("查找成功情况下的平均查找长度 %f\n", SearchLength1(s, HT));
        printf("查找不成功情况下的平均查找长度 %f\n", SearchLength2(HT));
        return 0;
    }
    


    运行结果:

    知识点总结:

    相比线性探查,拉链法适用于大数据,它是把所有的同义词用单链表链接起来,利用哈希函数求出每个关键字的地址,同一地址的利用链表存放在一起。

    展开全文
  • 在工业界,主要用拉链法解决哈希冲突,称之为哈希桶的概念。请实现一个简单的哈希表,将如下信息,插入到哈希表中。 哈希表的哈希桶数量设置为10,以员工编号为input来计算哈希后的key,哈希函数使用取余法,编码...

    在工业界,主要用拉链法来解决哈希冲突,称之为哈希桶的概念。请实现一个简单的哈希表,将如下信息,插入到哈希表中。

    哈希表的哈希桶数量设置为10,以员工编号为input来计算哈希后的key,哈希函数使用取余法,编码来实现,并且再编写一个单独的函数来打印出来所有存储的数据。

    编号姓名薪资
    198mark5000
    245jerry5600
    345ferry8000
    346roy7500

    基于数组+链表来实现,每个数组的元素指向一个链表(如果没有冲突,链表中只有一个节点 )

    #include<stdio.h>
    #include<stdlib.h>
    //哈希表的哈希桶数量设置为10,以员工编号为input来计算哈希后的key,哈希函数使用取余法,编码来实现,并且再编写一个单独的函数来打印出来所有存储的数据。
    
    //应该设置10个链表,设置一个有10个元素的指针数组保存其头结点的指针。
    
    struct NODE{
        char *name;
    	int salary;
    	struct NODE *next;
    } ;
    
    
    void new_node(struct NODE *arr[],int bianhao,char *name,int salary){
    	int index=bianhao%10;//索引值是从0-9的。
    
    	//创建一个新节点
    	struct NODE *p;
    	p=(struct NODE *)malloc (sizeof(struct NODE));
    	p->name=name;
    	p->salary=salary;
    	//判断对应的哈希桶是否为空
    	if(arr[index]->next==NULL){
    		//如果为空,将新节点接上去
    		arr[index]->next=p;
    		p->next=NULL;
    	}
    	else{
    		//不为空则遍历到为空的地方,再接上
    		struct NODE *temp_head;
    		temp_head=(struct NODE *)malloc (sizeof(struct NODE));
    		temp_head=arr[index];//移动temo_head指针
    		while(temp_head->next!=NULL){
    			temp_head=temp_head->next;
    		}
    		temp_head->next=p;
    		p->next=NULL;
    	}
    	
    }
    
    void main()
    {
    	//创建指针数组
    		struct NODE *arr[10];
    	//创建10个链表,并保存在指针数组中。
    	int i;
    	for(i=0;i<10;i++){
            struct NODE *head;
    		head=(struct NODE *)malloc (sizeof(struct NODE));
    		arr[i]=head;
    		arr[i]->next=NULL;
    	}
    	
    	//保存数据的函数
    	new_node(arr,198,"mark",5000);
    	new_node(arr,245,"jerry",5600);
    	new_node(arr,345,"ferry",8000);
    	new_node(arr,346,"roy",7500);
    	printf("以下为输出--------------\n");
    
    	//遍历链表进行输出
    	int j;
    	for(j=0;j<10;j++){
    		//说明桶子内有值,循环输出直到next为null
    		if(arr[j]->next!=NULL){
    				printf("第%d个桶子中的数据如下:\n",j);
    				struct NODE *temp_head2;
    				temp_head2=(struct NODE *)malloc (sizeof(struct NODE));
    				temp_head2=arr[j];//移动temo_head2指针
    				while(temp_head2->next!=NULL){
    					printf("员工%s,",temp_head2->next->name);
    					printf("薪水%d\n",temp_head2->next->salary);
    				
    					//指针移动
    					temp_head2=temp_head2->next;
    				}
    			
    		}
    	}
    }
    

    输出结果如下:

    以下为输出--------------
    第5个桶子中的数据如下:
    员工jerry,薪水5600
    员工ferry,薪水8000
    第6个桶子中的数据如下:
    员工roy,薪水7500
    第8个桶子中的数据如下:
    员工mark,薪水5000
    
    展开全文
  • 一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。 一、拉链法 ...
  • 什么是哈希冲突,其实...这种情况就就叫做哈希冲突解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。 一、拉链法 上篇博文我们举的例子,H...
  • 将所有哈希函数结果相同的节点连接在同一个单链表中。 #include <string> #include<stdio.h> #include<vector> struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next...
  • //使用拉链法解决散列冲突 void Insert(int data) { if (ARR[data]==NULL) { Node<int> * s = new Node; s->data = data; ARR[data] = s; s->next = NULL; } else { Node<int> * p = ARR...
  • 哈希表,是根据关键字值(Key)直接进行访问的数据结构,它通过把关键字映射到表中一个位置(数组下标)来直接访问,以加快查找关键值的速度。这个映射函数叫做哈希函数,存放记录的数组叫做哈希表 给定表M,存在函数f...
  • &lt;?php header('Content-type:text/html;charset=utf-8'); class HashTable{ private $buckets; private $size = 10; public function __construct() { $this-&...buckets = new SplFix...
  • //整数哈希函数 } 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_...
  • 哈希冲突 若两个不相等的 key 产生了相等的 哈希值 ,这时则需要采用 哈希冲突拉链法 Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单,将链表和数组相结合。也就是说创建一个...
  • 拉链法和线性探测法解决哈希冲突 转自:http://www.tuicool.com/articles/QNjAbaf   前言 前面学习到的几种算法比如 红黑树 , 二叉搜索树 ,查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一...
  • hash表拉链法解决冲突

    千次阅读 2017-03-07 18:34:03
    散列表(Hash table) 也称为 哈希表 。是字典的一种抽象。比如说你要查一个字,通过这个字的拼音首字母,找到...如果两个不同的 key`算出了同一个索引,此时就要用到一定的方法来解决哈希冲突。 哈希函数 哈希函数
  • 一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。 一、拉链法 上篇...
  •  HashMap中采用的“拉链法”就是一种冲突解决的方式(hash函数的设计才是冲突避免,但不是一种完全的冲突解决方法),如下图所示为“拉链法”结构。  但是HashMap中的节点是Map.Entry类型的,而不是简单的...
  • 哈希表 将所有的数据,确定在某个范围内,对整体情况进行记录。 时间复杂度O(n2)->O(n) 如:在100个数据元素中查找各个数字出现的个数,数字范围为1~10 分析:100个整型数据,范围是1~10 首先,建立一个长度为10...
  • https://www.cnblogs.com/heyanan/p/6912870.html
  • 哈希冲突拉链法

    千次阅读 2015-09-10 19:56:17
    解决哈希冲突一种比较直接的办法就是,将大小为M的数组的每一个元素指向一条链表,链表中的每一个节点都存储一个哈希值为该索引的键,这就是拉链法。 该方法的基本思想就是选择足够大的M,使得所有的链表都尽可能短...
  • 解决哈希冲突的办法

    2020-10-23 19:31:31
    常用解决哈希冲突的方法有以下几种。 开放定址(Open Addressing) 也叫再散列(Rehashing)方法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以...
  • 以vector为容器(可自动扩展),供用户多次输入(而不是在源代码中设置数组)来建立散列,以拉链法解决冲突(头插入建链),可进行多次搜索
  • 哈希表及哈希冲突解决办法

    千次阅读 2019-07-17 22:04:11
    哈希表及哈希冲突解决办法 目录 什么是哈希表? 哈希表的数据结构 哈希冲突 哈希冲突解决办法 1. 什么是哈希表? 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而...
  • 一、简介为了解决线性探构造哈希表所出现的大量哈希冲突,我们采用了另外一种方法,便是开链。而在SGI版本的STL中调用的也正是哈希桶的实现方法。注意:开链实现哈希表的时候会出现很多很多的错误,比如各种模板...
  • 来看一道题,问HashMap是用下列哪种方法来解决哈希冲突的? A 开放地址 B 二次哈希 C 链地址 D 建立一个公共溢出区 答案是:C 解决哈希冲突的方法有三种,分别是: 开放地址:寻找下一个为空的数组下标,而后将...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,230
精华内容 4,092
关键字:

拉链法解决哈希冲突