精华内容
下载资源
问答
  • 哈希表查找失败的平均查找长度

    千次阅读 2019-10-09 18:02:18
    “它是中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。” 理解: 1. 散列表中已经含有之前插入的元素。 即已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。 2. 这...

    “它是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。” 理解:

    1. 散列表中已经含有之前插入的元素。

        即表已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。

    2. 这个位置是散列函数函数可以散列到的位置,不一定是表的总长。

        如:散列函数为H(key) = (keyx3) MOD 10,而表长为15,此时ASLunsucess=..../10 (而不是/15)。

       另外计算总长度时是以初始位置到散列终点位置为范围计算的,即上面这个例子是从0-9插入计算的。

    3. 计算总长度时以计算出来的位置到找到空桶为标准计算。

    展开全文
  • 采用除留余数法实现哈希表的创建,任意采用一种处理冲突的方法解决冲突,计算哈希表的平均查找长度。实现以下功能:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数定义为:H(key)=key MOD 13, 哈希...

    采用除留余数法实现哈希表的创建,任意采用一种处理冲突的方法解决冲突,计算哈希表的平均查找长度。实现以下功能:

    已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数定义为:H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列,并计算平均查找长度(设每个记录的查找概率相等)。

    (1)哈希表定义为定长的数组结构;

    (2)使用线性探测再散列或链地址法解决冲突;

    (3)散列完成后在屏幕上输出数组内容或链表;

    (4)输出等概率查找下的平均查找长度;

    (5)完成散列后,输入关键字完成查找操作,要分别测试查找成功与查找不成功两种情况。

    一、函数间的调用关系

    ff73ae8c9679f0b0ed29f8e24c2bc76a.png

    二、相关算法描述

    1、散列表的创建(除留余数法)算法

    准备工作:将所有散列表初始化为NULLKEY.循环一组关键字个数次,执行以下:

                    ①调用Hash()函数,除留余数法求得放入关键字地址H0

                   ②进入第一个条件判断,判断①得到的地址H0是否为NULLKEY,若单元H0为空,将关键字放入此单元,同时计数器count加一操作,统计关键字比较的次数

                   ③如果条件②不满足,说明利用散列函数得到的单元已经存在关键字,利用线性探测法找下一个散列地址Hi,通过while循环找到新单元地址,循环条件为(HT[Hi].key!=NULLKEY),每循环一次,计数器count加一

                    ④当跳出while循环,说明已经找到没有关键字的单元,可以将关键字key存入,计数器count加一

                    ⑤调用Disp()函数,循环关键字次数输入散列表在屏幕

                    ⑥通过引用传递,将计数器count的数值带回,可以计算出平均查找长度的值

    for (int i = 1;i <= 12;++i)  {    cout << "请输入第" << i << "个关键字:";    cin >> key;    H0 = Hash(key);                    //除留余数法求得插入的地址H0    if (HT[H0].key == NULLKEY)    {      HT[H0].key = key;                //若单元H0为空,将关键字放入此单元      count++;    }                          //if    else    {      int i = 1;      Hi = H0;                    //进入else,说明当前地址为H0的单元不为空      while (HT[Hi].key != NULLKEY)          //当地址Hi对应的单元为空的时候跳出循环      {        Hi = (H0 + i) % MAXSIZE;          //按照线性探测法计算下一个散列地址Hi        ++i;                    //步长+1        count++;      }      HT[Hi].key = key;                //关键字key存放到地址为Hi的单元中      count++;    }                          //else  }

    2、散列表的查找(采用线性探测法处理冲突)

    ①根据散列函s数Hah(key)计算散列地址,若单元H0为空,则所查元素不存在,若单元H0中的关键字为key,则查找成功

    按照线性探测法计算下一个散列地址Hi,若单元Hi为空,则所查元素不存在,若单元H0中的关键字为key,则查找成功

    H0 = Hash(key);                      //根据散列函数Hash(key)计算散列地址  if (HT[H0].key == NULLKEY)    return -1;                      //若单元H0为空,则所查元素不存在  else if (HT[H0].key == key)    return H0;                      //若单元H0中的关键字为key,则查找成功  else  {    for (int i = 1;i < MAXSIZE;++i)    {      Hi = (H0 + i) % MAXSIZE;            //按照线性探测法计算下一个散列地址Hi      if (HT[Hi].key == NULLKEY)        return -1;                  //若单元Hi为空,则所查元素不存在      else if (HT[Hi].key == key)        return Hi;                  //若单元H0中的关键字为key,则查找成功    }                          //for    return -1;  }

    三、完整源码

    #include#includeusing namespace std;#define MAXSIZE 16                      //定长哈希表长度#define NULLKEY 0                      //单元为空的标记typedef int KeyType;typedef int InfoType;/*哈希表的存储结构*/typedef struct{  KeyType key;                      //关键字项目  InfoType otherinfo;                    //其他数据项}HashTable[MAXSIZE];/*散列函数,求散列地址*/int Hash(KeyType key){  return key % 13;                    //除留余数法}/*初始化数组*/void Init(HashTable& HT){  for (int i = 1;i <= 12;i++)    HT[i].key=NULLKEY;                  //初始化将哈希表等长数组的所有单元置为NULLKEY  cout << "数组初始化完成" << endl;}/*散列表的创建,除留余数法*/void CreateHash(HashTable &HT,int &number){  int key,H0,Hi,count=0;  cout << "给出一组关键字:19,14,23,1,68,20,84,27,55,11,10,79" << endl;  for (int i = 1;i <= 12;++i)  {    cout << "请输入第" << i << "个关键字:";    cin >> key;    H0 = Hash(key);                    //除留余数法求得插入的地址H0    if (HT[H0].key == NULLKEY)    {      HT[H0].key = key;                //若单元H0为空,将关键字放入此单元      count++;    }                          //if    else    {      int i = 1;      Hi = H0;                    //进入else,说明当前地址为H0的单元不为空      while (HT[Hi].key != NULLKEY)          //当地址Hi对应的单元为空的时候跳出循环      {        Hi = (H0 + i) % MAXSIZE;          //按照线性探测法计算下一个散列地址Hi        ++i;                    //步长+1        count++;      }      HT[Hi].key = key;                //关键字key存放到地址为Hi的单元中      count++;    }                          //else  }  number = count;}/*散列表的查找,采用线性探测法处理冲突*/int SearchHash(HashTable HT, KeyType key){  //在散列表HT中查找关键字为key的元素,若查找成功,则返回散列表的单元标号,否则返回-1  int H0, Hi;  H0 = Hash(key);                      //根据散列函数Hash(key)计算散列地址  if (HT[H0].key == NULLKEY)    return -1;                      //若单元H0为空,则所查元素不存在  else if (HT[H0].key == key)    return H0;                      //若单元H0中的关键字为key,则查找成功  else  {    for (int i = 1;i < MAXSIZE;++i)    {      Hi = (H0 + i) % MAXSIZE;            //按照线性探测法计算下一个散列地址Hi      if (HT[Hi].key == NULLKEY)        return -1;                  //若单元Hi为空,则所查元素不存在      else if (HT[Hi].key == key)        return Hi;                  //若单元H0中的关键字为key,则查找成功    }                          //for    return -1;  }                            //else}/*在屏幕上输出数组内容*/void Disp(HashTable HT){  cout << endl << "哈希表中的内容为:";  for (int i = 1;i <= 12;i++)    cout << HT[i].key << setw(5);        //输出哈希表中的内容  cout << endl;}int main(void){  KeyType key;  int number;  HashTable HT;                        Init(HT);                        //初始化数组单元都为NULLKEY  CreateHash(HT,number);                      //创建哈希表  Disp(HT);                        //输出到屏幕上  cout << "输出等概率查找条件下的平均查找长度" << (number*1.0) / 12 << endl;  //输出等概率查找条件下的平均查找长度  do  {    cout << "请输入要查找的关键字key:";    cin >> key;                        //输入要查找的关键字    if (SearchHash(HT, key) == -1)      cout << "查找失败,关键字不存在!" << endl;      //若返回下标为-1,则查找失败    else      cout << "查找成功,其关键字在哈希表中的位置为:" << SearchHash(HT, key);//查找成功,输出其在哈希表中的地址    cout << endl;  } while (key >= 0);  return 0;}

    四、调试结果

    c76326a546e88cd5fdda88721dcdefcd.png

    展开全文
  • 有关HashMap(哈希表部分理解:HashMap是一个散列表,存储是键值对(key-value),能够快速地查找所需对象(O(1)时间复杂度)。HashMap有两个影响其性能参数:“初始容量”-哈希表在创建时容量;...

    有关HashMap(哈希表)的部分理解:

    HashMap是一个散列表,存储的是键值对(key-value),能够快速地查找所需的对象(O(1)时间复杂度)。

    HashMap有两个影响其性能的参数:“初始容量”-哈希表在创建时的容量;“加载因子”-哈希表在其容量自动增加前可以达到多满的一种尺度。当HashMap中的条目数超出了加载因子与当前容量的乘积时,则需对HashMap进行重建内部数据结构操作(即rehash)。

    HashMap的构造函数:

    1,HashMap():默认构造函数

    2,HashMap(int capacity):指定容量大小的构造函数

    3,HashMap(int capacity,float loadFactor):指定容量大小和加载因子的构造函数

    4,HashMap(Map<? extends K,? extends V> map):包含子Map的构造函数

    HashMap的部分函数:

    1,clear()--清空HashMap,它是通过将所有的元素设为null来实现的。

    2,get(Object k) --获取key对应的value

    3,put(K key, V value) --对外提供接口,让HashMap对象可以通过put()将“key-value”添

    加到HashMap中。

    。。。

    那么HashMap是怎么存储的呢?

    Hash表的主干就是数组,它利用在数组中能根据下标查找某个元素,一次定位就可以达到的这种特性,比如如果要新增或查找某个元素,通过把当前元素的关键字,通过某个函数映射到数组中的某个位置,通过数组的下标定位就可以完成操作。

    bf27f61803394d6f809eb32588833f11.png
    存储位置=哈希函数(关键字)

    然而,此时的HashMap还不是完美的,如果两个不同的元素,通过哈希函数得到的存储地址相同怎么办呢?这就是发生了哈希冲突了。哈希冲突的解决方法有很多种,其中有一种是链地址法,也就是数组+链表的方式。

    前面已经说过了,HashMap的主干是entry数组,而链表主要是为了解决哈希冲突的。在HashMap中如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找、添加等操作很快,只需要一次寻址即可;如果定位到的数组包含链表,对于添加操作,时间复杂度为0(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作,仍需要遍历链表,通过key对象的equals方法逐一对比查找。那么,对于HashMap,链表出现越少,性能就越好。

    :HashMap的数组长度一定要是2的次幂。

    当发生哈希冲突并且size大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为

    之前数组2倍的新的数组,然后将当前的Entry数组中的元素全部传输过去,扩容后的新数组长

    度为之前的2倍。

    附:其他数据结构性能

    数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过

    给定值进行查找,需要遍历数组,时间复杂度为O(n),若是有序数组,可采用二分法查找,插

    值查找等方式,可将时间复杂度提高为O(logn);对于一般的插入删除操作,涉及到数组元素

    的移动,平均复杂度也为O(n)。

    线性链表:对于链表的新增、删除等操作(在找到指定操作位置后),仅需处理结点间的引用

    即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行对比,时间复杂度为O(n).

    二叉树:对一棵相对平衡的有序二叉树,对其进行插入、查找、删除等操作,平均复杂度为O

    (logn)。

    展开全文
  • 散列表动态扩容解答+面试题一、散列表(哈希表、Hash 表)不同与之前我们介绍线性表,所有数据都是顺序存储,当我们需要在线性表中查找某一数据时,当线性表过长,需要查找的数据排序比较靠后话,就需要花费...

    引言

    本节由一道头条面试题:如何设计哈希函数以及如何解决冲突问题展开,由以下几个方面进行循序渐进的阐述:

    • 什么是散列表?
    • 什么是散列函数?
    • 常见的散列函数有哪些?
    • 冲突又怎么解决喃?
    • 散列表的动态扩容
    • 解答
    • +面试题

    一、散列表(哈希表、Hash 表)

    不同与之前我们介绍的线性表,所有的数据都是顺序存储,当我们需要在线性表中查找某一数据时,当线性表过长,需要查找的数据排序比较靠后的话,就需要花费大量的时间,导致查找性能较差。

    例如学号,如果你想通过学号去找某一名学生,假设有 n 学生,难道你要一个一个的找,这时间复杂度就为 O(n),效率太低。当然你也可以使用二分查找算法,那时间复杂度就为 O(logn),有没有更高效的解决方案喃?

    我们知道数组通过下标查找的时间复杂度为 O(1),如果我们将学号存储在数组里,那就简单多了,我们可以直接通过下标(key)找到对应的学生。

    但日常生活中,key 一般都赋予特定的含义,使用 0,1,2 ... 太过简单了。学号通常都需要加上年级、班级等信息,学号为 010121 代表 1年级,1 班,21号。我们知道某一同学的学号就可以直接找到对应的学生。

    这就是散列! 通过给定的学号,去访问一种转换算法(将学号010121转换为1年级,1 班,21号的方法),得到对应的学生所在地址(1年级,1 班,21号)。

    其中这种转换算法称为散列函数(哈希函数、Hash 函数),给定的 key 称为关键字,关键字通过散列函数计算出来的值则称为散列值(哈希值、Hash 值)。通过散列值到 散列表(哈希表、Hash 表)中就可以获取检索值。

    如下图:

    17b89cabec1518010aa3880a193ca377.png

    也可以说,散列函数的作用就是给定一个键值,然后返回值在表中的地址。

    // 散列表
    function HashTable({
      let table = []
      this.put = function(key, value{}
      this.get = function(key{}
      this.remove = function(key{}
    }

    继续看上面学号的例子,每个学生对应一个学号,如果学生较多,假如有 10w 个,那我们需要存储的就有

    • 10w 个学号,每个学号 6 个十进制数,一个十进制数用 4 bit 表示(1个字节=8bit)
    • 散列函数
    • 10w 个学生信息

    这就需要多花 100000 * 6 / 2 / 1024  = 292.97 KB 的存储容量用于存储每个学生的学号,所以,散列表是一种空间换时间的存储结构,是在算法中提升效率的一种比较常用的方式,但是所需空间太大也会让人头疼,所以通常需要在二者之间权衡。

    二、散列函数

    这里,需要了解的是,构造散列函数应遵循的 原则 是:

    • 散列值(value)是一个非负数:常见的学号、内存寻址呀,都要求散列值不可能是负数
    • key 值相同,通过散列函数计算出来的散列值(value)一定相同
    • key 值不同,通过散列函数计算出来的散列值(value)不一定不相同

    再看一个例子:学校最近要盖一个图书馆,用于学生自习,如果给每位学生提供单独的小桌子的话,就需要 10w 张,这显然是不可能的,那么,有没有办法在得到 O(1) 的查找效率的同时、又不付出太大的空间代价呢?

    散列函数就提供了这种解决方案,10w 是多,但如果我们除以 100 喃,那就 0~999,这就很好找了,也不需要那么多桌子了。

    ca27a3619cea6a15671abc792d164046.png

    对应的散列函数就是:

    function hashTables(key{
        return Math.floor(key / 100)
    }

    但在实际开发应用中,场景不可能这么简单,实现散列函数的方式也可能有很多种,例如上例,散列函数也可以是:

    function hashTables(key{
        return key >= 1000 ? 999 : key
    }

    这个实现的散列函数相对于上一个在 999 号桌的冲突概率就高得多,所以,选择一个表现良好的散列函数就至关重要

    1. 创建更好的散列函数

    一个表现良好的散列函数可以大量的提高我们代码的性能,它有更快的查找、插入、删除等操作,更少的冲突,占用更小的存储空间。所以构建一个高性能的散列函数对我们至关重要。

    一个好的散列函数需要具有以下基本要求:

    • 易于计算:它应该易于计算,并且不能成为算法本身。
    • 统一分布:它应该在哈希表中提供统一分布,不应导致群集。
    • 较少的冲突:当元素对映射到相同的哈希值时发生冲突。应该避免这些。

    2. 常见的散列函数

    • 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。
    • 数字分析法:通过对数据的分析,发现数据中冲突较少的部分,并构造散列地址。例如同学们的学号,通常同一届学生的学号,其中前面的部分差别不太大,所以用后面的部分来构造散列地址。
    • 平方取中法:当无法确定关键字里哪几位的分布相对比较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为散列地址。这是因为:计算平方之后的中间几位和关键字中的每一位都相关,所以不同的关键字会以较高的概率产生不同的散列地址。
    • 取随机数法:使用一个随机函数,取关键字的随机值作为散列地址,这种方式通常用于关键字长度不同的场合。
    • 除留取余法:取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要,一般取素数或者直接用 n。

    注意:无论散列函数有多健壮,都必然会发生冲突。因此,为了保持哈希表的性能,通过各种冲突解决技术来管理冲突是很重要的。

    例如上例会存在一个问题,学号为 011111 与 021111 的学生,他们除以 100 后都是 111 ,这就冲突了。

    三、冲突解决

    在散列里,冲突是不可避免的。那怎样解决冲突喃?

    常见的解决冲突方法有几个:

    • 开放地址法(也叫开放寻址法):实际上就是当需要存储值时,对Key哈希之后,发现这个地址已经有值了,这时该怎么办?不能放在这个地址,不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希,比如往后移动一个地址,如果没人占用,就用这个地址。如果超过最大长度,则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
    • 链地址法:链地址法其实就是对Key通过哈希之后落在同一个地址上的值,做一个链表。其实在很多高级语言的实现当中,也是使用这种方式处理冲突的,我们会在后面着重学习这种方式。
    • 再哈希法:在产生冲突之后,使用关键字的其他部分继续计算地址,如果还是有冲突,则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
    • 建立一个公共溢出区:这种方式是建立一个公共溢出区,当地址存在冲突时,把新的地址放在公共溢出区里。

    我们这里介绍两个最简单的:开放寻址法里的线性探测,以及链地址法。

    1. 线性探测

    线性探测是开放寻址里最简单的方法,当往散列表中增加一个新的元素值时,如果索引为 index 的位置已经被占用了,那么就尝试 index + 1 的位置,如果 index + 1 的位置也被占用了,那就尝试 index + 2 的位置,以此类推,如果尝试到表尾也没找到空闲位置,则从表头开始,继续尝试,直到放入散列表中。

    如下图:

    909498d2056ee86274bb8d07a96f045a.png

    如果是删除喃:首先排查由散列函数计算得出的散列值,与要查找的散列值对比,相同则删除元素,如果该节点为空了,则设为 undefined ,不相等则继续比较 index + 1 ,以此类推,直到相等或遍历完整个散列表。

    如果是查找喃:首先排查由散列函数计算得出的散列值,与要查找的散列值对比是否相等,相等则查找完成,不相等继续排查 index + 1 ,直到遇到空闲节点( undefined 节点忽略不计),则返回查找失败,散列表中没有查找值。

    很简单,但它也有自己的局限性,当散列表中元素越来越多时,冲突的几率就越来越大。

    最坏情况下的时间复杂度为 O(n)。

    2. 链地址法

    链地址也很简单,它给每一个散列表中的节点建立一个链表,关键字 key 通过散列函数转换为散列值,找到散列表中对应的节点时,放入对应链表中即可。

    如下图:

    0d157c95462baf396a05151abb3db0ed.png

    插入:像对应的链表中插入一条数据,时间复杂度为 O(1)

    查找或删除:从链头开始,查找、删除的时间复杂度为 O(k),k为链表的长度

    四、动态扩容

    前面在介绍数组的时候,我们已经介绍过扩容,在 JavaScript 中,当数组 push 一个数据时,如果数组容量不足,则 JavaScript 会动态扩容,新容量为老的容量的 1.5 倍加上 16。

    在散列表中,随着散列值不断的加入散列表中,散列表中数据越来越慢,冲突的几率越来越大,查找、插入、删除等操作的时间复杂度越来越高,散列表也需要不断的动态扩容。

    五、回答开头问题

    如何设计哈希函数以及如何解决冲突,这是哈希表考察的重要问题。

    如何设计哈希函数?

    一个好的散列函数需要具有以下基本要求:

    • 易于计算:它应该易于计算,并且不能成为算法本身。
    • 统一分布:它应该在哈希表中提供统一分布,不应导致群集。
    • 较少的冲突:当元素对映射到相同的哈希值时发生冲突。应该避免这些。

    如何解决冲突?

    常见的解决冲突方法有几个:

    • 开放地址法(也叫开放寻址法):实际上就是当需要存储值时,对Key哈希之后,发现这个地址已经有值了,这时该怎么办?不能放在这个地址,不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希,比如往后移动一个地址,如果没人占用,就用这个地址。如果超过最大长度,则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
    • 链地址法:链地址法其实就是对Key通过哈希之后落在同一个地址上的值,做一个链表。其实在很多高级语言的实现当中,也是使用这种方式处理冲突的,我们会在后面着重学习这种方式。
    • 再哈希法:在产生冲突之后,使用关键字的其他部分继续计算地址,如果还是有冲突,则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
    • 建立一个公共溢出区:这种方式是建立一个公共溢出区,当地址存在冲突时,把新的地址放在公共溢出区里。

    六、常见的哈希表问题

    我们已经刷过的(https://github.com/sisterAn/JavaScript-Algorithms):

    • 腾讯&leetcode349:给定两个数组,编写一个函数来计算它们的交集
    • 字节&leetcode1:两数之和
    • 腾讯&leetcode15:三数之和

    今天刷一道 leetcode380:常数时间插入、删除和获取随机元素

    leetcode380:常数时间插入、删除和获取随机元素

    设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。

    • insert(val) :当元素 val 不存在时,向集合中插入该项。
    • remove(val) :元素 val 存在时,从集合中移除该项。
    • getRandom :随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

    示例 :

    // 初始化一个空的集合。
    RandomizedSet randomSet = new RandomizedSet();

    // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
    randomSet.insert(1);

    // 返回 false ,表示集合中不存在 2 。
    randomSet.remove(2);

    // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
    randomSet.insert(2);

    // getRandom 应随机返回 1 或 2 。
    randomSet.getRandom();

    // 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。
    randomSet.remove(1);

    // 2 已在集合中,所以返回 false 。
    randomSet.insert(2);

    // 由于 2 是集合中唯一的数字,getRandom 总是返回 2 。
    randomSet.getRandom();

    欢迎将解答提到 https://github.com/sisterAn/JavaScript-Algorithms/issues/48 ,这里我们提交了前端所用到的算法系列文章以及题目(已解答),欢迎star,如果感觉不错,点个在看支持一下呗?

    瓶子君将明日解答?

    阅读❤️

    欢迎关注「前端瓶子君」,回复「交流」加入前端交流群!

    欢迎关注「前端瓶子君」,回复「算法」自动加入,从0到1构建完整的数据结构与算法体系!

    在这里,瓶子君不仅介绍算法,还将算法与前端各个领域进行结合,包括浏览器、HTTP、V8、React、Vue源码等。

    在这里,你可以每天学习一道大厂算法题(阿里、腾讯、百度、字节等等)或 leetcode,瓶子君都会在第二天解答哟!

    04df27b5f9059185f17505c0ab5920b5.png
    》》面试官也在看的算法资料《《

    “在看转发”是最大的支持

    展开全文
  • 题图Pid=68670770在最近学习过程中,发现身边很多朋友对哈希表的原理和应用场景不甚了解,处于会用但不知道什么时候该用状态,所以我找出了刚学习Java时写HashMap实现,并以此为基础拓展关于哈希表的实现原理...
  • 本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/5vxYoeARG1nC7Z0xTYXELA作者:Xuegui Chen哈希是一种通过对数据进行压缩, 从而提高效率一种解决方法,但由于...一、哈希表概述哈希表的...
  • 也就是说,它通过把关键码值映射到中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,记为 Hash(key) = Addr 这里地址是数组下标、索引或内存地址等)。存放记录数组叫做散列表。②什么是...
  • Hash表也称散列表,也有直接译作哈希表,Hash表是一种特殊数据结构,它同数组、链表以及二叉排序树等相比较有很明显区别,它能够快速定位到想要查找的记录,而不是与表中存在记录关键字进行比较来进行查找。...
  • 但是在翻阅了大部分HashMap相关文章之后,发现大多数文章都是对HashMap源码分析,丝毫没有提到哈希表的概念。这就导致了很多人只记住了HashMap原理,却不知哈希表为何物奇特现象。很多情况下,面试官可能并...
  • 一、哈希表概述哈希表的哈希函数输入一个键,并向返回一个哈希表的索引。可能集合很大,但是哈希函数值集合只是表大小。哈希函数其他用途包括密码系统、消息摘要系统、数字签名系统,为了使这些应用程.....
  • 如何计算哈希表查找失败的平均查找长度

    千次阅读 多人点赞 2020-04-30 18:20:01
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录...
  • ![图片说明](https://img-ask.csdn.net/upload/201602/09/1455031746_265651.png) 这个失败的长度是怎么计算出来的? 分子是怎么来的? 请大家具体讲讲~
  • 等概率情况下查找不成功的平均查找长度: 接下来讨论不成功的情况, 看2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率...
  • 哈希表查找不成功的平均查找长度

    千次阅读 2017-05-27 10:40:52
    1.查找失败的情况:哈希表中不存在这个元素才会查找失败 2.查找失败的判定;见书 3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认...
  • 散列技术时记录存储位置和它关键字之间建立一个确定对应关系f,使得每个关键字key对应一个存储位置f(key),查找时根据这个对应关系找到给定值key映射f(key),若查找集合中存储这个记录,则必定在f(key)...
  • 散列表 散列表(Hash table,也叫哈希表)【也被称:散列映射、映射、字典和关联数组】,是根据键(key)而直接访问在内存存储位置数据结构。它通过计算一个关于键值函数,将所需查询数据映射到表中一个位置来...
  • 一,散列表基本概念直接将元素储存位置和其关键字之间建立某种直接关系,那么在进行查找时,就无需做比较或做很少次比较,按照这种关系直接由关键字找到相应记录,这就是散列表查找思想。它通过对元素...
  • 创建与输入数组相等长度的新数组,作为直接寻址。两数之和期望是Target,将Target依次减输入数组元素,得到值和直接寻址比较,如果寻址存在这个值则返回;如果不存在这个值则将输入数组中元素插入寻址...
  • 设哈希函数H(K)=3Kmod11,哈希地址空间为0~10,对关键字序列(32,13,49,24,38,21,4,12),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失败的平均查找长度ASLsucc和...
  • 在利用线性探测再散列法处理冲突的散列表中,很多人对计算失败的平均查找长度,作除数应该是散列表长,还是散列函数:mod后面的数不清楚,首先接下来我们先解决这一问题. 问题一:其除以的数是mod后面的数还是散列表长? ...
  • 请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15, 设每个...
  • 最近学了数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 Question1: 将关键字序列...
  • 散列思想散列表英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash表”,你一定也经常听过它,我在前面文章里,也不止一次提到过,但是你是不是真理解这种数据结构呢?散列表用是数组支持按照下标...
  • 什么是散列表散列表(hash table),我们平时叫它哈希表或者Hash 表,你肯定经常听到它。散列表是根据关键码值(Key value)而直接进行访问数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以...
  • 哈希表的实现

    2019-10-14 23:18:18
    哈希表容易造成冲突,为了避免冲突: 1.尽可能的让出来的下标符合均匀分布。 2.负载因子的调节 负载因子=哈希表中的数据个数/...求成功的平均查找长度和失败的平均查找长度 代码实现开散列 public class Hash { ...
  • 请画出按照线性探测再散列处理冲突得到的哈希表(给出求解过程),并计算查找成功和查找失败的平均查找长度各是多少。 请画出按照链地址法处理冲突得到的哈希表,并计算查找成功和查找失败的平均查找长度各是...
  • 请画出按照线性探测再散列处理冲突得到的哈希表(给出求解过程),并计算查找成功和查找失败的平均查找长度各是多少。 请画出按照链地址法处理冲突得到的哈希表,并计算查找成功和查找失败的平均查找长度各是...

空空如也

空空如也

1 2 3
收藏数 48
精华内容 19
关键字:

哈希表查找失败的平均查找长度