python hash

在 python3 中hash

help(hash) Help on built-in function hash in module builtins: hash(obj, /)     Return the hash value for the given object.#返回给定对象的哈希值     Two objects that compare equal must also have the same hash value, but the     reverse is not necessarily true.     #两个比较相等的对象也必须有相同的散列值,但是逆转不一定是正确的。

    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-p_w_picpath),通过散列算法,变换成固定长度的输出,该输出就是散列值。

    一个典型的空间换时间的算法,根据哈希出来的关键字进行快速的查询

构造方法:

    ① 直接寻址法

取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,

        其中a和b为常数(这种散列函数叫做自身函数)

    ② 数字分析法

        分析一组数据的某些特征,比如,比如在学校里用学生的年龄来作为标识的话,会有很大

        的冲突率,如果利用学生的学号作为标识的话,冲突率就会大大下降,因此数字分析就是

        找出这些特征的规律,尽可能利用这些数据来构成冲突几率较低的散列地址

    ③ 平方取中法

        先平方 后取中 生成散列地址

    ④ 折叠法

        均匀分割 分别取和 生成散列地址

    ⑤ 随机数法

选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。

    ⑥ 除留余数法

        取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = 

        key MOD p, p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。

        对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。

处理冲突的方法

   ① 开放寻址法:Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长,

    di为增量序列,可有下列三种取法:

    1).di=1,2,3,…,m-1,称线性探测再散列;

    2). di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…,±(k)^2,(k<=m/2)称二次探测再散列;

    3). di=伪随机数序列,称伪随机探测再散列。

    ② 再散列法:Hi=RHi(key),i=1,2,…,k RHi均是不同的散列函数,即在同义词产生地址冲突

      时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计

      算时间。

    ③ 链地址法(拉链法)

    ④ 建立一个公共溢出区

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python之linux下pdb试调

    break : 添加断点,比如在第5行添加断点break 5,在getlist函数添加断点break

    py3study
  • 安装s3cmd

    一、测试S3访问     root@node4:~# apt-get install python-boto     root@node4:~# vim s2t...

    py3study
  • 19:python中的判断语句

    Python条件语句是通过一条或多条语句的执行结果(True或者False)来决定执行的代码块。

    py3study
  • JVM中类加载的过程

      前面看了类加载的时机,本文来记录下类加载的过程,也就是加载的每个阶段都做了哪些事情

    用户4919348
  • 散列表的相关概念

    HashMap是Java源码中非常优秀的源码,涉及到很多的概念,算法、红黑树、数组、链表... 之前也尝试过硬着头皮去学习,但是由于基础本身就不是很牢固,所以后...

    飞翔的竹蜻蜓
  • 分离链接的散列散列代码实现

    散列 散列为一种用于以常数平均时间执行插入,删除和查找的技术。一般的实现方法是使通过数据的关键字可以计算出该数据所在散列中的位置,类似于Python中的字典。关...

    月见樽
  • linux网络编程之posix 线程(一):线程模型、pthread 系列函数 和 简单多线程服务器端程序

    一、线程有3种模型,分别是N:1用户线程模型,1:1核心线程模型和N:M混合线程模型,posix thread属于1:1模型。 (一)、N:1用户线程模型 “线...

    s1mba
  • airtest操作夜神模拟器adb冲突解决办法

    去aritestIde所在目录\AirtestIDE\airtest\core\android\static\adb\windows

    小小咸鱼YwY
  • 【原创】Java并发编程系列2:线程概念与基础操作

    本篇为【Dali王的技术博客】Java并发编程系列第二篇,讲讲有关线程的那些事儿。主要内容是如下这些:

    王金龙
  • 长文慎入-探索Java并发编程与高并发解决方案(更新中)1 基本概念2 CPU3 项目准备4线程安全性5发布对象7 AQS9 线程池10 死锁

    JavaEdge

扫码关注云+社区

领取腾讯云代金券