python之hash散列,常见的散列hash算法有哪些

发布时间：2022-11-18

本文目录一览：

  1. 流畅的Python
  2. Python字典的底层实现
  3. [Python数据结构-哈希表（Hash Table）](#Python数据结构-哈希表（Hash Table）)
  4. Python哈希函数什么情况下抛出异常

流畅的Python

第一章 Python数据模型 魔术方法(magic method)或者说双下方法(dunder method)表示特殊方法。以双下划线开始和结束，比如 __getitem__ len()需要实现 __len__() []和切片需要实现 __getitem__() 可迭代或者反向迭代，至少需要实现 __getitem__() in需要实现 __contains__(), 如果没有实现，则至少需要实现 __getitem__(), 因为它可以自己做迭代搜索 __repr__, 它能把一个对象用字符串的形式表达出来，repr()就是通过 __repr__ 这个特殊方法来得到一个字符串的表达形式的。如果没有实现 __repr__，输出实例时，得到的字符串就是 Vector object at 0x10e100070 之类的 注意 __repr__ 和 __str__ 的区别，后者是在 str() 函数中使用，或者是在用 print 函数打印的时候才被调用。 如果一个对象没有 __str__ 函数，而 Python 又需要调用它的时候，解释器会用 __repr__ 作为替代。 在 if、while 或者 and、or、not 运算符中，为了判定一个值 x 是真还是假，Python 会调用 bool(x)，这个函数只能返回 True 或者 False。 bool(x)，其实调用的是 x.__bool__() 的结果，如果不存在 __bool__, bool(x) 会尝试调用 x.__len__()。若返回 0，则 bool 会返回 False，否则 True。 第二章 序列构成的数组 序列类型概览

  1. 容器序列 list、tuple、collections.deque 这些序列都能存放不同类型的数据
  2. 扁平序列 str、bytes、bytearray、memoryview 和 array.array，这些序列只能容纳一种类型。 注意：容器序列存放的是它们所包含任意类型的对象的引用，而扁平序列里存放的是值而不是引用。换句话说，扁平序列其实是一系列连续的内存空间，但是扁平序列只能存放字符、字节和数值这种基础类型。 可变序列 list、bytearray、array.array、collections.deque 和 memoryview 不可变序列 tuple、str 和 bytes 列表推导
symbols = 'abc'
codes = []
for symbol in symbols:
    codes.append(symbol)

或者

codes = [symbol for symbol in symbols]

第一种就是正常的 for 循环，第二种就是列表推导 生成器表达式 虽然可以用列表推导来初始化元组、数组或者其他序列类型，但是生成器表达式更好。因为生成器表达式背后遵循了迭代器协议，可以逐个产出元素，而不是先建立一个完整的列表，然后再把这个列表传递到某个构造函数里面。 和列表推导差不多，就是方括号改成圆括号

symbols = 'abc'
array.array('i', (symbol for symbol in symbols))

元组的应用：

  1. 当作记录，因为它是不可更改的
  2. 元组拆包，可以得到里面的数据，类似于 a, b = (first, second)
  3. 具名元组，从 collections.namedtuple 生成具名元组，除了继承普通元组的属性，具名元组还有一些自己专有的属性。_fields 类属性，类方法 _make(iterable) 和实例方法 _asdict()。
  • _fields 类属性：包含具名元组的各个字段名称
  • _make(iterable)：通过 _make() 接受一个可迭代对象来生成这个类的一个实例
  • _asdict()：把具名元组以 collections.OrderedDict 的形式返回。 切片： s[a:b:c]：s 在 a 到 b 之间以 c 为间隔取值，c 还可以是负数，负值意味着取反。如 s[::-1] 意味着，将这个 list 倒置 给切片赋值：
l = list(range(5))
print(l)  # [0, 1, 2, 3, 4]
l[1:3] = [20, 30]
print(l)  # [0, 20, 30, 4]
l[1:3] = 100  # 报错，需要写成 [100]

对序列使用 + 和 * + 是把两个序列合并，在拼接过程中，两个被操作的序列都不会被修改，Python 会新建一个包含同类型数据的序列作为拼接结果。 * 是把序列复制几份然后拼接起来。例如 l = [1, 2]，l * 3 = [1, 2, 1, 2, 1, 2]，* 也会构建新的序列而不修改原有的对象。 序列的增量赋值 += 背后的特殊方法是 __iadd__，但是如果一个类没有实现这个方法，Python 会退一步调用 __add__ 第三章 字典和集合 字典推导

country_code = {country: code for code, country in dial_codes}  # dial_codes 是一个元组的 list

{code: country.upper() for country, code in country_code.items() if code < 66}

第一个是把国家作为键，第二个把 code 作为键

if key not in my_dict:
    my_dict[key] = []
my_dict[key].append(new_value)

可以直接写成：

my_dict.setdefault(key, []).append(new_value)

所有映射类型在处理找不到的键的时候，都会牵扯到 __missing__ 方法。 集合 {1, 2} 这是集合 集合推导

from unicodedata import name
{chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i), '')}

a.union(b, c, d) 这里 a 必须是 set，b、c 和 d 则可以是任何类型的可迭代对象 为了获取 dict[key] 背后的值，Python 会调用 hash(key) 来计算 key 的散列值，然后去散列表里面查找表元，若找到的表元是空的，则抛 KeyError，若不是空的，则表元里会有一对 found_key: found_value，这个时候 Python 会检验 key == found_key 是否为真，如果为真的话，会返回 found_value。如果不等，说明出现了散列冲突。发生这种情况的原因是，散列表所做的只是把随机的元素映射到只有几位的数字上，而散列表本身的索引又只依赖于这个数字的一部分。为了解决散列冲突，算法会在散列值中另外取几位，然后用特殊方法处理一下，把新得到的数字再当作索引来寻找表元。

dict 的实现

  1. 支持 hash() 函数，并且通过 __hash__() 方法所得到的的散列值是不变的。
  2. 通过 __eq__() 来检测相等性。
  3. 若 a == b，则 hash(a) == hash(b)。 往字典添加新键可能会改变已有键的顺序 无论何时往字典里添加新键，Python 解释器都可能作出字典扩容的决定。扩容导致的结果就是需要新建一个更大的散列表，并把字典里已有的元素添加到新表。这个过程可能会发生散列冲突，导致新散列表次序发生变化。 由此可知，不要对字典同时进行迭代和修改。如果你想扫描并修改一个字典，最好分成两步来解决，首先对字典迭代，以得出需要添加的内容，把这些内容放到一个新字典里，迭代结束之后再对原字典进行更新。 字符问题 字节序列 - 解码 - Unicode 字符串 - 解码 - Unicode
b = str.encode('utf8')  # 字符串转化成字节码，是编码
b.decode('utf8')  # 把字节码还原成字符串，是解码

一等函数 一等函数满足以下条件：

  1. 在运行时创建
  2. 能赋值给变量或数据结构中的元素
  3. 能作为参数传给函数
  4. 能作为函数的返回结果 高阶函数 接受函数为参数，或者把函数作为结果返回的函数是高阶函数。 匿名函数 通过对比可以看出，匿名函数 lambda x: x * x 实际上就是：
def f(x):
    return x * x

关键字 lambda 表示匿名函数，冒号前面的 x 表示函数参数。 可调用类型 任何 Python 对象都可以表现得像函数。只需要实现实例方法 __call__ 实现 __call__ 方法的类是创建函数类对象的简便方式。 函数内省 可以用 dir(len) 查看所有的函数属性

sorted(set(dir(func)) - set(dir(obj)))  # 计算差集，然后排序，得到类的实例没有而函数有的属性列表

== 运算符比较两个对象的值（对象中保存的数据），而 is 是比较对象的标识。 通常，我们关注的是值，而不是标识，因此 Python 中 == 出现的频率比 is 高。 a == b 是语法糖，等同于 a.__eq__(b)，装饰器也是语法糖。

Python字典的底层实现

字典是一种可变、无序容器数据结构。元素以键值对存在，键值唯一。它的特点搜索速度很快：数据量增加 10000 倍，搜索时间增加不到 2 倍；当数据量很大的时候，字典的搜索速度要比列表快成百上千倍。 在 Python 中，字典是通过散列表（哈希表）实现的。字典也叫哈希数组或关联数组，所以其本质是数组（如下图），每个 bucket 有两部分：一个是键对象的引用，一个是值对象的引用。所有 bucket 结构和大小一致，我们可以通过偏移量来读取指定 bucket。 定义一个字典 dic = {}，假设其哈希数组长度为 8。 Python 会根据哈希数组的拥挤程度对其扩容。“扩容”指的是创造更大的数组，这时候会对已经存在的键值对重新进行哈希取余运算保存到其它位置；一般接近 2/3 时，数组就会扩容。扩容后，偏移量的数字个数增加，如数组长度扩容到 16 时，可以用最右边 4 位数字作为偏移量。 计算键对象 name 的哈希值，然后比较哈希数组对应索引内的 bucket 是否为空，为空返回 None，否则计算这个 bucket 的键对象的哈希值，然后与 name 哈希值比较，相等则返回值对象，否则继续左移计算哈希值。 注意：

  1. 键必须为可哈希的，如数字、元组、字符串；自定义对象需要满足支持 hash、支持通过 __eq__() 方法检测相等性、若 a == b 为真，则 hash(a) == hash(b) 也为真。
  2. 字典的内存开销很大，以空间换时间。
  3. 键查询速度很快，列表查询是按顺序一个个遍历，字典则是一步到位。
  4. 往字典里面添加新键可能导致扩容，导致哈希数组中键的次序变化。因此，不要在遍历字典的同时进行字典的修改。

Python数据结构-哈希表（Hash Table）

哈希表（Hash Table）：通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 哈希函数（Hash Function）：将哈希表中元素的关键键值映射为元素存储位置的函数。 哈希冲突（Hash Collision）：不同的关键字通过同一个哈希函数可能得到同一哈希地址。 哈希表的两个核心问题是：哈希函数的构建 和 哈希冲突的解决方法。 常用的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。 常用的哈希冲突的解决方法有两种：开放地址法和链地址法。 给你一个整数数组 nums 和两个整数 k 和 t。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) == t，同时又满足 abs(i - j) == k。 如果存在则返回 True，不存在返回 False。 给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。 给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。 请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 力扣 217
    力扣 389
    力扣 496
    内容参考：

Python哈希函数什么情况下抛出异常

抛出异常是停止运行这个函数中的代码。 哈希算法将一个不定长的输入，通过散列函数变换成一个定长的输出，即散列值。是一种信息摘要算法。对象的 hash 值比原对象拥有更低的内存复杂度。 它不同于加密。哈希是将目标文本转换成具有相同长度的、不可逆的杂凑字符串，而加密则是将文本转换为具有相同长度的、可逆的密文。哈希算法是不可逆的，只能由输入产生输出，不能由输出产生输入。而加密则是可逆的。即可以从输入产生输出，也可以反过来从输出推出输入。

推荐文章