精华内容
下载资源
问答
  • 采用除留余数法实现哈希表的创建,任意采用一种处理冲突的方法解决冲突,计算哈希表的平均查找长度。实现以下功能:已知一组关键字(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

    展开全文
  • 如何计算哈希表查找失败时的平均查找长度

    千次阅读 多人点赞 2020-04-30 18:20:01
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录...

    题目描述:
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算?
    例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
    哈希函数为: H(key)=key MOD 13,哈希表长为m=15,设每个记录的查找概率相等,采用以上两种方法处理冲突,查找失败时的平均查找长度各是多少?

    今天数据结构老师讲的哈希表,留了一个“如何计算哈希表查找失败时的平均查找长度”可是把我给难为住了。(从中午12:00到下午16:00才搞懂,果然还是我太vegetable了

    几个小伙儿伴纷纷查资料,又是计算又是讨论,但是始终没有得到一致的结论。

    纠结的点主要就是:分母应该是哈希表长还是哈希函数里所给的MOD后面的13呢。查了很多资料发现里面的说法不一,而且查到的每一篇博客所给的题目都是除数(MOD后面的那个数)和哈希表长相等。(啊,可能我找的太少啦吧,找啦两三篇都是这样就去问老师啦)

    后来同学告诉我慕课上面讲的就有...anyway~现在是懂了,下面我就用大白话来描述一下我对这个“查找失败时的平均查找长度”的理解

    查找失败的次数就是指:根据哈希函数算出来你所要查找的关键字的位置,如果这个位置存的不是你的目标关键字,那么就按照你所定的存储哈希函数的规则,也就是所在位置+1向后寻找,直到找到你所要的关键字,如果遇到了表中的空位,那么就说明这个表中没有这个关键字,那么查找失败的次数就是你从“通过哈希函数算出的位置”到“表中的第一个遇到的空位”所经过的位数

    也就是说,分母指的是哈希表所给定的长度!!!

    就比如说,你的哈希表如下所示(由上面题目“采用线性探测再散列”生成的哈希表;):

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
      14 1 68 27 55 19 20 84 79 23 11 10    

    创建过程为:按照关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入

    现在我问你:我想要查找关键字“2”,那么我需要比较多少次才能知道失败了呢?

    答:根据所生成的表可以很容易的看出,关键字“2”不存在于表中。通过题目所给的哈希函数H(key)=key MOD 13可以算出关键字“2”应该在表中序号为2的位置,而如果2的位置所存的数与关键字“2”不相等,那么我需要按照“线性探测”直到找到关键字“2”。如果我没有找到关键字“2”,反而是遇到了空的位置,那么就说明关键字“2”查找失败了,那么我所走的步数就是查找失败的次数。把所有的位置查找失败的次数加起来除以表的总长度,就是“查找失败时的平均查找长度”

    ps:如果有错误欢迎指正,来自一个卑微的计算机大学僧

    答案(以线性探测再散列为例):第一行:序号;第二行:关键字;第三行:查找成功时查找长度;第四行:查找失败时查找长度

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
      14 1 68 27 55 19 20 84 79 23 11 10    
      1 2 1 4 3 1 1 3 9 1 1 3    
    1 13 12 11 10 9 8 7 6 5 4 3 2 1 1

    查找失败时的平均查找长度=(1+13+12+11+10+9+8+7+6+5+4+3+2+1+1)/ 15 = 93 / 15

    展开全文
  • 有关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)。

    展开全文
  • 题图Pid=68670770在最近的学习过程中,发现身边很多朋友对哈希表的原理和应用场景不甚了解,处于会用但不知道什么时候该用的状态,所以我找出了刚学习Java时写的HashMap实现,并以此为基础拓展关于哈希表的实现原理...
    题图Pid=68670770

    在最近的学习过程中,发现身边很多朋友对哈希表的原理和应用场景不甚了解,处于会用但不知道什么时候该用的状态,所以我找出了刚学习Java时写的HashMap实现,并以此为基础拓展关于哈希表的实现原理。

    什么是哈希表?

    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

    以上正式的解释摘自百度百科哈希表页面。

    从这段解释中,我们理应知道的:

    • 哈希表是一种数据结构
    • 哈希表表示了关键码值和记录的映射关系
    • 哈希表可以加快查找速度
    • 任意哈希表,都满足有哈希函数f(key),代入任意key值都可以获取包含该key值的记录在表中的地址

    官方解释听过了,那么如何用大白话来解释呢?

    简单的来说,哈希表是一种表结构,我们可以直接根据给定的key值计算出目标位置。在工程中这一表结构实现通常采用数组。

    与普通的列表不同的地方在于,普通列表仅能通过下标来获取目标位置的值,而哈希表可以根据给定的key计算得到目标位置的值。

    在列表查找中,使用最广泛的二分查找算法,复杂度为O(log2n),但其始终只能用于有序列表。普通无序列表只能采用遍历查找,复杂度为O(n)。

    而拥有较为理想的哈希函数实现的哈希表,对其任意元素的查找速度始终为常数级,即O(1)。


    图解:

    4365e45586eccf5a42d0e1a222ac2500.png

    在一个典型的哈希表实现中,我们将数组总长度设为模数,将key值直接对其取模,所得的值为数组下标。

    如图所示的三组数据,分别被映射到下标为0和7的位置中,显而易见的,第1组数据和第3组数据发生了哈希碰撞。


    如何解决哈希碰撞?

    常用的解决方案有散列法和拉链法。散列法又分为开放寻址法和再散列法等,此处不做展开。java中使用的实现为拉链法,即:在每个冲突处构建链表,将所有冲突值链入链表,如同拉链一般一个元素扣一个元素,故名拉链法。

    需要注意的是,如果遭到恶意哈希碰撞攻击,拉链法会导致哈希表退化为链表,即所有元素都被存储在同一个节点的链表中,此时哈希表的查找速度=链表遍历查找速度=O(n)。

    哈希表有什么优势?

    通过前面的概念了解,哈希表的优点呼之欲出:通过关键值计算直接获取目标位置,对于海量数据中的精确查找有非常惊人的速度提升,理论上即使有无限的数据量,一个实现良好的哈希表依旧可以保持O(1)的查找速度,而O(n)的普通列表此时已经无法正常执行查找操作(实际上不可能,受到JVM可用内存限制,机器内存限制等)。

    哈希表的主要应用场景

    在工程上,经常用于通过名称指定配置信息、通过关键字传递参数、建立对象与对象的映射关系等。目前最流行的NoSql数据库之一Redis,整体的使用了哈希表思想。

    一言以蔽之,所有使用了键值对的地方,都运用到了哈希表思想。

    Java中的哈希表实现-HashMap

    在正式开始对HashMap的介绍和实现之前,你应当知道以下这些知识:

    任意数对2的N次方取模时,等同于其和2的N次方-1作位于运算。

    公式表述为:

    k % 2^n = k & (2^n - 1)

    而位于运算相比于取模运算速度大幅度提升(按照Bruce Eckel给出的数据,大约可以提升5~8倍)。

    负载因子

    负载因子是哈希表的重要参数,其定义为:哈希表中已存有的元素与哈希表长度的比值。

    它是一个浮点数,表示哈希表目前的装满程度。由于表长是定值,而表中元素的个数越大,表中空余位置就会更少,发生碰撞的可能性也会进一步增大。

    哈希表的扩容策略依赖于负载因子阈值。基于性能与空间的选择,JDK标准库将HashMap的负载因子阈值定为0.75


    HashMap继承体系

    首先来看HashMap的继承体系:

    public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>
    
    public abstract class AbstractMap<K,V> implements Map<K,V>
    
    public interface Map<K, V>

    可以看到,抽象类AbstractMap就是对Map接口的抽象实现,HashMap通过继承AbstractMap间接实现了Map接口,同时自身直接声明了对Map接口的实现,即HashMap就是Map接口的直接实现。

    Map接口中定义了一个Map实现类必须要实现的方法。所有Map实现类都应当实现这些方法。

    Map接口定义的需要实现的方法:

    a38ca385f7565a1e41fe9706b41ab753.png

    在本篇文章剩余的篇幅中,将会基于Map接口实现一个我们自己的HashMap。

    MyHashMap实现:

    在动手之前,先分析清楚Map接口提供的方法,实现了哪些功能。其中关键的方法提取出来,结果为:

    //实现查找功能。
    //containsKey基于此方法实现。
    V get(Object key);
    //实现新增功能。
    //由于哈希表同key覆盖特性,此方法同时实现了更新操作。
    V put(K key, V value);
    //实现删除功能。
    V remove(Object key);
    //实现对Map的遍历功能。
    Set<Map.Entry<K, V>> entrySet();
    Collection<V> values();
    Set<K> keySet();

    我们的HashMap采用泛型数组作为存储数据的结构。此时应用到两个类Node和Entry。Node类用作拉链法链表节点,其中每个Node存储了一个Entry类,Entry中包含了Key和Value,是真正存储数据的类型。

    前文所述的与模运算等价的位与运算,当且仅当模数为2的N次幂时才会生效。所以我们的HashMap初始的数组长度将会定为16,扩容策略为每次扩容为上一次长度的2倍,负载因子0.75(这也是JDK标准库所采用的配置)。

    public class MyHashMap<K, V> implements Map<K, V> {
        private class Node {
            private MyEntry<K, V> entry = null;
            public Node next = null;
        }
    
        class MyEntry<K, V> implements Entry<K, V> {
            private int hash;
            private K key;
            private V value;
        }
    
        //常量区
        private static final double LOAD_FACTOR = 0.75;       //负载因子阈值
        private static final int INITIAL_SIZE = 16;           //数组初始大小
    
        //成员变量区
        private int element_count = 0;        //当前元素计数
        private Node[] node_list = (Node[]) Array.newInstance(Node.class, INITIAL_SIZE);       //存储数组。
    
        //略去Map列表的实现方法
    }

    值得注意的是

    private Node[] node_list = (Node[]) Array.newInstance(Node.class, INITIAL_SIZE)

    Java中并不支持直接申请泛型类的数组。只能通过Array.newInstance静态方法构造数组并强制转换为泛型类的数组。

    resize操作时同样需要用到此方法。

    Hash表的核心操作就是通过对key值的计算直接查找目标元素下标,因此我们首先参考标准库编写(fuzhi)出getIndex方法:

    private int getIndex( int hash, int mod ){
        return (hash & 0x7fffffff) & (mod - 1);
    }

    (hash & 0x7fffffff)是为了确保结果为正数。

    为什么要对0x7fffffff做位于操作?

    0x7fffffff是int可以表达的最大正整数,除了首位为0其他31位都为1。正数& 0x7fffffff结果为其本身,负数& 0x7fffffff结果为正数。

    为什么不用Math.abs?

    前面说过,位运算很快。而且由于Math.abs只是简单的return -a,因此Math.abs(Integer.MIN_VALUE)时结果仍然为负数,如下图所示:

    71733bc0ae6a12b3a78c1c7a12cb0ac7.png

    hash & 0x7fffffff保证结果为正数。

    (结果是不是负数的绝对值不重要,只要参数同样时每次计算都可以得出同样的结果,就可以作为哈希函数)

    基于getIndex方法,我们可以写出put和remove方法。

    @Override
    public V put( K key, V value ){
        put(new MyEntry<>(key, value), node_list, true);
        return value;
    }
    
    private void put( MyEntry<K, V> entry, Node[] target, boolean check ){
        put(new Node(entry), target, check);
    }
    
    /**
     * 如果目标位置为空,则创建节点并保存目标位置
     * 否则在列表中查找并替换重复项。
     * 如果没有重复项,则插入链表尾部。
     *
     * @param node   : 被加入数组的节点。
     * @param target : 目标数组。
     * @param check : 指示方法是否检查数组的当前元素数量。
     */
    private void put( Node node, Node[] target, boolean check ){
        int index = getIndex(node.getEntry().getHash(), node_list.length);
        if (target[index] == null) {
            target[index] = new Node(null);
        }
        if (target[index].next == null) {
            target[index].next = node;
            if (check) {
                //检查哈希表大小
                ++element_count;
                checkLoadFactor();
            }
            return;
        }
    
        Node temp = target[index].next;
        while (temp != null) {
            if (temp.getEntry().getHash() == node.getEntry().getHash()) {
                temp.setEntry(node.getEntry());
                return;
            }
            if (temp.next == null) {
                temp.next = node;
                temp.next.next = null;        //截断节点,防止出现循环引用
                if (check) {
                    //检查哈希表大小
                    ++element_count;
                    checkLoadFactor();
                }
            }
            temp = temp.next;
        }
    }

    其中几个值得注意的点:

    check参数:指示方法是否检查数组的当前元素数量。由于扩容时同样会使用这个方法作数组元素的迁移行为,一个检查的开关是必须的,否则会出现死循环。

    temp.next.next = null :同样,在数据迁移操作时,如果未截断链表的每个节点,会导致新老数组中对应列表发生串联,最终产生死循环。

    最终MyHashMap中将集成经典的链表操作。

    接着实现remove方法:

    @Override
    public V remove( Object key ){
        if (key == null) {
            return null;
        }
    
        int index = getIndex(key.hashCode(), node_list.length);
        if (node_list[index] == null || node_list[index].next == null) {
            return null;
        }
    
        //在目标位置的链表中查找目标键值。
        Node last = node_list[index];
        Node current = node_list[index].next;
        while (current != null) {
            if (current.getEntry().getHash() == key.hashCode()) {
                last.next = current.next;
                --element_count;                            //减少数组元素计数
                return current.getEntry().getValue();
            }
            last = last.next;
            current = current.next;
        }
    
        return null;
    }

    在remove方法中,将会计算得到目标节点下标,遍历目标链表节点,当查找到目标元素时,断开并重连链表将目标元素从链表中移除。

    非常典型的链表操作。

    接下来实现最重要的get操作。然而在HashMap的CRUD三个操作中,get操作最为简单,因为其不需要移动链表节点或改变链表结构,仅需要遍历链表即可。

    /**
     * 从Map中查找目标Key。
     * @param key
     * @return
     */
    @Override
    public V get( Object key ){
        int index = getIndex(key.hashCode(), node_list.length);
        //目标位置为空则直接返回null
        if (node_list[index] == null || node_list[index].next == null) {
            return null;
        }
    
        //目标位置不为空则遍历链表,查找相同的key
        Node temp = node_list[index].next;
        while (temp != null) {
            if (temp.getEntry().getHash() == key.hashCode()) {
                return temp.getEntry().getValue();
            }
            temp = temp.next;
        }
        return null;
    }

    接下来是resize方法,它实现了数组元素的迁移操作。

    但在resize方法之前,我们先来看一个有趣的方法,也是我的实现中不同于JDK标准库的方法,它提供了对元素数组的遍历操作,采用双指针法实现。它接受一个Consumer接口作为参数,它会对当前数组中的所有Node调用Consumer.accept方法。

    values方法,containsValue方法,keySet方法,entrySet方法都基于它来实现:

    //遍历list,并对其中的每一个元素执行指定的操作
    private void traversing( Node[] nl, Consumer<Node> con ){
        int head = 0, foot = nl.length - 1;
        Node node;
        while (head <= foot) {
            if (nl[head] != null && nl[head].next != null) {
                node = nl[head];
                while ((node = node.next) != null) {
                    con.accept(node);
                }
            }
            if (nl[foot] != null && nl[foot].next != null) {
                node = nl[foot];
                while ((node = node.next) != null) {
                    con.accept(node);
                }
            }
            ++head;
            --foot;
        }
    }

    有了traversing方法,可以用轻松(甚至是偷懒)的方式写出values,keySet,entrySet,containsValue:

    @Override
    public Collection<V> values(){
        Collection<V> collection = new ArrayList<>();
        traversing(node_list, (node -> {
            collection.add(node.getEntry().getValue());
        }));
        return collection;
    }
    
    @Override
    public Set<K> keySet(){
        Set<K> set = new HashSet<>();
        traversing(node_list, (node -> {
            set.add(node.entry.getKey());
        }));
        return set;
    }
    
    @Override
    public Set<Entry<K, V>> entrySet(){
        Set<Entry<K, V>> set = new HashSet<>();
        traversing(node_list, ( node ) -> {
            set.add(node.getEntry());
        });
    
        return set;
    }
    
    //在最坏情况下,这种实现会将HashMap遍历两次。
    //这样写仅仅是为了偷懒。
    //如果你要写一个用于生产环境的containsValue,不要这样做。
    @Override
    public boolean containsValue( Object value ){
        //遍历哈希表查找值
        for (Entry<K, V> entry : entrySet()) {
            V temp_value = entry.getValue();
            if (temp_value != null && temp_value.equals(value)) {
                return true;
            }
        }
        return false;
    }

    用于对HashMap进行扩容的resize方法如下,它的实现原理非常简单易懂:创建一个新数组,随后调用traversing和本类的put方法将原始数组中的所有元素插入到新数组中,最终使用新数组替换原始数组。

    随便一提,(hash & 0x7fffffff) & (mod - 1)可以保证将每个链表中的元素平均的放入新数组中的两个对应位置。

    /**
     * 列表扩容。
     */
    private void resize(){
        //创建新列表
        Node[] new_list = (Node[]) Array.newInstance(Node.class, node_list.length << 1);
        traversing(node_list, (node -> {
            put(node, new_list, false);
        }));
        //移动完成后替换当前列表。
        node_list = new_list;
    }

    大功告成!Map接口中的所有核心方法都被实现了。


    在OrsPced的Github可以找到本文中的完整实现。

    如果有更好的想法,评论或建议,欢迎在评论区提出。

    对阅读至此的您表示诚挚的感谢。

    展开全文
  • 哈希表查找失败的平均查找长度

    千次阅读 2019-10-09 18:02:18
    已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。 2. 这个位置是散列函数函数可以散列到的位置,不一定是的总长。 如:散列函数为H(key) = (keyx3) MOD 10,而长为15,此时...
  • 散列表的动态扩容解答+面试题一、散列表(哈希表、Hash 表)不同与之前我们介绍的线性表,所有的数据都是顺序存储,当我们需要在线性表中查找某一数据时,当线性表过长,需要查找的数据排序比较靠后的话,就需要花费...
  • 本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/5vxYoeARG1nC7Z0xTYXELA作者:Xuegui Chen哈希是一种通过对数据进行压缩, 从而提高效率的一种解决方法,但由于...一、哈希表概述哈希表的...
  • 也就是说,它通过把关键码值映射到中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,记为 Hash(key) = Addr 这里的地址是数组下标、索引或内存地址等)。存放记录的数组叫做散列表。②什么是...
  • 但是在翻阅了大部分HashMap相关的文章之后,发现大多数文章都是对HashMap源码的分析,丝毫没有提到哈希表的概念。这就导致了很多人只记住了HashMap的原理,却不知哈希表为何物的奇特现象。很多情况下,面试官可能并...
  • Hash表也称散列表,也有直接译作哈希表,Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。...
  • 一、哈希表概述哈希表的哈希函数输入一个键,并向返回一个哈希表的索引。可能的键的集合很大,但是哈希函数值的集合只是表的大小。哈希函数的其他用途包括密码系统、消息摘要系统、数字签名系统,为了使这些应用程.....
  • 哈希算法 查找失败

    2019-10-08 16:08:07
    step1:先将所有的数据装入哈希表汇总 1%11 = 1,没有冲突 13%11 = 2,没有冲突 12%11 = 1,下标1的位置上放置了数据1,此时冲突了,使用 线性探测法处理冲突,下标1上已经有数据了,所以往后查,此时下标2上也有...
  • ![图片说明](https://img-ask.csdn.net/upload/201602/09/1455031746_265651.png) 这个失败的长度是怎么计算出来的? 分子是怎么来的? 请大家具体讲讲~
  • 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的...
  • 哈希表查找不成功的平均查找长度

    千次阅读 2017-05-27 10:40:52
    1.查找失败的情况:哈希表中不存在这个元素才会查找失败 2.查找失败的判定;见书 3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认...
  • 散列技术时记录的存储位置和它的关键字之间建立的一个确定对应的关系f,使得每个关键字key对应一个存储位置f(key),查找时根据这个对应的关系找到给定值key的映射f(key),若查找集合中存储这个记录,则必定在f(key)...
  • 等概率情况下,查找06位置查找失败的查找次数为: 看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3. 地址1, 到第一个关键为空的地址2的距离为2,因此查找不成功的次数为...
  • 查找可以分为静态查找和动态查找。 静态查找 定义: ...将给定值与静态查找中数据元素的关键字逐个比较,若中某个元素的关键字与给定值相等,则查找成功,否则查找失败。 class StaticT...
  • 散列表 散列表(Hash table,也叫哈希表)【也被称:散列映射、映射、字典和关联数组】,是根据键(key)而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来...
  • 一,散列表的基本概念直接将元素的储存位置和其关键字之间建立某种直接关系,那么在进行查找时,就无需做比较或做很少次的比较,按照这种关系直接由关键字找到相应的记录,这就是散列表查找法的思想。它通过对元素...
  • 创建与输入数组相等长度的新数组,作为直接寻址。两数之和的期望是Target,将Target依次减输入数组的元素,得到的值和直接寻址比较,如果寻址存在这个值则返回;如果不存在这个值则将输入数组中的元素插入寻址...
  • 方法一:闭散列(即开放地址法):当发生哈希冲突时,如果该哈希表还没有被填满,那么就把该元素放到哈希表的下一个空闲的位置。 优缺点下面介绍; 开散列法(哈希桶):又名链地址法,先用哈希函数计算每个数据的...
  • 最近学了数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 Question1: 将关键字序列...
  • 哈希 哈希集(hash_set) 哈希集是与普通集合不同的是,他能完成时间复杂度为O(1)的查找和插入。 它通过哈希函数建立键值(key)与桶号的一一对应关系,当你插入数据时,通过哈希函数计算出桶号并...哈希表(hash_map...
  • 一、顺序查找 ...若扫描结束仍没有找到关键字等于k的结点,表示查找失败。 二、折半查找 元素必须是有序的,如果是无序的则要先进行排序操作。 基本思想:也称为是折半查找,属于有序查找算法。用给定值...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 158
精华内容 63
关键字:

哈希表查找失败