python hash

发布时间：2019-08-28 09:07:53编辑：auto阅读（1590）



    在 python3 中hashj_0028.gif

    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），通过散列算法，变换成固定长度的输出，该输出就是散列值。

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

    构造方法：j_0023.gif

        ① 直接寻址法

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

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

        ② 数字分析法

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

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

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

        ③ 平方取中法

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

        ④ 折叠法

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

        ⑤ 随机数法

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

        ⑥ 除留余数法

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

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

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

    处理冲突的方法j_0022.gif

       ① 开放寻址法：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均是不同的散列函数，即在同义词产生地址冲突

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

          算时间。

        ③ 链地址法（拉链法）

        ④ 建立一个公共溢出区

关键字：

上一篇： python and   or

下一篇： python expect