queue python一、什么是数据结构？二、数据结构的(2)

假设有一个长度为7的数组，哈希函数h(k)=k%7。元素集合{14,22,3,5}的存储方式如下图。

2、哈希冲突

由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况 ，

这种情况叫做哈希冲突。

比如h(k)=k%7, h(0)=h(7)=h(14)=...

3、解决哈希冲突的办法

a、开放寻址法

b、拉链发

开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。queue python

线性探查：如果位置i被占用，则探查i+1, i+2,……

二次探查：如果位置i被占用，则探查i+12,i-12,i+22,i-22,……

二度哈希：有n个哈希函数，当使用第1个哈希函数h1发生冲突时，则尝试使用h2,h3,……

拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。

4、哈希表在Python中的应用

a、字典与集合都是通过哈希表来实现的

b、 在Python中的字典：a = {'name': 'Alex', 'age': 18, 'gender': 'Man'}，使用哈希表存储字典，通过哈希函数将字典的键映射为下标。

假设h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4，则哈希表存储为[None, 18, None, ’Alex’, ‘Man’]

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-65114-2.html