行业知识
【java数据结构】HashMap和HashSet
2026-11-18 19:42:57
来源:互联网转载
���录
一.认识哈希表:
1.1什么是哈希表?
1.2哈希表的表示:
1.3常见哈希函数:
二.认识HashMap和HashSet:
2.1关于Map.Entry的说明:,>
2.2Map常用方法说明:
2.3HashMap的使用案例:
2.4Set常见方法说明:
2.5HashSet使用案例:
源码:
一.认识哈希表:
1.1什么是哈希表?
之前的学习中,如果我们要查找一个元素,肯定是要经过比较的,那有没有一种办法,可以不用经过比较,直接就能拿到呢?
如果我们能构造一种存储结构,通过一种函数 (hashFunc) 使元素的存储位置与函数得出的关键码之间能够建立一一映射的关系,那么在查找某个元素的时候,就能通过这个函数来很快的找到该元素所在的位置。
这种函数就叫做哈希(散列)函数,上述所说构造出来的结构,叫做哈希表或者称为散列表。
哈希表简介:
哈希表(Hash Table):也叫做散列表。是根据关键码值(Key Value)直接进行访问的数据结构。哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做「哈希函数(散列函数)」,存放记录的数组叫做「哈希表(散列表)」。
1.2哈希表的表示:
举个栗子:为了记录一个班的学生的信息,分别包括学号和姓名。我们就可以用哈希表(数组加链表)来记录,这里学号(关键值key)通过哈希函数得到一个数组下标,这个下标就是这个学生信息存放在对应数组中的位置,同时学生的信息(姓名和学号)叫做键值对,又称作Entry
使用方法:
- 向哈希表中插入一个关键码值:哈希函数决定该关键字的对应值应该存放到表中的哪个区块,并将对应值存放到该区块中。
- 在哈希表中搜索一个关键码值:使用相同的哈希函数从哈希表中查找对应的区块,并在特定的区块搜索该关键字对应的值。
- 实现哈希表: 数组+链表 或者 数组+二叉树
1.3常见哈希函数:
- 直接定值法--(常用):取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B 优点:简单、均匀 缺点:需要事先知道关 键字的分布情况 使用场景:适合查找比较小且连续的情况
- . 除留余数法--(常用) : 设散列表中允许的 地址数为 m ,取一个不大于 m ,但最接近或者等于 m 的质数 p 作为除数,按照哈希函数: Hash(key) = key% p(p
上一篇:车辆转让合同书要公章吗备案怎么办
下一篇:全球服服务器锁定怎么解锁?