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

哈希表（Hash Table） ：通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

创新互联是一家专业的成都网站建设公司，我们专注成都做网站、网站设计、外贸营销网站建设、网络营销、企业网站建设，买友情链接，1元广告为企业客户提供一站式建站解决方案，能带给客户新的互联网理念。从网站结构的规划UI设计到用户体验提高，创新互联力求做到尽善尽美。

哈希函数（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中冷门但非常好用的内置函数

Python中有许多内置函数,不像print、len那么广为人知,但它们的功能却异常强大,用好了可以大大提高代码效率，同时提升代码的简洁度，增强可阅读性

Counter

collections在python官方文档中的解释是High-performance container datatypes，直接的中文翻译解释高性能容量数据类型。这个模块实现了特定目标的容器，以提供Python标准内建容器 dict , list , set , 和 tuple 的替代选择。在python3.10.1中它总共包含以下几种数据类型：

容器名简介

namedtuple() 创建命名元组子类的工厂函数

deque 类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)

ChainMap 类似字典(dict)的容器类，将多个映射集合到一个视图里面

Counter 字典的子类，提供了可哈希对象的计数功能

OrderedDict 字典的子类，保存了他们被添加的顺序

defaultdict 字典的子类，提供了一个工厂函数，为字典查询提供一个默认值

UserDict 封装了字典对象，简化了字典子类化

UserList 封装了列表对象，简化了列表子类化

UserString 封装了字符串对象，简化了字符串子类化

其中Counter中文意思是计数器，也就是我们常用于统计的一种数据类型，在使用Counter之后可以让我们的代码更加简单易读。Counter类继承dict类，所以它能使用dict类里面的方法

举例

#统计词频

fruits = ['apple', 'peach', 'apple', 'lemon', 'peach', 'peach']

result = {}

for fruit in fruits:

if not result.get(fruit):

result[fruit] = 1

else:

result[fruit] += 1

print(result)

#{'apple': 2, 'peach': 3, 'lemon': 1}下面我们看用Counter怎么实现：

from collections import Counter

fruits = ['apple', 'peach', 'apple', 'lemon', 'peach', 'peach']

c = Counter(fruits)

print(dict(c))

#{'apple': 2, 'peach': 3, 'lemon': 1}显然代码更加简单了，也更容易阅读和维护了。

elements()

返回一个迭代器，其中每个元素将重复出现计数值所指定次。元素会按首次出现的顺序返回。如果一个元素的计数值小于1，elements()将会忽略它。

c = Counter(a=4, b=2, c=0, d=-2)

sorted(c.elements())

['a', 'a', 'a', 'a', 'b', 'b']most_common([n])

返回一个列表，其中包含n个最常见的元素及出现次数，按常见程度由高到低排序。如果n被省略或为None，most_common()将返回计数器中的所有元素。计数值相等的元素按首次出现的顺序排序：

Counter('abracadabra').most_common(3)

[('a', 5), ('b', 2), ('r', 2)]这两个方法是Counter中最常用的方法，其他方法可以参考 python3.10.1官方文档

实战

Leetcode 1002.查找共用字符

给你一个字符串数组words，请你找出所有在words的每个字符串中都出现的共用字符（包括重复字符），并以数组形式返回。你可以按任意顺序返回答案。

输入：words = ["bella", "label", "roller"]

输出：["e", "l", "l"]

输入：words = ["cool", "lock", "cook"]

输出：["c", "o"]看到统计字符，典型的可以用Counter完美解决。这道题是找出字符串列表里面每个元素都包含的字符，首先可以用Counter计算出每个元素每个字符出现的次数，依次取交集最后得出所有元素共同存在的字符，然后利用elements输出共用字符出现的次数

class Solution:

def commonChars(self, words: List[str]) - List[str]:

from collections import Counter

ans = Counter(words[0])

for i in words[1:]:

ans = Counter(i)

return list(ans.elements())提交一下，发现83个测试用例耗时48ms，速度还是不错的

sorted

在处理数据过程中，我们经常会用到排序操作，比如将列表、字典、元组里面的元素正/倒排序。这时候就需要用到sorted()，它可以对任何可迭代对象进行排序，并返回列表

对列表升序操作：

a = sorted([2, 4, 3, 7, 1, 9])

print(a)

# 输出：[1, 2, 3, 4, 7, 9]对元组倒序操作：

sorted((4,1,9,6),reverse=True)

print(a)

# 输出：[9, 6, 4, 1]使用参数：key，根据自定义规则，按字符串长度来排序：

fruits = ['apple', 'watermelon', 'pear', 'banana']

a = sorted(fruits, key = lambda x : len(x))

print(a)

# 输出：['pear', 'apple', 'banana', 'watermelon']all

all() 函数用于判断给定的可迭代参数iterable中的所有元素是否都为 TRUE，如果是返回 True，否则返回 False。元素除了是 0、空、None、False外都算True。注意：空元组、空列表返回值为True。

all(['a', 'b', 'c', 'd']) # 列表list，元素都不为空或0

True

all(['a', 'b', '', 'd']) # 列表list，存在一个为空的元素

False

all([0, 1，2, 3]) # 列表list，存在一个为0的元素

False

all(('a', 'b', 'c', 'd')) # 元组tuple，元素都不为空或0

True

all(('a', 'b', '', 'd')) # 元组tuple，存在一个为空的元素

False

all((0, 1, 2, 3)) # 元组tuple，存在一个为0的元素

False

all([]) # 空列表

True

all(()) # 空元组

Trueany函数正好和all函数相反：判断一个tuple或者list是否全为空，0，False。如果全为空，0，False，则返回False；如果不全为空，则返回True。

F-strings

在python3.6.2版本中，PEP 498提出一种新型字符串格式化机制，被称为 “字符串插值” 或者更常见的一种称呼是F-strings，F-strings提供了一种明确且方便的方式将python表达式嵌入到字符串中来进行格式化：

s1='Hello'

s2='World'

print(f'{s1} {s2}!')

# Hello World!在F-strings中我们也可以执行函数：

def power(x):

return x*x

x=4

print(f'{x} * {x} = {power(x)}')

# 4 * 4 = 16而且F-strings的运行速度很快，比传统的%-string和str.format()这两种格式化方法都快得多，书写起来也更加简单。

本文主要讲解了python几种冷门但好用的函数，更多内容以后会陆陆续续更新~

Python如何哈希字符串

Python中字符串是可哈希的，即可以作为字典的键或者HashTable的键使用。

您可以这样子使用Python内置函数hash（散列函数）：

您也可以将字符串转为一个集合：

总之，Python里面有很多内置的hash功能性数据结构和函数。

python之哈希算法

哈希(Hash)算法：`hash（object）`

哈希算法将一个不定长的输入，通过散列函数变换成一个定长的输出，即散列值。是一种信息摘要算法。对象的hash值比原对象拥有更低的内存复杂度。

它不同于加密。哈希（hash）是将目标文本转换成具有相同长度的，不可逆的杂凑字符串，而加密则是将文本转换为具有相同长度的，可逆的密文。

哈希（hash）算法是不可逆的，只能由输入产生输出，不能由输出产生输入。而加密则是可逆的。即可以从输入产生输出，也可以反过来从输出推出输入。

对于hash算法，不同的数据应该生成不同的哈希值。如果两个不同的数据经过Hash函数计算得到的Hash值一样。就称为哈希碰撞（collision）。哈希碰撞无法被完全避免。只能降低发生概率。

好的hash函数会导致最少的hash碰撞。

*

可哈希性（hashable）：

可哈希的数据类型为不可变的数据结构（如字符串srt，元组tuple，对象集objects等）。这种数据被称为可哈希性。

不可哈希性：

不可哈希的数据类型，为可变的数据结构（如字典dict，列表list和集合set等）。

如果对可变的对象进行哈希处理，则每次对象更新时，都需要更新哈希表。这样我们则需要将对象移至不同的数据集，这种操作会使花费过大。

因此设定不能对可变的对象进行hash处理。

**

**

Python3.x添加了hash算法的随机性，以提高安全性，因此对于每个新的python调用，同样的数据源生成的结果都将不同。

哈希方法有（MD5, SHA1, SHA256与SHA512等）。常用的有SH256与SHA512。MD5与SHA1不再常用。

- MDH5 (不常用)

- SHA1 (不常用)

- SHA256 (常用)

- SHA512 (常用)

一种局部敏感的hash算法，它产生的签名在一定程度上可以表征原内容的相似度。

可以被用来比较文本的相似度。

安装simhash：

Pip3 install simhash

感知哈希算法（perceptual Hash Algorithm）。用于检测图像和视频的差异。

安装Imagehash:

pip3 install Imagehash

比较下面两张图片的Imagehash值

可以看到两张图片的hash值非常相似。相似的图片可以生成相似的哈希值是Imagehash的特点。

当前文章：Python完美散列函数 散列表散列函数
网页路径：http://pwwzsj.com/article/hhccho.html