哈希表 or 散列表(Hash Table)

直接寻址表 + hash = 哈希表
注：字典类型是Python中最常用的数据类型之一，它是一个键值对的集合，字典通过键来索引，关联到相对的值，理论上它的查询复杂度是 O(1)
哈希表一个通过哈希函数来计算数据存储位置的数据结构,通常支持如下操作:
- insert(key,value):插入键值对(key,value)
- get(key):如果存在键为key的键值对则返回其value,否则返回空值
- delete(key):删除键为key的键值对

1.数据添加：
- 把key通过哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余
- 取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
2.数据查询：再次使用哈希函数将key转换为对应的数组下标，并定位到数组的位置获取value。
除法哈希法: h(k) = k % m
乘法哈希法: h(k) = floor(m*(Akey%1))
_全域哈希法: ha,b(k) = ((a_key + b) mod p) mod m a,b=1,2,...p-1

1.比如字典{“name”:”zhangsan”,”age”:26}，那么他们的字典key为name、age，假如哈希函数h(“name”)=1、h(“age”)=3,
2.那么对应字典的key就会存储在列表对应下标的位置，[None,“zhangsan”,None,26]

字典与集合都是通过哈希表来实现的。
- a = {'name': 'Alex', 'age': 18, 'gender': 'Man'} 使用哈希表存储字典,通过哈希函数将字典的键映射为下标。
- 假设h('name')= 3,h('age') = 1, h(gender')=4,则哈希表存储为[None, 18, Norhe, 'Alex', 'Man'] 如果发生哈希冲突,则通过拉链法或开发寻址法解决
MD5(Message-Digest Algorithm5)曾经是密码学中常用的哈希函数,可以把任意长度的数据映射为 128位的哈希值,其曾经包含如下特征:
- 1. 同样的消息,其MD5值必定相同;
- 2. 可以快速计算出任意给定消息的MD5值;
- 3. 除非暴力的枚举所有可能的消息,否则不可能从哈希值反推出消息本身;
- 4. 两条消息之间即使只有微小的差别,其对应的MD5值也应该是完全不同、完全不相关的;
- 5. 不能在有意义的时间内人工的构造两个不同的消息使其具有相同的MD5值。
历史上MD5和SHA-1曾经是使用最为广泛的cryptographic hashfunction,但是随着密码学的发展,这两个哈希函数的安全性相继受到了各种挑战。（比特币）
- 因此现在安全性较重要的场合推荐使用SHA-2等新的更安全的哈希函数。
- SHA-2包含了一系列的哈希函数:SHA-224,SHA-256,SH/A-384, SHA-512, SHA-512/224,SHA-512/256,其对应的哈希值长度分别为224,256,384 or 512位。
- SHA-2具有和MD5类似的性质(参见MD5算法的特征)。

results matching ""