精华内容
下载资源
问答
  • 拉链法
    2021-02-28 18:13:41

    什么是基于拉链法的散列表?

    对于散列算法的碰撞处理,一种直接的办法就是将大小为M的数组中的每个元素指向一条链表,链表中的每个结点都存储了散列值为该元素的索引的键值对。

    这种方法称为拉链法,因为发生冲的元素都被存储在链表中。

    这个方法的基本思想就是选择足够大的M,使得所有的链表都尽可能的短以保证高效地查找。

    基于拉链法的散列表的查找方法:首先根据散列值找到对应的链表,

    然后沿着链表顺序查找相应的键。

    拉链法的一种实现方法使用原始的链表数据类型。

    采用一般性的策略(但效率稍低),为M个元素分别构建符号表来保存散列到这里的键。

    拉链法中链的平均长度

    因为我们要用M条链表保存N个键,无论键在各个链表中的分布如何,链表的平均长度肯定为

    N/M

    例如,假设所有的键都落在了第一条链表上,所有链表的平均长度仍然

    (N+0+0+0+…+0)/M = N/M。

    拉链法在实际情况中很有用,因为每条链表确实都大约有N/M个键值对。在一般情况中,我们能够依赖这种高效的查找和插入操作。

    代码实现

    public class SeparateChainingHashST {

    private static final int INIT_CAPACITY = 4;

    private int n; // 键值对的总数

    private int m; // 散列表的大小

    private SequentialSearchST[] st; // 存放链表对象的数组

    public SeparateChainingHashST() { //无参构造

    this(997);

    }

    public SeparateChainingHashST(int m) { //有参构造

    this.m = m; //创建M条链表

    st = (SequentialSearchST[]) new SequentialSearchST[m];

    for (int i = 0; i < m; i++)

    st[i] = new SequentialSearchST();

    }

    private int hash(Key key) { //获得键的hash值

    return (key.hashCode() & 0x7fffffff) % m;

    }

    public Value get(Key key) { //获取符号表中的指定键

    int i = hash(key);

    return st[i].get(key);

    }

    public void put(Key key, Value val) { //存放一个键值对到符号表

    if (val == null) {

    delete(key);

    return;

    }

    //如果列表的平均长度>= 2,则将表大小增加一倍

    if (n >= 10*m) resize(2*m);

    int i = hash(key);

    if (!st[i].contains(key)) n++;

    st[i].put(key, val);

    }

    public Iterable keys() { //返回符号表中键的迭代器

    Queue queue = new Queue();

    for (int i = 0; i < m; i++) {

    for (Key key : st[i].keys())

    queue.enqueue(key);

    }

    return queue;

    }

    这段简单的符号表实现维护着一条链表的数组,用散列表来为每个键选择一条链表。简单起见,我们使用了SequentialSearchST。在创建st[]时需要进行类型转换,因为Java不允许泛型的数组。默认的构造函数会使用997条链表,因为对于较大的符号表,这种实现比SequentialSearchST大约快1000倍。当你能够预知需要的符号表大小时,这种短小精悍的方案能够得到不错的性能。

    一种更可靠的方案是动态调整链表数组的大小,这样无论在符号表中有多少键值对都能保证链表较短。

    散列表的大小

    在实现基于拉链法的散列表时,我们的目标是选择适当的数组大小M,既不会因为空链表而浪费大量内存,也不会因为链表太长而在查找上浪费大量时间。对于拉链法来说这并不是关键性的选择。

    如果存入的键多余预期,查找所需的时间只会比选择更大的数组稍长;如果少于预期,虽然有些空间浪费但查找会非常快。

    当内存不是很紧张时,可以选择一个足够大的M,使得查找所选要的时间变为常数;当内存紧张时,选择尽量大的M仍然能够将性能提高M倍。

    删除操作

    要删除一个键值对,先用散列值找到含有该键的SequentialSearchST对象,然后调用该对象的delete()方法。

    public void delete(Key key) {

    if (key == null) throw new IllegalArgumentException("argument to delete() is null");

    int i = hash(key);

    if (st[i].contains(key)) n--;

    st[i].delete(key);

    // 如果列表的平均长度<= 2,则将表大小减半 if (m > INIT_CAPACITY && n <= 2*m) resize(m/2);

    }

    有序性相关操作

    散列最主要的目的在于均匀地将键散布开来,因此在计算散列后键的顺序信息就丢失了。如果你需要快速找到最大键或者最小键,或是查找某个范围内的键,散列表都不是合适的选择,因为这些操作的时间都是线性的。

    小小总结:

    基于拉链法的散列表的实现简单。在键的顺序并不重要的应用中。它可能是最快的(也是使用最广泛的)符号表实现。

    更多相关内容
  • 拉链法

    千次阅读 2018-05-24 16:41:51
    一、有序集合求交集的方法有 a)二重for循环法,时间复杂度O(n*n) b)拉链法,时间复杂度O(n) c)水平分桶,多线程并行 d)bitmap,大大提高运算并行度,时间复杂度O(n) e)跳表,时间复杂度为O(log(n))以下是...

    list1与list2求交集的方法总结!

    一、有序集合求交集的方法有

             a)二重for循环法,时间复杂度O(n*n)

             b)拉链法,时间复杂度O(n)

             c)水平分桶,多线程并行

             d)bitmap,大大提高运算并行度,时间复杂度O(n)

             e)跳表,时间复杂度为O(log(n))

    以下是方法的具体介绍:

    方案一:for * for,土办法,时间复杂度O(n*n)

        每个搜索词命中的网页是很多的,O(n*n)的复杂度是明显不能接受的。倒排索引是在创建之初可以进行排序预处理,问题转化成两个有序的list求交集,就方便多了。

    方案二:有序list求交集,拉链法

        

          有序集合1{1,3,5,7,8,9}

          有序集合2{2,3,4,5,6,7}

        两个指针指向首元素,比较元素的大小:

        (1)如果相同,放入结果集,随意移动一个指针

        (2)否则,移动值较小的一个指针,直到队尾

      这种方法的好处是:

      (1)集合中的元素最多被比较一次,时间复杂度为O(n)

      (2)多个有序集合可以同时进行,这适用于多个分词的item求url_id交集

      这个方法就像一条拉链的两边齿轮,一一比对就像拉链,故称为拉链法

    方案三:分桶并行优化

        数据量大时,url_id分桶水平切分+并行运算是一种常见的优化方法,如果能将list1<url_id>和list2<url_id>分成若干个桶区间,每个区间利用多线程并行求交集,各个线程结果集的并集,作为最终的结果集,能够大大的减少执行时间。

         举例:

          有序集合1{1,3,5,7,8,9, 10,30,50,70,80,90}

          有序集合2{2,3,4,5,6,7, 20,30,40,50,60,70}

         求交集,先进行分桶拆分:

          桶1的范围为[1, 9]

          桶2的范围为[10, 100]

          桶3的范围为[101, max_int]

        于是:

        集合1就拆分成

        集合a{1,3,5,7,8,9}

        集合b{10,30,50,70,80,90}

        集合c{} 

        集合2就拆分成

        集合d{2,3,4,5,6,7}

        集合e{20,30,40,50,60,70}

        集合e{}

        每个桶内的数据量大大降低了,并且每个桶内没有重复元素,可以利用多线程并行计算:

        桶1内的集合a和集合d的交集是x{3,5,7}

        桶2内的集合b和集合e的交集是y{30, 50, 70}

        桶3内的集合c和集合d的交集是z{}

        最终,集合1和集合2的交集,是x与y与z的并集,即集合{3,5,7,30,50,70}

    方案四:bitmap再次优化

        数据进行了水平分桶拆分之后,每个桶内的数据一定处于一个范围之内,如果集合符合这个特点,就可以使用bitmap来表示集合:

          

     

      如上图,假设set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的所有元素都在桶值[1, 16]的范围之内,可以用16个bit来描述这两个集合,原集合中的元素x,在这个16bitmap中的第x个bit为1,此时两个bitmap求交集,只需要将两个bitmap进行“与”操作,结果集bitmap的3,5,7位是1,表明原集合的交集为{3,5,7}

         水平分桶,bitmap优化之后,能极大提高求交集的效率,但时间复杂度仍旧是O(n)

        但bitmap需要大量连续空间,占用内存较大

    方案五:跳表skiplist

        有序链表集合求交集,跳表是最常用的数据结构,它可以将有序集合求交集的复杂度由O(n)降至O(log(n))

         

        集合1{1,2,3,4,20,21,22,23,50,60,70}

        集合2{50,70}

        要求交集,如果用拉链法,会发现1,2,3,4,20,21,22,23都要被无效遍历一次,每个元素都要被比对,时间复杂度为O(n),能不能每次比对“跳过一些元素”呢?

    跳表就出现了:

          

        集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表时,一级只有{1,20,50}三个元素,二级与普通链表相同,集合2{50,70}由于元素较少,只建立了一级普通链表;如此这般,在实施“拉链”求交集的过程中,set1的指针能够由1跳到20再跳到50,中间能够跳过很多元素,无需进行一一比对,跳表求交集的时间复杂度近似O(log(n)),这是搜索引擎中常见的算法。

     

     

     

    本片博客转载自以下网站(本着分享以及保存以便日后复习的目的发布此博客):

    展开全文
  • 字典也叫散列表,最大的特点是通过key来查找其对应的值其时间复杂度是O(1),下面这篇文章就来给大家介绍介绍python利用拉链法实现字典的方法。 在Python中怎样用列表实现字典? 用列表实现字典最大的问题就是解决hash...
  • } 小博演示的拉链法是将数组的特点(方便查找,不易删除)以及链表的特点(方便删除,不易查找)取长补短的一种折中方法。 ----------------------------------------------分界线,又出现了----------------------...

    前段时间理解了一下所谓的哈希表,一直以来在小博印象中哈希表是深奥的,是高大上的,但是接触原理以及看了一份demo之后我就觉得哈希表也就那样吧,接下来我把小博自己的理解尽量用最直白的语句来解释下~~~

    ---------------------------------------------------------我是分界线,没错,很丑------------------------------------------------------------------

    首先什么是哈希表???

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

    以上是一段在百度百科中的解释,如果还是不能理解,那么我就抽象的比喻一下。

    先看(是根据关键码值(Key value)而直接进行访问的数据结构),这里的关键码值以及数据结构可以用具体的物体代替一下,这里小博将关键码值用学号代替,数据结构用学生代替,学生与学号都是唯一的,可以根据学号直接找到学生。(说了一堆废话~~~~接下去才是重点)。

    场景演示一下,当我们需要将数据存入哈希表中的时候,就好像是一堆学生在办理入学,那么这时候有个地中海的大肚子男老师过来了,他对每个上前办理的学生说:你是XXX号,你所在的班级是YYY班,记住咯。然后这名学生就屁颠屁颠的去YYY班了。那么怎么查找呢??想必在学校中被校长点名过的同学应该都想到了,比如XXX号犯错了,他所在的班级是YYY一班,那么校长会说,在YYY一班的XXX号,你出来一下咱们好好喝喝茶~~这样校长就不用为了找XXX号同学而找遍每一个学生了,相对来说就是提升了查找效率。这是哈希表其中的一个特性————查找方便

    还有一个比较重要的特性,小博暂时没想到怎么怎么形象的比喻(原谅小博的见识浅薄~~囧)。另一个特性是空间高利用率,各位大老爷可能有几个一下子不能理解这个,请容小博详细说明,都知道需要存数据是需要容器的,数组,结构体等都是容器的一种,那么只要是容器都需要各自的空间(其实不仅仅是容器需要,其他也是一样的,但是相比之下其他占用的比较少罢了,继续正文),比如数组,当申请的时候需要一块连续的空间,而数据结构也是如此,申请的时候需要一块整个数据结构大小的空间,而且每次申请空间的时候,系统内部所为你划分的空间并不是一块挨着一块申请的,因此肯定会有少部分空间无法申请导致浪费,采用数据结构可以灵活的利用这些空间,采用链表将每个结构体联系起来,那么就形成了一个最简单的哈希表。直接上代码理解一下吧~~~~(写这些的时候小博已经神游,断片了,原谅小博的才疏学浅。)

    #include

    #include

    #include

    typedef struct ITEM

    {

    int val;

    int index;

    struct ITEM *next;

    }Item;

    typedef struct LIST

    {

    Item *head;

    Item *end;

    }List;

    #define HASH_VAL 10

    void insertItem(List* list, Item* item)

    {

    int key = (unsigned int)item->val%HASH_VAL;

    if (!list[key].head)

    {

    list[key].head = item;

    list[key].end = item;

    }

    else

    {

    list[key].end->next = item;

    list[key].end = item;

    }

    }

    void showList(List* list)

    {

    Item* p = NULL;

    for (int i = 0; i < 10; i++)

    {

    printf("%d:", i);

    p = list[i].head;

    if (p)

    {

    do

    {

    printf("%d(下标:%d) ", p->val, p->index);

    if (p->next)

    p = p->next;

    else

    break;

    } while (1);

    }

    printf("\n");

    }

    }

    bool aaa(int* a, int val)

    {

    for (int i = 0; i < 10; i++)

    {

    if (a[i] == val)

    return true;

    }

    return false;

    }

    bool serchItem(List* list, int val)

    {

    int key = (unsigned int)val%HASH_VAL;

    Item* p = list[key].head;

    while (p)

    {

    if (p->val == val)

    return true;

    p = p->next;

    }

    return false;

    }

    int main(int argc, char* argv[])

    {

    List list[10];

    Item item[10];

    memset(list, 0, sizeof(List)* 10);

    memset(item, 0, sizeof(Item)* 10);

    int a[10] = {21,11,1,51,5,6,7,8,9,0};

    for (int i = 0; i < 10; i++)

    {

    item[i].index = i;

    item[i].val = a[i];

    insertItem(list, &item[i]);

    }

    showList(list);

    system("pause");

    return 0;

    }

    小博演示的拉链法是将数组的特点(方便查找,不易删除)以及链表的特点(方便删除,不易查找)取长补短的一种折中方法。

    ----------------------------------------------分界线,又出现了-----------------------------------------------------------------

    文中好像很多废话,希望没有把各位大老爷给绕晕了,新人小白发表,不足之处请见谅,欢迎大牛指导,其他同道也可交流

    展开全文
  • 拉链法—构建哈希表

    2022-03-29 22:46:24
    输入一个序列,按照序列中的元素顺序,利用拉链法构造哈希表,输出哈希表的查询结果。哈希表的插入(插入同一线性链表时采用头插法) 输入 第一行数据分别表示序列的长度n,哈希表的长度m,以及用计算哈希函数...

    题目:

    题目描述
    输入一个序列,按照序列中的元素顺序,利用拉链法构造哈希表,输出哈希表的查询结果。哈希表的插入(插入同一线性链表时采用头插法)

    输入
    第一行数据分别表示序列的长度n,哈希表的长度m,以及用计算哈希函数(采用除留余数法)值的p,第二行表示由n个数据构成的序列,第三行表示待查询的元素

    例如输入样例1:
    11 13 13
    16 74 60 43 54 90 46 31 29 88 77
    29

    输出
    输出查询结果(若成功则输出Success,失败则输出Failure)以及比较次数

    例如针对样例1的输出为:
    Success 1

    样例输入 Copy
    11 13 13
    16 74 60 43 54 90 46 31 29 88 77
    29

    样例输出 Copy
    Success 1

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct LinkNode {
    	int data;
    	struct LinkNode* next;
    }LinkNode, * LinkList;
    
    struct {		//存放拉链法的下标
    	LinkList L;
    	int a;
    }s1[1000];
    
    void insert_head(LinkList L, int a) {	//头插法
    	LinkList Ltemp = new LinkNode();
    	Ltemp->data = a;
    	Ltemp->next = L->next;
    	L->next = Ltemp;
    }
    
    int main() {				//拉链法构造哈希表
    	int n, m, p;
    	cin >> n >> m >> p;
    
    	int i, j, temp;
    	int a[10000] = {};
    
    	for (i = 1; i <= n; i++) {
    		cin >> a[i];
    	}
    	int x;
    	cin >> x;
    
    	for (i = 0; i <= m; i++) {	//单链表初始化分配内存
    		s1[i].L = new LinkNode();
    	}
    
    	for (i = 1; i <= n; i++) {
    		temp = a[i] % p;		//除留余数 
    		insert_head(s1[temp].L, a[i]);	//该位置头插入该数 
    	}
    
    	int x_yushu = x % p;		//算出x除留余数后的结果 
    	int num = 0;
    	while (s1[x_yushu].L) {		//在该下标 单链表遍历查找x
    		if (s1[x_yushu].L->data == x) break;
    		num++;
    		s1[x_yushu].L = s1[x_yushu].L->next;
    	}
    	if (s1[x_yushu].L == NULL) {	//没找到
    		cout << "Failure " << num - 1 << endl;
    	}
    	else {
    		cout << "Success " << num << endl;
    	}
    	return 0;
    }

    测试结果:

    展开全文
  • 将哈希表理解为一个顺序表,顺序表里面存储的是一个链表(拉链法解决碰撞) 注:(hash & 0x7FFFFFFF)的作用:让hash值一直保持为正。 Because -1 % 10 == -1 which you certainly don’t want for indexing into...
  • 一、拉链法需要注意的是,拉链法中定义的几个数组分别为 h[N],e[N],ne[N],idx,他们所存放的值以及其下标代表的含义:h[N]: 下标为哈希后的值,所存放的值是指针,指向拉链的第一个元素,也就是拉链后第一个元素的...
  • 一、散列查找 (一)散列表(Hash Table) 散列表(Hash Table),又称哈希表。是⼀种数据结构,特点是:数据元素的关键字与其存储...用拉链法(又称链接法、链地址法)处理“冲突”:把所有“同义词”存储在一个链表中
  • 拉链法和线性探测法

    2019-07-24 20:47:00
    除留余数,选择大小为素数M的数组,对于任意正整数k ,计算k除以M的余数。 如果M不是素数,我们可能无法利用键中包含的所有信息,这可能导致我们无法均匀地散列散列值 浮点数 第一,如果键是0-1的实数,我们可以将...
  • 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码易语言拉链法哈希表源码.rar 易语言源码...
  • 数据范围 1≤N≤1e5 −1e9≤x≤1e9 输入样例: 5 I 1 I 2 I 3 Q 2 Q 5 输出样例: Yes No 代码如下: 第一种方法(拉链法): 单链表的使用:22. 单链表(c++)_AMG GTR的博客-CSDN博客 #include #include using ...
  • 开放寻址法和拉链法十分类似,只是处理冲突的方式不一样。拉链法通过在冲突位置开链表解决,开放寻址法通过往后顺次找空位置解决。 拉链法: #include<iostream> #include<cstdio> #include<vector&...
  • 自己手撸了一下拉链法解决散列冲突的算法,代码如下: #include <iostream> #include <vector> #define N 1000 using namespace std; typedef struct ChainNodes { int data; ChainNodes* Next; }...
  • #include <stdio.h> #include <stdlib.h> #include <string.h> #define max 15 /*1、输入10个一百以内的数,用x%15作为哈希...2、输入10个一百以内的数,用x%15作为哈希函数,用拉链法作为存储结构。
  • 另一种是拉链法,首先计算应该映射的位置,然后在该位置上再建立一条链,存储相应映射到该位置的数据,查找时,也是对于链上元素进行遍历,删除时只需要打上标记,通常不实际进行删除。 1、开放定址法 例如解决如题...
  • 哈希表实现
  • 线性探测 即从发生冲突的地址(记做d)开始,依次探查d的下一个地址,直至找到一个空位置为止。记住这句话。查找时若查到空位置还没有找到需要查找的元素则说明不在列表中。冲突次数为找到该余数位置但已经被前面...
  • 用java写的拉链法实现哈希表的建立,应用到类似于电话本查询的程序里,课程设计时候做的,所以不是很完美
  • 2.拉链法 哈希表的主要作用: 把一个较大(0-10^9 )的数据映射到较小(0-N(N一般为10^5 到 10^6))的数据 哈希函数:可以把一个从-10^19 到10^19 的中的一个数映射到0-10^5之间的一个数 1.哈希函数怎么写? 一般情况下...
  • 哈希拉链法

    2018-10-16 17:19:28
    哈希拉链法 前言 前面学习到的几种算法比如 红黑树 , 二叉搜索树 ,查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一种算法可以使查找插入 时间复杂度 达到常数级别。 散列表(Hash table) 也...
  • HashMap拉链法简介

    千次阅读 2020-05-20 10:28:49
    拉链法用途 解决hash冲突(即put操作时计算key值问题)。 拉链法原理 把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。 有m个散列地址就有m个链表,同时用指针数组A[0,1,2…m-1]存放各个...
  • 数据结构——拉链法(链地址法)

    千次阅读 2019-12-10 20:54:16
    当存储结构是链表时,多采用拉链法,用拉链法处理冲突的办法是:把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0..m-1]存放各个链表的头...
  • 哈希——拉链法

    千次阅读 2018-03-01 15:25:06
    首先写哈希——拉链法要知道哈希冲突。 哈希冲突: 对于两个数据元素的关键字 Ki 和 Kj (i != j),有 Ki != J ,但有: HashFun(Ki) == HashFun(Kj) 即不同关键字通过相同哈希哈数计算出相同的哈希地址,该种...
  • 在工业界,主要用拉链法来解决哈希冲突,称之为哈希桶的概念。请实现一个简单的哈希表,将如下信息,插入到哈希表中。 哈希表的哈希桶数量设置为10,以员工编号为input来计算哈希后的key,哈希函数使用取余法,编码...
  • 哈希表之拉链法

    2019-10-09 03:59:53
     小博演示的拉链法是将数组的特点(方便查找,不易删除)以及链表的特点(方便删除,不易查找)取长补短的一种折中方法。 ----------------------------------------------分界线,又出现了---------------------...
  • 开放地址法和拉链法的优缺点? 开放地址法: 会产生堆积问题,不适合大规模的数据存储,插入时,可能会出现多次冲突的情况,删除数据时,其他数据也有影响,实现相对较为复杂。且节点规模大时,再平方探测会浪费空间...
  • 用索引‘’‘ 线性探测与拉链法解决哈希冲突 首先,对数据进行一个分组,以整型为例。选定一个分组标准,也就是一个间隔,就是怎么分,隔几个数分一组。以上述问题为例,100w分成0~99各组,即每个数据的值都对100...
  • 哈希表(拉链法解决冲突)

    千次阅读 2020-06-10 22:57:22
    Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 实现...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,146
精华内容 7,658
关键字:

拉链法

友情链接: python_2.7.13150.rar