精华内容
下载资源
问答
  • 哈希表

    2021-03-30 22:49:45
    哈希表的概念1.1哈希表的基本概念 1.哈希表的概念 1.1哈希表的基本概念 哈希表基于数组衍生出来的,哈希表高效的核心奥秘是数组的随机访问能力。 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,...

    1.概念

    1.1哈希表的引入

    哈希表基于数组衍生出来的,哈希表高效的核心奥秘是数组的随机访问能力
    顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较,顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(logN),搜索的效率取决于搜索过程中元素的比较次数。
    在这里插入图片描述
    这组数据比较小,这样的方法可以实现,那如果是这样的一组数据呢:1002 1003 1004这组数据呢?那么就用到了理想的搜索方式。那么这样的映射关系是怎么样的呢?

    1.2哈希表的概念

    理想的搜索方法: 可以不经过任何的比较,一次要直接从表中得到要搜索的元素。如果构造一种存储结构,通过某种函数使元素的存储位置与他的关键码之间能够建立一一对应的映射关系(也就是下标的位置之间建立一个映射关系),那么在查找过程中通过该函数可以很快找到该元素。
    插入元素
    根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。
    搜索元素
    对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相同,则搜索成功。
    该方式即为哈希(散列)的方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或者称为散列表)
    在这里插入图片描述
    选取了一个简单的%的映射,此时我们发现,很容易出现两个不同的Key映射到同一个位置上,这是什么问题呢?

    2.哈希冲突

    上面我们出现这样一个问题,若再插入一个数据19,那么会出现则莫杨的问题呢?
    把不同的关键字通过相同的哈希树计算出相同的哈希地址,这种现象称为哈希冲突或者是哈希碰撞。
    把具有不同关键码而具有相同哈希地址的数据元素称为“同义词。

    3.哈希冲突-避免

    3.1彻底消除???

    首先,我们需要明确一点,由于我们的哈希表底层数组的容量往往是小于实际要存储关键字的容量,这就会导致一个问题,冲突的发生是必然的 ,但是我们能够做的就是降低冲突率。

    3.2哈希函数的设计

    引起哈希冲突的一个原因可能是:哈希函数设计的不够合理。
    哈希函数的设计原则:
    1)哈希函数的定义域必须包括需要存储的全部关键码,如果哈希表允许有m个地址时,其值域必须在0到m-1之间;
    2)哈希函数计算出来的地址能均匀分布在整个空间中;
    3)哈希函数应该比较简单;
    常见的哈希函数
    1.除留余数法
    方法描述: 设散列表中允许的地址数为m,取一个不大于m,但最接近的或者等于m的质数p作为除数,按照哈希函数:Hash(key)=key%p(p<=m),将关键码转化为哈希地址。

    3.3负载因子调节

    哈希表的载荷因子定义为:填入表中元素的个数/哈希表的长度。
    负载因子是散列表装满程度的标志因子。由于哈希表的长度是定值,负载因子与”填入表中的元素个数“成正比,所以,负载因子越大,表示填入表中的元素越多,产生冲突的可能性就越大;反之,负载因子越小,标明填入表中的元素越小,产生冲突的可能性就越小。
    所以当冲突率达到一个无法忍受的情况时,我们需要降低负载因子来变相的降低冲突率。

    4.哈希冲突-解决

    4.1闭散列

    闭散列:也叫开放地址法,当发生哈希冲突时,如果哈希表未被装满,说明哈希表中必然还有空位置,那么可以把Key存放到冲突位置的”下一个“空位置中去。这种解决思路,放进去好放,查找的时候比较困难,删除的时候就会更加困难。
    在这里插入图片描述
    如果整个哈希表冲突的比较严重,此时查找的过程就相当于遍历数组了,效率就会受到很大的影响。

    4.2开散列

    开散列法法又叫链地址法(开链法),首先对关键码使用哈希函数计算出哈希地址,具有相同地址的关键码归于同一个集合,每一个集合都称为是一个桶,各个桶中的元素都通过一个单链表来连接起来,各链表的头节点存储在哈希表中。
    在这里插入图片描述
    从上图可以看出,开散列中每个桶中放的元素都是哈希冲突的元素(开散列可以认为是把一个大集合中的搜索问题转化为在小集合中做搜索了)。
    如果某个下标冲突的特别厉害,导致链表很长了,解决方案有两种:
    1)针对数组进行扩容
    此时key%新的长度,得到的下标大概率就分散开了
    2)直接把链表变成一个二叉搜索树/哈希表。
    注意:Java标准库中的HashMap\HashSet就是采取开散列的方式来处理hash冲突,并且当链表较长的时候,就会把链表转换为一个二叉搜索树(红黑树)

    5,哈希表的实现

    class HashNode{
       public int key;
       public int value;
       public HashNode next;
    
        public HashNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public class HashBucket {
    //哈希表的核心是有一个数组,数组上的元素又是一个链表
      private HashNode [] array=new HashNode[16];
      private int size=0;
    
      //通过这个方法,希望把key映射成数组下标
        private int hasCode(int key){
            //此处是简单求余,可以用更复杂的方式
            //比如说
            return key%array.length;
        }
    
      //核心方法
        public void put(int key,int value){
        //1.先根据Key,计算出下标位置
        int index=hasCode(key);
        //2.看看key在hash表中是否存在
            //如果存在,直接修改value,不存在直接插入
            for(HashNode cur=array[index];cur!=null;cur=cur.next){
             if(cur.key==key){
                 //这就说明了找到了相同key的值,然后修改value的值
                cur.value=value;
                return;
             }
            }
            //3.如果经过上面的循环,没有找到匹配的key,就需要创建新的节点
            // ,创建链表,头插
          HashNode  newNode=new HashNode(key,value);
            newNode.next=array[index];
            array[index]=newNode;
            size++;
    
            //4.如果持续插入,就可能会导致冲突概率越来越大,链表越来越长
            //就会影响到后续操作的效率,就可以考虑可以扩容
            //为了衡量啥时候引入扩容,引入负载因子
            if(loadFactor()>0.75){
                //比较拥挤了,就需要扩容
                resize();
            }
        }
    
        private void resize(){
            //搞一个更大的数组,把旧的元素搬运过去就行了
            HashNode [] newArray=new HashNode[array.length*2];
            //遍历旧的哈希表,进行搬运
            HashNode next=null;
            for(int i=0;i<array.length;i++){
                for(HashNode cur=array[i];cur!=null;cur=next){
                    next=cur.next;
                  int newIndex=cur.key%newArray.length;
                  //把当前的cur对应的节点插入到新的数组上
                   cur.next=newArray[newIndex] ;
                   newArray[newIndex]=cur;
                }
            }
            array=newArray;
        }
    
        private double loadFactor(){
            return (double)size/array.length;
        }
    
        public Integer get(int key){
        int index=hasCode(key);
        //遍历对应的链表
            for(HashNode cur=array[index];cur!=null;cur=cur.next){
               if(cur.key==key) {
                   return cur.value;
               }
            }
            return null;
        }
     }
    
    展开全文
  • 哈希表(散列表)原理详解

    万次阅读 多人点赞 2018-07-03 19:40:58
    什么是哈希表哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...

    什么是哈希表?

       哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

    记录的存储位置=f(关键字)

    这里的对应关系f称为散列函数,又称为哈希(Hash函数),采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。

    哈希表hashtable(key,value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。(或者:把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
        而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位

     

    数组的特点是:寻址容易,插入和删除困难;

    而链表的特点是:寻址困难,插入和删除容易。

    那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:


    左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

     

     Hash的应用

    1、Hash主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说,Hash就是找到一种数据内容和数据存放地址之间的映射关系

    2、查找:哈希表,又称为散列,是一种更加快捷的查找技术。我们之前的查找,都是这样一种思路:集合中拿出来一个元素,看看是否与我们要找的相等,如果不等,缩小范围,继续查找。而哈希表是完全另外一种思路:当我知道key值以后,我就可以直接计算出这个元素在集合中的位置,根本不需要一次又一次的查找!

    举一个例子,假如我的数组A中,第i个元素里面装的key就是i,那么数字3肯定是在第3个位置,数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想,建立一个从key到位置的函数,然后进行直接计算查找。

    3、Hash表在海量数据处理中有着广泛应用。

     

     

    Hash Table的查询速度非常的快,几乎是O(1)的时间复杂度。

    hash就是找到一种数据内容和数据存放地址之间的映射关系。

    散列法元素特征转变为数组下标的方法

    我想大家都在想一个很严重的问题:“如果两个字符串在哈希表中对应的位置相同怎么办?”,毕竟一个数组容量是有限的,这种可能性很大。解决该问题的方法很多,我首先想到的就是用“链表我遇到的很多算法都可以转化成链表来解决,只要在哈希表的每个入口挂一个链表,保存所有对应的字符串就OK了。

    散列表的查找步骤 

    当存储记录时,通过散列函数计算出记录的散列地址

    当查找记录时,我们通过同样的是散列函数计算记录的散列地址,并按此散列地址访问该记录

     

    关键字——散列函数(哈希函数)——散列地址

    优点:一对一的查找效率很高;

    缺点:一个关键字可能对应多个散列地址;需要查找一个范围时,效果不好。

    散列冲突:不同的关键字经过散列函数的计算得到了相同的散列地址。

    好的散列函数=计算简单+分布均匀(计算得到的散列地址分布均匀)

    哈希表是种数据结构,它可以提供快速的插入操作和查找操作。

     

    优缺点

    优点:不论哈希表中有多少数据,查找、插入、删除(有时包括删除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。

    哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。

    如果不需要有序遍历数据,并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

    缺点:它是基于数组的,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重,所以程序员必须要清楚表中将要存储多少数据(或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程)。

     

        元素特征转变为数组下标的方法就是散列法。散列法当然不止一种,下面列出三种比较常用的:

    1,除法散列法 
    最直观的一种,上图使用的就是这种散列法,公式: 
          index = value % 16 
    学过汇编的都知道,求模数其实是通过一个除法运算得到的,所以叫“除法散列法”。

    2,平方散列法 
    求index是非常频繁的操作,而乘法的运算要比除法来得省时(对现在的CPU来说,估计我们感觉不出来),所以我们考虑把除法换成乘法和一个位移操作。公式: 
          index = (value * value) >> 28   右移,除以2^28。记法:左移变大,是乘。右移变小,是除。
    如果数值分配比较均匀的话这种方法能得到不错的结果,但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题,value如果很大,value * value不会溢出吗?答案是会的,但我们这个乘法不关心溢出,因为我们根本不是为了获取相乘结果,而是为了获取index。

    3,斐波那契(Fibonacci)散列法

    平方散列法的缺点是显而易见的,所以我们能不能找出一个理想的乘数,而不是拿value本身当作乘数呢?答案是肯定的。

    1,对于16位整数而言,这个乘数是40503 
    2,对于32位整数而言,这个乘数是2654435769 
    3,对于64位整数而言,这个乘数是11400714819323198485

        这几个“理想乘数”是如何得出来的呢?这跟一个法则有关,叫黄金分割法则,而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列,即如此形式的序列:01123581321345589144233,377610, 987, 1597, 2584, 4181, 6765, 10946,…。另外,斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。

        对我们常见的32位整数而言,公式: 
                index = (value * 2654435769) >> 28

        如果用这种斐波那契散列法的话,那上面的图就变成这样了:


    注:用斐波那契散列法调整之后会比原来的取摸散列法好很多。 

    适用范围
        快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。

    基本原理及要点
        hash函数选择,针对字符串,整数,排列,具体相应的hash方法。 
    碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。

     

     

    散列冲突的解决方案:

    1.建立一个缓冲区,把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时,发现找的不对,就在缓冲区里找。

    2.进行再探测。就是在其他地方查找。探测的方法也可以有很多种。

    (1)在找到查找位置的index的index-1,index+1位置查找,index-2,index+2查找,依次类推。这种方法称为线性再探测。

    (2)在查找位置index周围随机的查找。称为随机在探测。

    (3)再哈希。就是当冲突时,采用另外一种映射方式来查找。

    这个程序中是通过取模来模拟查找到重复元素的过程。对待重复元素的方法就是再哈希:对当前key的位置+7。最后,可以通过全局变量来判断需要查找多少次。我这里通过依次查找26个英文字母的小写计算的出了总的查找次数。显然,当总的查找次数/查找的总元素数越接近1时,哈希表更接近于一一映射的函数,查找的效率更高。

     

    扩展 
        d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同 时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个 位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key 存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。

     

    问题实例(海量数据处理) 
        我们知道hash 表在海量数据处理中有着广泛的应用,下面,请看另一道百度面试题:
    题目:海量日志数据,提取出某日访问百度次数最多的那个IP。
    方案:IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。

    展开全文
  • 哈希表原理

    千次阅读 2019-07-08 18:05:07
    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后...

    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。取值时,先对指定的键求Hash值,再和容量取模得到底层数组中对应的位置,如果指定的键值与存贮的键相匹配,则返回该键值对,如果不匹配,则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入、删除等操作可以做到 O ( 1 ) O(1) O(1),最坏的情况是 O ( n ) O(n) O(n),当然这种是最极端的情况,极少遇到。
    image
    不管哪门语言,实现一个HashMap的过程均可分为三大步骤:

    • 实现一个Hash函数
    • 合理解决Hash冲突
    • 实现HashMap的操作方法

    Hash函数

    Hash函数非常重要,一个好的Hash函数不仅性能优越,而且还会让存储于底层数组中的值分配的更加均匀,减少冲突发生。之所以是减少冲突,是因为取Hash的过程,实际上是将输入键(定义域)映射到一个非常小的空间中,所以冲突是无法避免的,能做的只是减少Hash碰撞发生的概率。具体实现时,哈希函数算法可能不同,在Rust及很多语言的实现中,默认选择SipHash哈希算法。

    默认情况下,Rust的HashMap使用SipHash哈希算法,其旨在防止哈希表碰撞攻击,同时在各种工作负载上提供合理的性能。虽然 SipHash 在许多情况下表现出竞争优势,但其中一个比其它哈希算法要慢的情况是使用短键,例如整数。这就是为什么 Rust 程序员经常观察到 HashMap 表现不佳的原因。在这些情况下,经常推荐 FNV 哈希,但请注意,
    它不具备与 SipHash 相同的防碰撞性。

    影响Hash碰撞(冲突)发生的除了Hash函数本身意外,底层数组容量也是一个重要原因。很明显,极端情况下如果数组容量为1,哪必然发生碰撞,如果数组容量无限大,哪碰撞的概率非常之低。所以,哈希碰撞还取决于负载因子。负载因子是存储的键值对数目与数组容量的比值,比如数组容量100,当前存贮了90个键值对,负载因子为0.9。负载因子决定了哈希表什么时候扩容,如果负载因子的值太大,说明存储的键值对接近容量,增加碰撞的风险,如果值太小,则浪费空间。

    所以,既然冲突无法避免,就必须要有解决Hash冲突的机制方法。

    处理冲突的几种方法

    主要有四类处理冲突的方法:

    • 外部拉链法(常用)
    • 开放定址法(常用)
    • 公共溢出区(不常用)
    • 再Hash法(不常用)

    外部拉链法

    主要思想是基于数组和链表的组合来解决冲突,桶(Bucket)中不直接存储键值对,每个Bucket都链接一个链表,当发生冲突时,将冲突的键值对插入链表中。外部拉链法的有点在于方法简单,非同义词之间也不会产生聚集现象(相比于开放定址法),并且其空间结构是动态申请的,所以比较适合无法确定表长的情况:缺点是链表指针需要额外的空间,遇到碰撞拒绝服务时会退化为单链表。

    同义词:两个元素通过Hash函数得到了相同的索引地址,这两个元素就叫做同义词。

    下面是外部拉链法的两种实现方法,主要区别在于桶(Bucket)中是否存储数据。
    image

    image

    开放定址法

    主要思想是发生冲突时,直接去寻找下一个空的地址,只要底层的表足够大,就总能找到空的地址。这个寻找下一个地址的行为,叫做探测。 h a s h i = ( h a s h ( k e y ) + d i ) &ThinSpace; &VeryThinSpace; m o d &VeryThinSpace;&ThinSpace; m , i = 1 , 2... k &ThinSpace; ( k ≤ m − 1 ) {hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}, i=1,2...k\,(k\leq m-1) hashi=(hash(key)+di)modmi=1,2...k(km1)`,其中 h a s h ( k e y ) hash(key) hash(key)为哈希函数, m m m为哈希表长, d i d_{i} di为增量序列, i i i为已发生冲突的次数。根据增量序列取法的不同有多种探测方法:

    • d i = 1 , 2 , 3... ( m − 1 ) d_{i}=1,2,3...(m-1) di=1,2,3...(m1)称为线性探测(Linear Probing);即 d i = i d_{i}=i di=i,或者为其他线性函数。相当于逐个探测存放地址的表,直到查找到一个空单元,把散列地址存放在该空单元。
    • d i = ± 1 2 , ± 2 2 , ± 3 2 . . . ± k 2 ( k ≤ m / 2 ) d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2) di=±12,±22,±32...±k2(km/2)称为平方探测(Quadratic Probing)。相对线性探测,相当于发生冲突时探测间隔$ d_{i}=i^{2}$个单元的位置是否为空,如果为空,将地址存放进去。
    • d i = 伪 随 机 数 序 列 d_{i}=伪随机数序列 di=,称为伪随机探测。

    下图为线性探测:

    image

    公共溢出区

    主要思想是建立一个独立的公共区,把冲突的键值对都放在其中。不常用,这里不再细述。

    再Hash法

    主要思想是有冲突时,换另外一个Hash函数来算Hash值。不常用,这里不再细述。

    实现哈希表的操作方法

    主要是:

    • insert
    • remove
    • get
    • contains_key
    • …等等…

    其中最重要的是插入、查找、删除这三个操作。

    参考文档Hash table

    关注微信公众号,推送常用数据结构、TCP/IP、分布式、后端开发等技术分享,共同学习进步!

    展开全文
  • 姓名哈希表

    千次阅读 多人点赞 2020-06-13 14:53:55
    /为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...

    /为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法
    构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。
    编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法分别封装为2个函数。
    提交实验报告
    /
    程序分析
    1、将姓名表各个名字得ASCII码相加求和。
    2、创建哈希表,将ASCII码取余得KEY值,若未发生冲突存入哈希表
    3、发生冲突调用冲突函数。进行线性探测。最后存入哈希表。

    #define HASH_SIZE 50//哈希表的长度
    #define Name_SIZE 30//名字表长度
    #define R 49//小于哈希表长度的R
    //int i,key;
    struct Name
    {
        char *name;            //姓名
        int ascii;             //对应的ascii码和
    };
    struct hash
    {
        char *name;            //姓名                 
        int ascii;             //对应ASCII码和
        int s;                 //查找长度
    };
    Name NameList [Name_SIZE];
    hash hashtable [HASH_SIZE];
    void init_Namelistlist ( );      //初始化姓名表
    void C_hashtable ( ) ;      //创建hash表
    void collison (int i );          //冲突函数,第i个姓名表发生冲突
    void print_Namelist ( );
    void print_hash ( );         //打印函数
    #include<stdio.h>
    #include<ctype.h>         //toascii函数
    void init_Namelist( )
    {
    
        NameList[0].name="zhangsan";
        NameList[1].name="lisi";
        NameList[2].name="wangmazi";
        NameList[3].name="ergoudan";
        NameList[4].name="tieniu";
        NameList[5].name="dabendan";
        NameList[6].name="xunan";
        NameList[7].name="zhoulei";
        NameList[8].name="tanglei";
        NameList[9].name="xiaomin";
        NameList[10].name="xiaohong";
        NameList[11].name="xiaoli";
        NameList[12].name="damin";
        NameList[13].name="jinzhengyu";
        NameList[14].name="xiasaobi";
        NameList[15].name="xuyang";
        NameList[16].name="lihao";
        NameList[17].name="huangzhifeng";
        NameList[18].name="liangsifen";
        NameList[19].name="yanzhiwo";
        NameList[20].name="liyanlin";
        NameList[21].name="liuxiaohan";
        NameList[22].name="tanghuan";
        NameList[23].name="gongxiaoyu";
        NameList[24].name="haoren";
        NameList[25].name="huairen";
        NameList[26].name="shuchang";
        NameList[27].name="lixinru";
        NameList[28].name="zhouhang";
        NameList[29].name="wangcunwen";
        int i,j;
        for(i=0;i<Name_SIZE;i++)
        {    
            for(j=0;(*(NameList[i].name+j))!='\0';j++)             
            NameList[i].ascii+=toascii(*(NameList[i].name+j));            //ascii码求和
        }                  
    }
    void collison (int i)
    {
        int key,flag;
        flag=0;                                                           //未探测至末尾
        key=(NameList[i].ascii)%R;
        while(hashtable[key].s != 0)
        {
            key=key+1; 
          //  printf("%d",key);                                             //线性探测每次加1
            if(key==HASH_SIZE-1){                                          //探测至哈希表末端
                key=0;
                flag=1;                                                    //探测至末尾标识                       
            }
        }
        if(hashtable[key].s==0)
            {
                hashtable[key].name=NameList[i].name;
                hashtable[key].ascii=NameList[i].ascii;
                if(flag==0)
                hashtable[key].s= (key-(NameList[i].ascii%R))+1 ;
                else
                hashtable[key].s= (HASH_SIZE-(NameList[i].ascii%R))+key+1;   //查找次数                                                                                       //查找次数
            }
    }
    void C_hashtable()                                      //创建哈希函数
    {
        int i,key;
        for(i=0;i<HASH_SIZE;i++)
        {
            hashtable[i].name="\0";
            hashtable[i].ascii=0;
            hashtable[i].s=0;                              //初始化哈希表
        }
        for(i=0;i<Name_SIZE;i++)
        {
            key=(NameList[i].ascii)%R;                        //除留余数法
            if(hashtable[key].s == 0 )                      //未发生冲突
            {
                hashtable[key].name=NameList[i].name;
                hashtable[key].ascii=NameList[i].ascii;
                hashtable[key].s=1;
            }
            else                                                //发生冲突
              collison ( i );                                 //调用冲突函数
            
        }
    
    }
    void show()
    {
        printf("******************************Hashtable_creat******************************\n");
         printf("please input \n A:print Namelist \n B:print the hash table \n C:exit\n");
    }
    void print_Namelist ( )
    {
        int i;
        for(i=0;i<Name_SIZE;i++)
        {
            printf("number:%d\tname:%s\tascii:%d\n",i,NameList[i].name,NameList[i].ascii);
        }
    }
    void print_hash ( )
    {   
        int i;
        float ASL=0.0;                         //平均查找长度
        for(i=0;i<HASH_SIZE;i++)
        {   
            printf("number:%d\tname:%s\tascii:%d\t%d\n",i,hashtable[i].name,hashtable[i].ascii,hashtable[i].s);
            ASL+=hashtable[i].s;
        }
        ASL=ASL/Name_SIZE;
        printf("ASL:%f\n",ASL);
    }
    int main()
    {
        char c;
        while(1){
        show( );
        init_Namelist( );
        C_hashtable( );
        printf ("please in put the order: \n");  
        scanf("%c",&c);
        getchar( );    
        switch(c)
        {
        case 'A':print_Namelist ( );break;
        case 'B' :print_hash ( );break;
        case 'C' :break;
       // default: printf("EROOR\n");break;
        }
        }
         return 0;
    }
    
    展开全文
  • Java哈希表及链式哈希表的实现

    千次阅读 2019-06-18 14:40:02
    哈希表也称为散列表,是用来存储群体对象的集合类结构。 什么是哈希表 数组和向量都可以存储对象,但对象的存储位置是随机的,也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时,只能以某种...
  • 哈希表设计

    2021-01-03 20:06:32
    实验 哈希表设计 数据结构课设 发出来分享 水平有限 希望各位网友多多交流和指正 一、实验目的 熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别。 二、实验原理 程序的功能是对一批关键字集合...
  • 谈谈哈希表

    2017-10-16 16:16:36
    哈希表简单来说可以看作是是对数组的升级,(也有不少人认为哈希表的本质就是数组),那么哈希表和数组的具体联系和区别在哪里呢?我们在利用数组存储数据的时候,记录在数组中的位置是随机的,位置和记录的关键字...
  • #include <iostream> #include <map> using namespace std; ... int array[11] = {1, 2, 3, 3... //less表示该哈希表中小数字的次数,再存放大数字的次数。在此处就是,现存放数组中1出现的次数,在存放数

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 83,422
精华内容 33,368
关键字:

哈希表比较次数