聊聊哈希表的设计与具体实现cherbim3年前发布750散列表也叫哈希表（ Hash table ），是根据关键字（ key ）而直接访问在内存存储位置的数据结构。在很多高级语言中都有哈希表的身影，比如在 Python 中，有一种数据结构叫做，中文翻译是字典，应该是基于哈希表实现的。下面以生活中查电话号码作为一个通俗的例子，讲解什么是哈希表。 可以把哈希表想象成一本按照人名首字母顺序排列电话簿，当我们要查找张三的电话号码时，可以轻易得知的首字母是。理想情况下，张三可能在电话簿 Z 开头的第一个，不理想的情况下，可能要往后再找几个人。显然，根据姓名首字母查找电话，要比挨个查找快很多，这就是哈希表的特点，快。 与上面例子所对应的哈希表相关名词: 对于不同关键词，经过哈希函数的计算，可能得到同一哈希地址。比如，尽管奔波儿灞(key1)和灞波儿奔(key2)是不同的名字（）但经过计算得到的是同一结果()，他们名字的首字母都是。这种情况就叫做冲突。 解决冲突的方法有很多种，比如开放地址法和，可以根据具体使用场景来选择。一般来说，在实际项目和开发中采用链地址法比较多。链地址法的是，把相同哈希地址的关键字放在同一个链表中。采用链地址法解决冲突的哈希表，可以理解为数组和链表的组合。在上图中，存放首字母的是一个长度为 26 的数组，而数组的每一个元素可以看作是一个单链表，链表的数据域存放着姓名，指针域指向下一个存放相同首字母的姓名的节点。上面我们对哈希表有了一个大概的了解，接下来设计并实现一个字典()，在这个字典中，可以存放键值对，也可以根据键(key)获取对应的值(val)。首先看结构体，它有三个成员，分别用来表示后继节点指针和键与值，用以表示单链表的节点。接着是结构体，用来表示字典本身。下面是用于操作队列的函数名及其作用与复杂度 哈希函数是一种映射关系，构造哈希函数是一个数学问题，方法也很多，总的来说，要尽量减少冲突，地址尽量分布的均匀。这里我们选择一个简单的用于计算整数哈希值的函数，以及用于计算字符串哈希的 TIME33 算法。拓展，有一种叫的算法因为被 Redis 应用而广为人知, 由 Austin Appleby 在 2008 年发明, 发明者被邀到 google 工作。函数接受一个参数，用以下面判断字典的类型，从而确定对应的 hash 函数。然后是设置字典的大小，并为数组申请内存，然后 table 所有元素置 0 ，代表数组该位置为空。最后返回该新建的字典。创建一个,也即是单链表的节点。这里接受俩 void 类型指针为参数，使得字典可以保存各类数据。第一种方法：这种方法简单有效，无论是新增、冲突或者更新操作，都以要插入的键值对生成的新结点作为对应数组位置的第一个节点。新增和冲突，本质都是链表插入，使用此方法时，更新并非实质更新。由于新结点作为对应数组位置的第一个节点，这就导致旧数据（相同 key 的节点）排列在新结点之后，而查询时，是从数组对应位置链表的第一个节点开始查找，所以总是先查找到新的键值对。值得一提的是，的 dcit 在插入键值对时，就使用了该方法。第二种方法：这个方法可以参考上文提到的，优点是利用内存更加少一点，缺点就是不够优雅，增加了算法复杂度。在调试和测试时，可以将 dict->size 设置为 1 ，进而观察新增、更新、冲突等情况。查字典就是给定一个 key ，查对应的 val 。参考上文提到的。在清除 dict 所有 entry ，而不清除 dict 本身时，只需要遍历 table 数组，发现不为 0 的元素时再遍历清除对应的链表即可。释放 dict 的操作，只需要释放所有 entry 后，再释放 dict 本身即可。测试时，插入键值对我使用的是第二种方法，此外我还将 dict 中的 size 设置为 1 ，这样 table 中就一个位置，方便观察插入、更新、冲突时，链表的变化。编译输出本篇摘录于我的原创系列文章（学习笔记）本人才疏学浅，文章难免有纰漏之处，还望大佬们指点。
没有回复内容