Python中的id函数和hash函数——数据的“特征值”

简介

id()函数与 hash()函数是 Python 中的两个内置函数。它们的功能当然不同，但都可谓是返回数据 “特征值” 的函数，且在一些情况下有不错的作用。

id()?函数

id(x) 返回对象x独有的，或者说代表它 “identity” 的一个值，所有变量（对象）能使用该函数。同一时间程序中所有变量（对象）的 id 值互不相同。

print(id(321), id(231), id([31, 213]))

2824800761168 140707144970216 2824802116416

事实上，id(x) 返回的就是 x 在内存中地址！不信你看：

it = iter([2,3,1])
print(it)
print("{:X}".format(id(it))) # 用format方法输出id(it)的十六进制

????????发现结果就是它的地址！如下：?

<list_iterator object at 0x00000291B34FE3E0>
291B34FE3E0

小练习

????????Python中【列表、字典、集合等】变量赋值给变量相当于 “传递引用”，请运用函数id() 证明这一点。

def getList():
    ls = [1,2,3]
    print(id(ls))
    return ls

a = getList()
print(id(a))

2600945393664
2600945393664

hash() 函数

• Python中的哈希值：可哈希（hashable）对象到整数的映射。两个对象相同则哈希值相同，反之不同，特别地，数值对象仅比较其大小（如int(1)=float(1.0)，故两者哈希值相同）。

• 函数 hash() 只能作用于可哈希对象，hash(x) 返回 x 的哈希值

• 事实上，Python的字典就是以哈希值来比较键（key）的，因此你肯定没见过字典的key为一个列表（不可哈希）！

print(hash(231213), hash('r21fc'), hash(231213.0000001))
231213 313982128143448928 230586287917

print({2:-3, 2.0:-3})
{2: -3}

print(hash([3,-1]))
TypeError: unhashable type: 'list'

就刷题的应用而言，hash() 函数可能有一个妙用——快速获得字符串的哈希并用其优化字符串的比较！

字符串哈希（直接用hash()函数）例题

P2580 于是他错误的点名开始了 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P2580

这道题本身是考字典树（Trie）树的模板。可是这么 Python 的问题怎么能不用优美的 Python 卡一发呢！显然，对于此题我们可以运用 Python 中的集合（set）进行解决。

当然，字符串的比较必然慢于哈希值（一个整数）的比较。实践证明，直接将字符串丢入 set 与将其哈希值丢入 set 的用时在数据较大时有显著差异（也决定了是否能用 Python 卡过此题），见下：

注：选用语言 “PyPy 3”

不用哈希——90分

n=int(input())
names = []
for i in range(n):
    names.append(input())
m=int(input())
s = set()
for i in range(m):
    name = input()
    if name in names:
        if name not in s:
            print('OK')
            s.add(name)
        else:
            print('REPEAT')
    else:
        print('WRONG')

用哈希——100分且整体明显提速

n=int(input())
names = []
for i in range(n):
    names.append(hash(input()))
m=int(input())
s = set()
for i in range(m):
    h = hash(input())
    if h in names:
        if h not in s:
            print('OK')
            s.add(h)
        else:
            print('REPEAT')
    else:
        print('WRONG')

小练习

????????用 hash()函数去以小常数干爆 LeetCode 的 Hard 字符串题吧~

Substring with Concatenation of All Words - LeetCodehttps://leetcode.com/problems/substring-with-concatenation-of-all-words/

?