【数据结构入门精讲 | 第十四篇】散列表知识点及考研408、企业面试练习(1)

简介: 【数据结构入门精讲 | 第十四篇】散列表知识点及考研408、企业面试练习(1)


概念

散列表(Hash Table),也被称为哈希表或散列映射,是一种常用的数据结构之一。它通过将键(key)映射到值(value)来实现高效的数据存储和检索。

散列表的主要思想是利用哈希函数将键转换成对应的索引,然后将值存储在该索引位置上。当需要查找或插入元素时,再次使用哈希函数计算出对应的索引,从而快速定位到目标位置。

散列表的优势在于具有高效的查找和插入操作。由于直接通过索引进行访问,时间复杂度通常为O(1),即常数时间。

装填因子: 设m和n分别表示表长和表中填入的结点数,则将α=n/m定义为散列表的装填因子(Load Factor)。α越大,表越满,冲突的机会也越大。通常取α≤1。

然而,在极端情况下,散列表的性能可能会下降,例如哈希冲突(多个键映射到同一个索引位置)的发生,这会导致链表的长度增加,进而影响到操作的效率。为了解决这个问题,可以采用一些方法,本文介绍两种方法。

伪代码

// 定义散列表的数据结构
struct HashTable {
    int size; // 散列表的大小
    vector<vector<pair<Key, Value>>> table; // 存储键值对的二维向量数组
};
// 初始化散列表
HashTable Initialize(int size) {
    HashTable hashTable;
    hashTable.size = size;
    hashTable.table.resize(size); // 根据指定的大小调整table的大小
    return hashTable;
}
// 哈希函数,将键映射到散列表的索引位置
int HashFunction(Key key, int size) {
    // 根据键的特性,选择适当的哈希函数来计算散列值
    // 返回散列值对散列表大小取模,得到索引位置
    return hashValue % size;
}
// 向散列表中插入键值对
void Insert(HashTable& hashTable, Key key, Value value) {
    int index = HashFunction(key, hashTable.size); // 计算键的散列值并得到索引位置
    hashTable.table[index].push_back(make_pair(key, value)); // 在索引位置插入键值对
}
// 从散列表中删除指定键的键值对
void Delete(HashTable& hashTable, Key key) {
    int index = HashFunction(key, hashTable.size); // 计算键的散列值并得到索引位置
    vector<pair<Key, Value>>& bucket = hashTable.table[index]; // 获取索引位置的桶
    for (auto it = bucket.begin(); it != bucket.end(); ++it) {
        if (it->first == key) {
            bucket.erase(it); // 删除键值对
            break;
        }
    }
}
// 在散列表中查找指定键的值
Value Search(HashTable& hashTable, Key key) {
    int index = HashFunction(key, hashTable.size); // 计算键的散列值并得到索引位置
    vector<pair<Key, Value>>& bucket = hashTable.table[index]; // 获取索引位置的桶
    for (const auto& entry : bucket) {
        if (entry.first == key) {
            return entry.second; // 返回找到的值
        }
    }
    return defaultValue; // 如果未找到,则返回默认值
}

线性探测法

线性探测法(Linear Probing)是一种解决散列表中哈希冲突的开放寻址法。当哈希函数将键映射到一个已经被占用的位置时,线性探测法会依次往后查找下一个空闲位置,直到找到一个可用的位置为止。

具体来说,当进行插入或查找操作时,如果键在哈希表中的位置已经被占用,线性探测法会通过逐个检查相邻位置的方式,找到下一个可用的位置。如果下一个位置也被占用,则继续往后查找,直到找到一个空闲位置或者遍历整个散列表。

线性探测法的优势在于实现简单,不需要维护额外的数据结构。它可以将冲突的元素存储在散列表中的连续位置,减少了对内存的访问时间,有利于缓存性能的提升。此外,线性探测法还具有较好的空间利用率,因为所有元素都存储在同一个散列表中。

平方探测法

平方探测法(Quadratic Probing)是解决散列表中哈希冲突的一种开放寻址法。与线性探测法不同,平方探测法在查找下一个可用位置时使用了平方的增量来避免元素聚集在一起的问题。

具体来说,当进行插入或查找操作时,如果哈希函数将键映射到一个已经被占用的位置,平方探测法会通过使用平方的增量来寻找下一个可用位置。例如,在第一次冲突时,会尝试移动12=1个位置,如果仍然冲突,则尝试移动22=4个位置,依次类推。这样可以有效地避免连续的冲突,减少了元素聚集在一起的情况,提高了性能。

平方探测法的优势在于相对于线性探测法,它能够更均匀地分布元素,减少了聚集性,提高了散列表的性能。此外,平方探测法也无需维护额外的数据结构,实现较为简单。

查找成功的平均查找长度

比如给定
    22  43  15
0   1   2   3   4   5   6   7(表长为7)
求查找成功的平均查找长度?
当查找22时,查找长度为1
查找43时,查找长度为2
15时,为3
所以查找成功的平均查找长度为(1+2+3)/元素个数=6/3=2

查找失败的平均查找长度

比如给定
98  22 30  87   11  40  6   20(冲突)
0   1   2   3   4   5   6   7  8  9  10
求查找失败的平均查找长度?
接着假设给一个元素x
x只能从0映射到6(因为编号7是迫不得已才有位置的)
所以分母是7
当x映射到0时查找失败,则查找9次(查找编号0~7+查找为空)
当x映射到1时查找失败,则查找8次(查找编号1~7+查找为空)
当x映射到2时查找失败,则查找7次(查找编号2~7+查找为空)
...
当x映射到6时查找失败,则查找3次(查找编号6~7+查找为空)
所以分子是(9+8+7+...+3)=42
所以查找失败的平均查找长度为42/7

接下来我们开始散列表的专项练习

判断题

1.平均查找长度与节点个数无关的查找方法是:哈希(散列表)法(对)

2.在散列表中,所谓同义词就是:具有相同散列地址的两个元素(对)

3.将M个元素存入用长度为S的数组表示的散列表,则该表的装填因子为M/S。(对)

4.即使把2个元素散列到有100个单元的表中,仍然有可能发生冲突。(对)

5.

6.

7.

解析:

表格为 0 1 2 3 4 5 6 7 8 9

先插入2,2%11=2,所以插入到编号2的位置

0 1 2 3 4 5 6 7 8 9

2

再插入2,理应插到编号2的位置,但2被占,(2+1^2)%11=3,所以插入到编号为3的位置

0 1 2 3 4 5 6 7 8 9

2 2

再插入2,理应插到编号2的位置,但2被占,(2+12)%11=3,所以插入到编号为3的位置,但3被占,(2+22)%11=6,所以插到编号为6的位置

再插入2,理应插到编号2的位置,但2被占,(2+12)%11=3,所以插入到编号为3的位置,但3被占,(2+22)%11=6,但6被占,(2+3^2)%11=0,所以插到编号为0的位置

8.

9.

10.

解析:解析:如果是按取模10的话,会产生冲突。

选择题


解析:26%17=9
25%17=8
72%17=4
38%17=4,冲突,所以放在5
8%17=8,冲突,所以放9,但又冲突,所以放10
18%17=1
58%17=8,冲突,放11

2.

3.在第一次发现冲突之前插入的数字个数 除以 表长度 得到 装填因子

4.

5.

6.

6%11=6
25%11=3
39%11=6 冲突 6+1^2=7
61%11=6 冲突 6-1^2=5

7.

解析:

8.

9.

解析:

98  22 30  87   11  40  6   
0   1   2   3   4   5   6   7  8  9  10
插入20时,20本该占编号为6的位置,但被占,所以后移
98  22 30  87   11  40  6   20
0   1   2   3   4   5   6   7  8  9  10
接着假设给一个元素x
x只能从0映射到6(因为编号7是迫不得已才有位置的)
所以分母是7
当x映射到0时查找失败,则查找9次(查找编号0~7+查找的末尾为空)
当x映射到1时查找失败,则查找8次(查找编号1~7+查找的末尾为空)
当x映射到2时查找失败,则查找7次(查找编号2~7+查找的末尾为空)
...
当x映射到6时查找失败,则查找3次(查找编号6~7+查找的末尾为空)
所以分子是(9+8+7+...+3)=42
所以查找失败的平均查找长度为42/7
目录
相关文章
|
2天前
|
数据可视化 Python
Python模型评估与选择:面试必备知识点
【4月更文挑战第17天】本文深入探讨了Python模型评估与选择在面试中的关键点,包括性能度量、过拟合与欠拟合识别、模型比较与选择、模型融合和偏差-方差权衡。强调了避免混淆评估指标、忽视模型验证和盲目追求高复杂度模型的常见错误,并提供相关代码示例,如交叉验证、网格搜索和超参数调优。通过理解这些概念和技巧,可在面试中展示出色的数据科学能力。
26 12
|
10天前
|
机器学习/深度学习 分布式计算 BI
Flink实时流处理框架原理与应用:面试经验与必备知识点解析
【4月更文挑战第9天】本文详尽探讨了Flink实时流处理框架的原理,包括运行时架构、数据流模型、状态管理和容错机制、资源调度与优化以及与外部系统的集成。此外,还介绍了Flink在实时数据管道、分析、数仓与BI、机器学习等领域的应用实践。同时,文章提供了面试经验与常见问题解析,如Flink与其他系统的对比、实际项目挑战及解决方案,并展望了Flink的未来发展趋势。附带Java DataStream API代码样例,为学习和面试准备提供了实用素材。
30 0
|
10天前
|
SQL 分布式计算 监控
Sqoop数据迁移工具使用与优化技巧:面试经验与必备知识点解析
【4月更文挑战第9天】本文深入解析Sqoop的使用、优化及面试策略。内容涵盖Sqoop基础,包括安装配置、命令行操作、与Hadoop生态集成和连接器配置。讨论数据迁移优化技巧,如数据切分、压缩编码、转换过滤及性能监控。此外,还涉及面试中对Sqoop与其他ETL工具的对比、实际项目挑战及未来发展趋势的讨论。通过代码示例展示了从MySQL到HDFS的数据迁移。本文旨在帮助读者在面试中展现Sqoop技术实力。
24 2
|
10天前
|
监控 负载均衡 Cloud Native
ZooKeeper分布式协调服务详解:面试经验与必备知识点解析
【4月更文挑战第9天】本文深入剖析ZooKeeper分布式协调服务原理,涵盖核心概念如Server、Client、ZNode、ACL、Watcher,以及ZAB协议在一致性、会话管理、Leader选举中的作用。讨论ZooKeeper数据模型、操作、会话管理、集群部署与管理、性能调优和监控。同时,文章探讨了ZooKeeper在分布式锁、队列、服务注册与发现等场景的应用,并在面试方面分析了与其它服务的区别、实战挑战及解决方案。附带Java客户端实现分布式锁的代码示例,助力提升面试表现。
29 2
|
10天前
|
数据采集 消息中间件 监控
Flume数据采集系统设计与配置实战:面试经验与必备知识点解析
【4月更文挑战第9天】本文深入探讨Apache Flume的数据采集系统设计,涵盖Flume Agent、Source、Channel、Sink的核心概念及其配置实战。通过实例展示了文件日志收集、网络数据接收、命令行实时数据捕获等场景。此外,还讨论了Flume与同类工具的对比、实际项目挑战及解决方案,以及未来发展趋势。提供配置示例帮助理解Flume在数据集成、日志收集中的应用,为面试准备提供扎实的理论与实践支持。
24 1
|
11天前
|
分布式计算 资源调度 监控
Hadoop生态系统深度剖析:面试经验与必备知识点解析
本文深入探讨了Hadoop生态系统的面试重点,涵盖Hadoop架构、HDFS、YARN和MapReduce。了解Hadoop的主从架构、HDFS的读写流程及高级特性,YARN的资源管理与调度,以及MapReduce编程模型。通过代码示例,如HDFS文件操作和WordCount程序,帮助读者巩固理解。此外,文章强调在面试中应结合个人经验、行业动态和技术进展展示技术实力。
|
14天前
|
缓存 NoSQL 定位技术
深入探索Redis:面试中必须掌握的关键知识点
深入探索Redis:面试中必须掌握的关键知识点
|
26天前
|
存储 NoSQL Java
Redis 数据结构操作入门
Redis 数据结构操作入门
15 0
|
28天前
|
存储 算法 搜索推荐
【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点(二)
【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点
93 2
|
28天前
|
存储 算法 C++
【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点(一)
【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点
51 2

热门文章

最新文章