精华内容
下载资源
问答
  • 算法导论-除法散列法

    2020-11-08 17:14:12
    当应用除法散列法时,要避免选择m的某些值。例如,m不应该是2的幂,因为如果m=2pm=2^pm=2p,则h(k)就是k的p个最低位数。除非已知各种最低p位的排列形式为等可能的,否则在设计函数时,最好考虑关键的所有位。 这段...

    h ( k ) = k m o d    m h(k) =k \mod m h(k)=kmodm
    当应用除法散列法时,要避免选择m的某些值。例如,m不应该是2的幂,因为如果 m = 2 p m=2^p m=2p,则h(k)就是kp个最低位数。除非已知各种最低p位的排列形式为等可能的,否则在设计函数时,最好考虑关键的所有位。

    这段话什么意思呢?当 m = 2 3 m=2^3 m=23结果就会这样:

    57   m o d   8 ≡ 1057   m o d   8 ≡ 3057   m o d   8 ≡ 10057   m o d   8 ≡ 1 57 \bmod 8 \equiv 1057 \bmod 8 \equiv 3057 \bmod 8 \equiv 10057 \bmod 8 \equiv 1 57mod81057mod83057mod810057mod81

    只要低3位是057,余数结果都一样。

    为什么呢?
    假设, m = 2 p m=2^p m=2p ,k的低3位是 r 0 r_0 r0

    • 当k的位数小于等于p时: 余数就是k除以 r 0 r_0 r0的余数

    • 当k的位数大于p时:
      k = r 1 ∗ 1 0 p + m + r 0 ( m > 0 ; m 、 r 1 、 r 0 都 是 整 数 ; r 0 为 低 3 位 ) k = r 1 ∗ 2 p + m ∗ 5 p + m + r 0 k=r_1*10^{p + m} + r_0 (m\gt0; m、r_1、r_0都是整数;r_0为低3位)\\ k=r_1*2^{p + m}*5^{p + m} + r_0 k=r110p+m+r0(m>0mr1r0r03)k=r12p+m5p+m+r0
      k除以 m = 2 p m=2^p m=2p的余数就是k除以 r 0 r_0 r0的余数

    展开全文
  • } re_txt("除法散列法", s, 0); } #region 鏈接散列表 public class clsHash : Hashtable { } public static class toolHX { public static clsDL_dtl hx_find(clsHash hx, int k1,int k2) { var x = hx[k1]; if (x...
    算法導論14-除法散列法

            private void btn散列表_Click(object sender, EventArgs e)
            {
                int[] a = get_intArray(100);
                a = sjpxsz(a);
                var b = a.Take(20).ToArray();
                clsHash ch = new clsHash();
                string s="";
                try
                {
                    for (int i = 0; i < b.Length; i++)
                    {
                        var k = toolHX.cf_slb(b[i], 7);
                        var val = b[i];
                        clsDL d = new clsDL();
                        if (ch[k] != null)
                        {
                            d = (clsDL)ch[k];
                            if (d.head.val==k)
                            {
                                clsDL_dtl dl = new clsDL_dtl();
                                dl.key = val;
                                dl.val = k;
                                toolDL.dl_pop(d, dl);
                            }
                        }
                        else
                        {
                            d = new clsDL();
                            clsDL_dtl dl = new clsDL_dtl();
                            dl.key = val;
                            dl.val = k;
                            d.head = dl;
                            d.tail = dl;
                            d.ls.Add(dl);
                            ch[k] = d;
                        }
                    }

                    foreach (var k in ch.Keys)
                    {
                        clsDL d = (clsDL)ch[k];
                        s += string.Format("樓層: {0} - 編號: ", d.head.val.ToString("00"));
                        var h = d.head;
                        while (h!=null)
                        {
                            s += string.Format("{0} ", h.key.ToString("00"));
                            h = h.next;
                        }
                        s += System.Environment.NewLine;
                    }

                }
                catch (Exception ex)
                {
                    s = ex.Message;
                }

                re_txt("除法散列法", s, 0);
            }

        #region 鏈接散列表

        public class clsHash : Hashtable
        {
            
        }

        public static class toolHX
        {
            public static clsDL_dtl hx_find(clsHash hx, int k1,int k2)
            {
                var x = hx[k1];
                if (x!=null)
                {
                    var d = (clsDL)x;
                    var l = toolDL.dl_search(d, k2);
                    return l;
                }
                return null;
            }

            public static int cf_slb(int k,int m)
            {
                if (m>0)
                {
                    return k % m;
                }
                return -1;
            }
        }

        #endregion


    展开全文
  • 《算法精解:C语言描述》上提到的一种简单的将键值k映射到m槽位...当m不是素数时在散列分布时也会增加分布不均匀的机会,总的来说哈希函数的设计尽量使键值均匀、随机地分布在表中,其他方法可以参考《算法导论》。
    《算法精解:C语言描述》上提到的一种简单的将键值k映射到m槽位的方法:h(k)=k mod m。
    
    而该书上写了一段话:“通常情况下,要避免m取2的幂,因为假设m=2^p,则h(k)是k的二进制数的低p位......,通常选择m会是一个素数,而且不那么靠近2的幂......”。这段话理由是:

    以 m = 2^3 = 8 为例,如下图所示:


    从概率的角度,出现相同的概率比较高,而通常我们希望 h(k) 的值依赖于 k 的所有位而不是最低 p 位,因为这样才会使得散列表看起来更均匀。当m不是素数时在散列分布时也会增加分布不均匀的机会,总的来说哈希函数的设计尽量使键值均匀、随机地分布在表中,其他方法可以参考《算法导论》。
    展开全文
  • 应用除法散列法的时候,要避免选择m的某些值,例如,m不应该为2 的幂 。(尽量取素数,并且距离 2^p 比较远的数值。 )因为如果 m = 2^p (2的p次方),则 H(k) 就是k的p个最低位数字。除非一直各种最低p位的排列...

    算法导论对于除法散列函数的描述。其中涉及到一小点数学问题:

    k mod m时,m之所以为素数时为了使得k在m所在的素数域上保持唯一性(根据欧拉定理和费马小定理)

    散列函数: 

    1. H(k) = k Mod m  

    其中m的取值如是描述:

    应用除法散列法的时候,要避免选择m的某些值,例如,m不应该为2 的幂 。(尽量取素数,并且距离 2^p 比较远的数值。 )因为如果 m = 2^p (2的p次方),则 H(k) 就是k的p个最低位数字。除非一直各种最低p位的排列形式为等可能的,否则在设计散列函数的时候,最好考虑关键字的所有位。

    解释一下:

    如果 m = 2^p (2的p次方),则 H(k) =k Mod m 就等价于 k的低m位与 m 求余所得的值。例如:m = 8 = 2^3 。那么,1456 Mod 8 = 2456 Mod 8 = 3456 Mod 8 = 4456 Mod 8 = 456 Mod 8 ………… 如果这样的话,那么H(k)重复得概率就会大大的增加了。

    “除非已知各种最低p位的排列形式为等可能的”这句话的意思是,如果低位p位在所有k中出现的概率是相同的,那么就可以使用2^p 来作为散列值。“否则在设计散列函数的时候,最好考虑关键字的所有位。”也就是尽量考虑到所有的位数。

    希望解释的能够看懂^^^^^看不懂的只能回家了,不要写代码了........

    附:

    费马小定理是数论中的一个重要定理,其内容为: 假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1。假如p是一个质数的话,则2^(p-1)≡1(mod p)成立(这是费马小定理的一个特殊情况)是对的。但反过来,假如2^(p-1)≡1(mod p)成立那么p是一个质数是不成立的(比如341符合上述条件但不是一个质数)。

    转载于:https://my.oschina.net/lvzhitao/blog/782741

    展开全文
  • 除法散列法中,散列函数为:h(k) = k mod m 其中k为关键字,关键字全域为自然数集N;m为槽的个数。 为什么《算法导论》上说“m = 2^p,则h(k)就是k的p个最低位数字”呢? 我的思路是:由于10的p次(和p次以上)幂...
  • HashDivision<string> hashDivision; hashDivision[2] = "hello"; hashDivision[5] = "world"; cout<<hashDivision[2]<<endl; cout<<hashDivision[5]<...
  • 除法散列法似乎通过取k除以m的余数,来将关键字k映射到m个槽的某一个中去,亦即,散列函数为: h(k)=k mod m 当应用除法散列时,要注意m的选择。例如,m不应是2的幂,应为如果m=(2的p次)方,则 h(k)就是k的p个最低位...
  • 哈希表(Hash Table)及散列法(Hashing) 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?...
  • 散列函数设计:留余数

    千次阅读 2017-02-22 21:36:48
    散列函数设计:留余数 转载地址 感谢分享留余数介绍 留余数此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为:f( key ) = key mod p ( p ≤ m ) mod是取模(求余数)的意思。...
  • 散列存储方法

    万次阅读 2016-04-09 10:43:18
    因为n=11,利用余法构造散列函数,选取小于M的最大质数P=13,则散列函数为:h(key) = key%13。按顺序插入各个结点: 26: h(26) = 0,36: h(36) = 10, 41: h(41) = 2,38: h(38) = 12, 44: h(44) = 5。 插入15...
  • 散列是数据结构中较为重要的内容。两种基本方法之一的链地址虽稍繁琐,但思路较简单,过程清晰。 散列表(Hash table,也叫哈希...散列函数:留余数(取关键字被某个不大于散列表表长m的数p后所得的余数为散...
  • 除法散列法通过取关键字k除以槽数m的余数来确定散列值,散列函数即: h(k) = k mod m 。因为只需要做一次取模操作,因此除法散列法是非常快的。 注意点: 在应用除法散列法时,要避免选择m的某些值。例如2的m次...
  • 这两种方法的不同之处在于:开散列法把发生冲突的关键码存储在散列表主表之外,而闭散列法把发生冲突的关键码存储在表中另一个槽内。 下面介绍业内比较流行的hash冲突解决策略: 线性探测(Linear probing) 双重哈希...
  • 本文探讨拉链表解决哈希冲突的方式和几种常见的散列函数。  首先,什么是散列表?  对于一个数组,我们在O(1)时间复杂度完成可以完成其索引的查找,现在我们想要存储一个key value的键值对,我们可以根据key生成...
  • 散列表类似于数组,可以把散列表的散列值看成数组的索引值,访问散列表和访问数组元素一样快速,他可以在常数时间内实现查找和插入操作。 由于无法通过散列值知道键的大小,因此散列表无法实现有序性操作。 散列...
  • 五:留余数 六:随机数 这些方法原理都是将原来数字按某种规律变成另一个数字 一:直接定址 取关键字的某个线性函数值作为散列地址: 直接定址获取得到的散列函数有点就是简单,均匀也不会产生...
  • 咨询 CONSULT是从基因组测序读取中去除污染物的工具。 依靠位置敏感的哈希,CONSULT从查询集中提取k -mers,并测试它们是否落在参考数据集中用户指定的k -mers汉明距离内。 它支持在其参考库中包含大约80亿个k- mers...
  • 一、散列查找 (一)散列表(Hash Table) 散列表(Hash Table),又称哈希表。是⼀种数据结构,特点是:数据元素的关键字与其存储地址直接相关 若不同的关键字通过散列函数映射到同⼀个值,则称它们为“同义词” ...
  • (4)散列函数设计:留余数

    千次阅读 2016-02-01 17:50:02
    留余数此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为: f( key ) = key mod p ( p ≤ m ) mod是取模(求余数)的意思。事实上,这方法不仅可以对关键字直接取模,也可在折叠、...
  • 留余数+ 链地址再散列 #include&lt;bits/stdc++.h&gt; #define HASHSIZE 13 using namespace std; typedef struct node { int num; struct node *next; }NODE; typedef struct hash { NODE *...
  • 从 ThreadLocal 的实现看散列算法

    千次阅读 2018-07-19 18:08:00
    因为求模数其实是通过一个除法运算得到的,所以叫“除法散列法” 平方散列法(平方取中法) 先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和...
  • hash

    2012-05-11 20:53:10
    七、哈希表(Hash Table)及散列法(Hashing) 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构...
  • 这是数据结构课程作业,用二次探测再散列法解决冲突建立哈希表并查找 从键盘读入 待查找 的权重数值,以留余数法为哈希函数,二次探测再散列法解决冲突建立哈希表,基于哈希算法从数组中查找相应的记录,计算相应...
  • 哈希表(留余数法构造 线性探测再散列法处理冲突)#include &lt;stdio.h&gt;#include &lt;stdlib.h&gt;#include &lt;string.h&gt;int main(){ int a[11]={22,41,53,46,30,13,1,67},b[11]...
  • 散列函数(哈希函数,Hash Function)

    万次阅读 2014-08-13 18:41:49
     散列的概念属于查找,它不以关键字的比较为基本操作,采用直接寻址技术。在理想情况下,查找的期望时间为O(1)。 简单的说,hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。输出字符串的...
  • 开散列概念: 开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储...
  • 正在学习数据结构里的散列相关知识,书里一般都会提到,如果用留余数的散列函数,最好选择素数作为除数。但没有对此详细的证明。 对此不太理解,个人理解是,无论素数还是合数,在取模的一个周期内都是均匀分布...
  • 散列

    2018-04-24 14:10:00
    散列(Hash)是一种对数据的处理方法,通过某种特定的算法将要检索的项与用来检索的索引(称为散列,或者散列值)关联起来,生成一种便于搜索的数据结构(称为散列表)。 2、散列的常见应用: 散列常用作一种数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,137
精华内容 8,054
关键字:

除法散列法