有哪些学校的网站做的好处,做阿里云网站,hao123设为主页官网下载,iis网站属性没有asp.net 一.哈希表的概念
关于查找元素时#xff1a; 在顺序结构以及平衡树 中#xff0c;元素关键码与其存储位置之间没有对应的关系#xff0c;因此在 查找一个元素时#xff0c;必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N) #xff0c;平衡树中… 一.哈希表的概念
关于查找元素时 在顺序结构以及平衡树 中元素关键码与其存储位置之间没有对应的关系因此在 查找一个元素时必须要经过关键 码的多次比较 。 顺序查找时间复杂度为 O(N) 平衡树中为树的高度即 O( log2 N ) 搜索的效率取决于搜索过程中元素的比较次数。 理想的搜索方法可以 不经过任何比较一次直接从表中得到要搜索的元素 。 如果构造一种存储结构通过某种函 数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快 找到该元素 。 哈希表Hash Table:哈希表是一种使用哈希函数进行键值映射的数据结构它将键key和值value存储在一起。它的内部实现是一个固定大小的数组数组的每个位置被称为存储桶bucket或槽slot,以实现高效的数据查找和插入操作。
在哈希表的用途
哈希表是一种常见且广泛应用的数据结构它在许多领域和应用中发挥着重要作用。以下是哈希表的一些常见用途
查找和检索哈希表能够提供快速的查找和检索操作。通过将键映射到哈希表的存储桶中可以在常数时间复杂度内找到所需的数据。这使得哈希表非常适用于需要快速查找和检索数据的场景。字典和关联数组哈希表常被用作字典或关联数组的实现。通过将键值对存储在哈希表中可以根据键快速查找对应的值。这在许多编程语言中的字典数据结构中得到广泛应用。数据索引哈希表可以用于构建快速的数据索引。将索引关键字映射到哈希表的存储桶中可以在索引数据集时快速定位和检索数据。数据唯一性检查哈希表可以用于快速检查数据的唯一性。通过将数据的哈希值作为键存储在哈希表中可以快速判断数据是否已存在。
二.了解哈希函数
哈希函数是一种将输入数据例如字符串、数字等映射为固定长度的哈希值hash value的函数。哈希函数将任意大小的输入转换为固定大小的输出通常是一个整数或固定长度的字符串。不同的哈希函数在设计和实现上可能会有一些区别。
2.1直接定址法
直接定址法是一种简单的哈希函数它将输入数据直接映射到哈希值的范围。具体来说对于给定的输入直接定址法使用输入值作为哈希值不经过其他复杂的计算。
使用公式hash(key) (A * key B) % M
其中
hash(key) 是输入数据 x 的哈希值A和B是常数用于调整哈希函数的映射方式M 是哈希表的大小用于取模运算确保哈希值在合适的范围内
举例子解释
假设我们有一个哈希表大小为10我们希望将输入的整数映射到该哈希表中。
输入的整数51221
使用了常数 A 3 和 B 2 来说明直接定址法的哈希函数。这些常数的选择是任意的可以根据具体的需求和情况进行调整。
如下图所示 直接定址法作为一种哈希函数具有以下优点和缺点 优点 简单快速直接定址法的计算过程非常简单只需将输入数据直接转换为哈希值没有复杂的计算步骤因此计算速度非常快。低冲突率由于每个输入数据都有唯一的哈希值冲突的概率非常低。在哈希表大小和输入数据范围匹配的情况下冲突几乎是不会发生的。 缺点 依赖数据范围直接定址法要求输入数据的范围与哈希表的大小相匹配如果数据范围过大或过小可能会导致哈希冲突或者浪费存储空间。分布不均匀如果输入数据的分布不均匀某些哈希值可能会被频繁使用而其他哈希值很少使用导致哈希表的性能下降。冲突解决困难直接定址法在处理冲突时比较困难因为不同的输入可能会映射到相同的哈希值。当出现冲突时需要采取额外的措施解决如链地址法或开放定址法。 2.2除留余数法 除留余数法Modulo Division Method是一种常用的哈希函数方法用于将输入数据映射到哈希表中的位置。它基于取模运算的性质将输入数据除以哈希表的大小通常为素数并取余数作为最终的哈希值。
公式hash(key) key % capacity; capacity为存储元素底层空间总的大小。
例子如下 除留余数法作为一种哈希函数方法具有以下优点和缺点
优点
简单高效除留余数法的计算过程非常简单只需进行一次取模运算即可得到哈希值计算速度非常快。均匀分布当哈希表大小 M 为素数时除留余数法可以获得较好的哈希值分布。素数的选择可以降低冲突的概率使得哈希值在哈希表中更均匀地分布。
缺点
冲突率受限除留余数法在处理冲突时的灵活性有限。由于哈希值的范围受限于哈希表的大小当输入数据之间存在关联性或者哈希表大小较小的情况下冲突的概率可能会增加。数据分布依赖除留余数法对输入数据的分布敏感。如果输入数据集的分布不均匀一些哈希值可能会频繁出现而其他哈希值则很少使用导致哈希表的性能下降。限制于素数为了获得较好的哈希值分布除留余数法通常建议选择素数作为哈希表的大小。然而素数的选择可能会受到限制特别是在某些特定的应用环境中。 2.3平方取中法了解
平方取中法Mid-square Method是一种哈希函数方法用于将输入数据映射到哈希表中的位置。它基于对输入数据的平方运算并提取中间部分作为最终的哈希值。
使用以下步骤 将输入数据 x 平方y x^2提取中间部分作为哈希值取 y 的中间部分作为最终的哈希值。
具体提取中间部分的方式可以根据需求和数据范围进行选择。常见的方法包括
取中间 k 位如果 y 是一个多位数可以取 y 中间的 k 位作为哈希值。取中间 k 位后再取模可以先取 y 中间的 k 位然后再对其进行取模运算以确保哈希值在合适的范围内。
例如假设我们有一个三位数的输入数据 x 123我们可以使用平方取中法来计算其哈希值
1. 平方y 123^2 15129 2. 提取中间两位哈希值为 51
平方取中法作为一种哈希函数方法具有以下优点和缺点
优点
简单易实现平方取中法的实现较为简单只需进行平方运算和提取中间部分的操作。较好的分布性当输入数据分布均匀时平方取中法可以获得较好的哈希值分布减少冲突的概率。
缺点
数据分布依赖平方取中法对输入数据的分布敏感。如果输入数据集的分布不均匀一些哈希值可能会频繁出现而其他哈希值则很少使用导致哈希表的性能下降。冲突率受限平方取中法的冲突率受限于平方操作和中间部分的提取方式。在某些情况下平方取中法可能会导致较高的冲突率特别是在数据范围较大时。哈希值范围限制平方取中法的哈希值范围受限于输入数据的位数和中间部分的提取方式。如果哈希表的大小超过了哈希值的范围可能会导致哈希值无法充分覆盖哈希表的索引。 2.4折叠法了解
折叠法Folding Method是一种哈希函数方法用于将输入数据划分为固定大小的块然后对这些块进行相加或位运算以获得最终的哈希值折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况
折叠法的使用步骤
划分块将输入数据分成固定大小的块例如每个块包含4位。相加或位运算对每个块进行相加或位运算操作例如将每个块的位相加。最终哈希值将所有中间结果组合在一起得到最终的哈希值。
例子如下
假设我们有一个输入数据为 987654321我们可以使用折叠法来计算其哈希值。
1. 划分块将输入数据分成固定大小的块例如每个块包含3位。 输入数据987654321 分块结果987 654 321
2. 相加或位运算对每个块进行相加或位运算操作例如将每个块的位相加。 分块结果987 654 321 相加结果9 8 7 246 5 4 153 2 1 6
3. 最终哈希值将所有中间结果组合在一起得到最终的哈希值。 中间结果24 15 6 最终哈希值24156
通过折叠法我们将输入数据 987654321 映射到了哈希值 24156。
优点
简单易实现折叠法的实现相对简单只需要将输入数据划分为块并进行相加或位运算。适用性广泛折叠法可以适用于不同长度的输入数据通过划分块和操作方式的灵活选择可以处理各种数据类型和大小的输入。
缺点
块的选择问题折叠法的效果受到块的大小和选择方式的影响。选择不合适的块大小可能导致冲突率增加或哈希值分布不均匀。数据依赖性折叠法对输入数据的分布敏感如果输入数据的分布不均匀可能会导致一些哈希值频繁出现而其他哈希值很少使用降低哈希表的性能。哈希值范围限制折叠法的哈希值范围受到块的大小和操作方式的限制。如果哈希表的大小超过了哈希值的范围可能会导致哈希值无法充分覆盖哈希表的索引。 2.5随机数法(了解)
随机数法Randomized Hashing是一种哈希函数方法通过使用随机数来计算哈希值。在随机数法中每个输入数据都会与一个随机数进行组合并通过某种哈希函数来计算最终的哈希值随机数法常用于加密和安全领域以及需要高度随机性和分布均匀的哈希值的场景。
随机数法的使用步骤
1. 选择随机数从一个随机数生成器中选择一个随机数。 2. 输入数据与随机数组合将输入数据与随机数进行组合可以简单地将它们连接在一起形成一个新的字符串。 3. 哈希函数计算使用某种哈希函数对组合后的字符串进行计算得到最终的哈希值
举例子如下
假设我们有一个输入数据为 Hello, World!我们可以使用随机数法来计算其哈希值。
1. 选择随机数从一个随机数生成器中选择一个随机数例如选择随机数为 987654321。 2. 输入数据与随机数组合将输入数据与随机数进行组合形成一个新的字符串。 输入数据Hello, World! 随机数987654321 组合结果Hello, World!987654321
3. 哈希函数计算使用某种哈希函数对组合后的字符串进行计算得到最终的哈希值。 哈希函数SHA-256安全哈希算法-256位 哈希值d0e8c2e3f1b9a27a8e2b26a410baea6f4a6e8a4d9b3c6e9e4c8a1b7c8a3d6b7
通过随机数法我们将输入数据 Hello, World! 映射到了哈希值 d0e8c2e3f1b9a27a8e2b26a410baea6f4a6e8a4d9b3c6e9e4c8a1b7c8a3d6b7。每次使用不同的随机数都会得到不同的哈希值增加了哈希值的随机性和分布性。
优点
高度随机性使用随机数可以增加哈希值的随机性降低冲突的概率。哈希值分布均匀通过随机数的引入可以获得更均匀的哈希值分布。
缺点
随机数生成开销每次计算哈希值都需要生成一个随机数这可能会带来一定的计算开销。难以重现哈希值由于使用的随机数是不可预测的难以在重现哈希值的场景中使用。 2.6数字分析法了解
设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某 些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。例如 假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前 7 位都是 相同的那么我们可以 选择后面的四位作为散列地址如果这样的抽取工作还容易出现 冲突还可以对抽取出来的数字进行反转( 如 1234改成 4321) 、右环位移 ( 如 1234 改成 4123) 、左环移位、前两数与后两数叠加 ( 如 1234 改成 123446) 等方法。 数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均 匀的情况。 注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突 三.哈希冲突
3.1了解哈希冲突
哈希冲突是指在使用哈希函数时两个或多个不同的输入值产生了相同的哈希值。换句话说哈希函数将不同的输入映射到了相同的输出。
如下例子 我们需要明确一点由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的这就导致一 个问题冲突的发生是必然的 但我们能做的应该是尽量的 降低冲突率 。 引起哈希冲突的一个原因可能是 哈希函数设计不够合理 。 哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1 之间 哈希函数计算出来的地址能均匀分布在整个空间中 哈希函数应该比较简单 冲突-避免-负载因子调节 负载因子Load Factor是指哈希表中已存储元素数量与哈希表总容量之间的比率关系。它用来衡量哈希表的填充程度。 负载因子通常用公式表示为负载因子 已存储元素数量 / 哈希表总容量 例如如果哈希表中已存储了100个元素而哈希表的总容量为200那么负载因子为 100/200 0.5。 负载因子和冲突率的关系粗略演示 所以当冲突率达到一个无法忍受的程度时我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的那我们能调整的就只有哈希表中的数组的大小。 3.2 线性探测-解决哈希冲突
线性探测一种解决哈希冲突的开放寻址法方法之一。当发生哈希冲突时线性探测会尝试在哈希表中的下一个空槽中查找可用的位置。
具体来说当要插入一个元素到哈希表中并且发现目标槽已经被占用时线性探测会按照一定的规则依次检查下一个槽直到找到一个空槽或者遍历了整个哈希表。通常线性探测的规则是顺序地检查下一个槽即向后移动一个位置。
例子如下 哈希冲突-线性探测法 优点 1. 实现简单线性探测是一种简单直观的解决哈希冲突的方法易于实现和理解。 2. 内存局部性线性探测具有较好的内存局部性即相邻的元素在哈希表中也会相邻存储。这在一定程度上可以提高缓存的命中率减少内存访问的开销。
缺点 1. 聚集性问题线性探测可能导致聚集性问题即连续的哈希冲突会导致连续的元素聚集在一起。这会导致哈希表中出现长串的连续占用的槽位称为聚集。聚集会降低查找、插入和删除操作的效率因为需要线性地探测较长的距离才能找到空槽。 2. 高负载因子敏感线性探测对于高负载因子填充程度高敏感。当哈希表的负载因子接近或超过1时发生冲突的概率会增加导致线性探测的效率下降聚集性问题更加明显。 3. 删除操作复杂线性探测中的删除操作相对复杂因为删除一个元素后后续的元素可能会被移动到前面的位置以填补空缺。这会导致查找操作更加复杂需要额外的逻辑来处理元素的迁移。 3.3 二次探测-解决哈希冲突 线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题而找到下次探测的方法是 举例子如下 哈希冲突-二次探测法 优点 1. 减少聚集性问题相比于线性探测二次探测能够更均匀地分布元素减少聚集性问题。这意味着元素在哈希表中的分布更加均匀减少了长串连续占用的槽位提高了查找和插入操作的效率。 2. 较简单的实现相对于其他开放寻址法方法如双重哈希二次探测的实现较为简单不需要额外的哈希函数。 缺点 1. 探测序列不完整二次探测可能导致探测序列不完整即某些槽位永远不会被访问到。这是因为二次探测使用的二次函数只能探测到特定的位置可能无法遍历整个哈希表导致某些槽位永远不会被使用。 2. 聚集性问题仍可能存在尽管相对于线性探测二次探测能够减少聚集性问题但在高负载因子下仍可能出现聚集。当哈希表填充程度较高时依然存在连续的哈希冲突导致元素聚集在一起影响操作的效率 注意 当表的长度为质数且表装载因子 a 不超过 0.5 时新的表项一定能够插入而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a 不超过 0.5如果超出必须考虑增容。因此比散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。 3.4哈希桶-解决哈希冲突 哈希桶开散列法又叫链地址法 ( 开链法 ) 首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 如下图展示 从上图可以看出开散列中每个桶中 开散列可以认为是把一个在大集合。 哈希桶散列表的代码的实现 package HashBucket;public class hashBucket {static class Node{public int key;public int val;public Node next;public Node(int key,int val){this.key key;this.val val;}}public Node[] array;//哈希链表public int usedSize;//存放多少个数据public float loadFactor 0.75f;public hashBucket(){array new Node[10];}public void put(int key,int val){int index key % array.length; // 计算key在数组中的索引位置//遍历index下标的链表,是否存在key,存在就更新value,不存在就头插法Node cur array[index];//array[index]是一个结点while (cur ! null) { // 遍历链表if (cur.key key) { // 如果当前节点的key与目标key相等cur.val val; // 更新节点的value值return;}cur cur.next; // 继续遍历下一个节点}// 链表遍历完成未找到目标key执行插入操作Node node new Node(key, val); // 创建一个新的节点存储目标key和valuenode.next array[index]; // 将新节点的next指向当前索引位置的链表头节点array[index] node; // 将新节点设为当前索引位置的链表头节点usedSize; // 更新已使用的大小if(doLoadFactor() 0.75){//进行扩容resize();}}private void resize(){Node[] newArray new Node[2* array.length];//遍历原来的数组for (int i 0; i array.length; i) {Node cur array[i];while(cur!null){Node tmp cur.next;int newIndex cur.key % newArray.length;//采用头插法 插入到新数组的 newIndex下标cur.next newArray[newIndex];newArray[newIndex] cur;cur tmp;}}}private float doLoadFactor(){return usedSize * 1.0f/ array.length;}public int get(int key){int index key % array.length;Node cur array[index];while(cur!null){if(cur.key key){return cur.val;}cur cur.next;}return -1;}}视频展示如下 哈希散列表-put方法演示 补充知识点当散列表扩容时需要注意的事项 哈希散列表扩容时-注意点(tmp的存在) 1.为什么要用到tmp存放cur.next 因为党cur结点移动到新的索引址后,cur.next就存放的是在同一个索引值的下标的地址了,导致原来的就丢失了 2,扩容时需要注意什么: 应当对当时的结点进行遍历,然后放到合适的数组下标,比如没扩容之前元素14放在4下标,扩容之后应当放到数组14下标的位置(往后放) 3.5哈希桶K,V模型 假设现在定义在hashBucket2类中通过定义泛型 K, V允许存储任意类型的键Key和值Value对象。 在put方法中通过传入键K key和值V val的参数可以将键值对存储到散列表中。在创建新的节点时使用传入的键和值来构造一个NodeK, V对象并将其插入到对应桶的链表头部。 hashBucket2类实现的代码如下 package HashBucket;public class hashBucket2K, V {static class NodeK, V {public K key; // 节点的键public V val; // 节点的值public NodeK, V next; // 下一个节点的引用public Node(K key, V val) {this.key key;this.val val;}}public NodeK, V[] array; // 桶数组public int usedSize; // 已使用的桶数量public static final float DEFAULT_LOAD_FACTOT 0.75f; // 默认装载因子public hashBucket2() {array (NodeK, V[]) new Node[10]; // 初始化桶数组初始大小为10}public void put(K key, V val) {int hash key.hashCode() % array.length; // 计算键的哈希码并对桶数组长度取模得到桶的索引int index hash % array.length; // 计算桶的索引NodeK, V cur array[index]; // 获取桶对应的链表头节点while (cur ! null) {if (cur.key.equals(key)) {// 键已存在更新值cur.val val;return;}cur cur.next; // 继续遍历下一个节点}NodeK, V node new Node(key, val); // 创建新的节点node.next array[index]; // 将新节点的next指向桶的原头节点array[index] node; // 将新节点设为桶的头节点实现头插法usedSize; // 更新已使用的桶数量}public V get(K key) {int hash key.hashCode(); // 计算键的哈希码int index hash % array.length; // 计算桶的索引NodeK, V cur array[index]; // 获取桶对应的链表头节点while (cur ! null) {if (cur.key.equals(key)) {// 找到与键匹配的节点返回对应的值return cur.val;}cur cur.next; // 继续遍历下一个节点}return null; // 未找到匹配的键返回null}
} 提示Java中的泛型允许在运行时使用任意类型的对象因此可以存储各种类型的对象 Test类的实现的代码如下 package HashBucket;import java.util.HashMap;
import java.util.Map;
import java.util.Objects;class Student{String id;public Student(String id){this.id id;}//会根据id生产hashcodeOverridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Student student (Student) o;return Objects.equals(id, student.id);}Overridepublic int hashCode() {return Objects.hash(id);}
}
public class Test {public static void main(String[] args) {Student student1 new Student(563342523);Student student2 new Student(563342523);hashBucket2Student,Integer hashbucket2 new hashBucket2();hashbucket2.put(student1,20);//通过存入student1对象可以查看student2的val因为在相同位置Integer val hashbucket2.get(student2);System.out.println(Value for student2: val);}
} 这里主要介绍的是(重点)当需要自定义相等性比较和哈希码计算时必须重写equals和hashCode方法以确保对象在比较和存储时的一致性和正确性。重写这两个方法可以根据对象的内部状态来确定相等性并为相等的对象生成相同的哈希码使它们能够正确地在散列表中进行操作。 比如在给定的代码中Studentb重写了equals和hashCode方法根据id字段来判断对象的相等性和计算哈希码。由于student1和student2的id字段值相同根据equals方法的逻辑它们被认为是相等的对象。 当student1作为键存入散列表时散列表会根据hashCode方法计算出哈希码并将键值对存储在相应的桶位置。 接下来当使用student2作为键调用散列表的get方法时散列表会根据hashCod方法计算出student2的哈希码并在相应的桶位置进行查找。由于student1和student2的哈希码相同根据散列表的逻辑它们会被认为是相等的键。 运行如下 如果没有重写equals和hashCode方法 package HashBucket;import java.util.HashMap;class Student {String id;public Student(String id) {this.id id;}
}public class Test {public static void main(String[] args) {Student student1 new Student(563342523);Student student2 new Student(563342523);HashMapStudent, Integer map new HashMap();map.put(student1, 20);// 由于没有重写 hashCode() 和 equals() 方法student1 和 student2 被视为不同的对象// 所以无法通过 student2 获取相应的值Integer val map.get(student2);System.out.println(val); // 输出: null}
} Student 类未重写 hashCode() 和 equals() 方法。因此尽管 student1 和 student2 的ID相同它们被视为不同的对象。当试图使用 student2 作为键来获取值时由于哈希表中的键不匹配返回的值为 null。 四.五道相关例题
1.只出现一次的数字 解题思路判断元素是否存在于集合中来找出只出现一次的元素。在第一次遍历时将出现过的元素添加到集合中如果遇到重复元素则移除。最后在第二次遍历时找出集合中剩下的唯一元素并返回。 力扣-只出现一次的数字 2.138. 随机链表的复制 - 力扣LeetCode
解题思路
创建一个 HashMap哈希映射用于存储原节点和复制节点的对应关系。键为原节点值为复制节点。第一次遍历原链表创建新的复制节点并将原节点和复制节点的对应关系存储在 map 中。第二次遍历原链表根据 map 中存储的对应关系修改每个复制节点的 next 指针和 random 指针。 通过 map.get(cur) 获取当前原节点对应的复制节点。将复制节点的 next 指针指向原节点的 next 节点的复制节点。将复制节点的 random 指针指向原节点的 random 节点的复制节点。返回复制链表的头节点即 map.get(head)。 力扣-复制带随机指针的链表 3.771. 宝石与石头 - 力扣LeetCode
解题思路 创建一个 HashSet哈希集合用于存储宝石的字符。遍历宝石字符串 jewels 的每个字符 ch将其添加到 hashset 中。初始化一个计数器 count 为 0。遍历石头字符串 stones 的每个字符 ch如果 hashset 包含字符 ch则增加 count 的值。返回计数器 count 的值即宝石字符串在石头字符串中出现的次数。 力扣-石头与宝石 4. 旧键盘 (20)__牛客网 (nowcoder.com) 解题思路
在循环体内通过in.nextLine()分别获取两行输入字符串分别赋值给string1和string2。调用func(string1, string2)方法并将获取的两个字符串作为参数传递给该方法。func方法的作用是将str1中不在str2中出现的字符打印出来。首先创建一个HashSet集合set用于存储str2中的字符转换为大写形式。然后创建另一个HashSet集合set2用于存储已经打印过的字符。遍历str1中的每个字符转换为大写形式如果该字符既不在set中也不在set2中则打印该字符并将其添加到set2集合中。循环结束后程序继续等待下一组输入直到没有更多的输入行。 5.692. 前K个高频单词 - 力扣LeetCode
解题思路这个较为复杂
首先通过遍历words数组使用HashMap统计每个单词出现的次数并将其存储在map中其中单词作为键出现次数作为值。
接下来创建一个小根堆minHeap来存储出现次数最高的k个单词。小根堆中的元素是Map.EntryString, Integer类型表示单词和对应的出现次数。小根堆的大小始终保持在k以内。
通过自定义的比较器Comparator将minHeap构建为小根堆。在比较器中首先比较单词出现次数如果出现次数相同则按照字典序进行比较以满足题目要求。
遍历map的每个键值对如果minHeap的大小小于k则直接将当前键值对加入minHeap中。否则取出堆顶元素出现频率最小的单词与当前键值对进行比较。如果当前键值对的出现频率比堆顶元素大就将堆顶元素移除并将当前键值对加入堆中。如果出现频率相同根据字典序进行比较如果当前单词字典序较小也进行堆的更新。
最后从小根堆中取出k个频率最高的单词并按照它们在堆中的顺序存储在result列表中返回结果。
小根堆的使用是为了维护出现频率最高的k个单词通过比较和堆的更新操作保持堆中始终存储频率最高的k个单词。这样在遍历完整个map后堆中保留的就是出现频率最高的k个单词而且按照题目要求的字典序排列。 五.总结 1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set 2. java 中使用的是哈希桶方式解决冲突的 3. java 会在冲突链表长度大于一定阈值后将链表转变为搜索树红黑树 4. java 中计算哈希值实际上是调用的类的 hashCode 方法进行 key 的相等性比较是调用 key 的 equals 方 法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值 必须覆写 hashCode 和 equals 方 法 而且要做到 equals 相等的对象 hashCode 一定是一致的。 学习笔记 1.为什么HashMap打印时有时不是按顺序的 因为key % 数组长度根据关键字给算出对应的位置而我们不知道。
2.为什么不用fori循环输出 因为hash的放的位置并不是按数组的下标计算的
3.为什么HaspmapStudent,Interger map new Hash();(Student是自定义的类)不报错 因为Haspmap是不会进行比较key放null也是可以的
4.为什么HashSet存放相同的key输出只有只有一个 因为Hash的底层是一个HashMap是可以去重的每次存储元素的时候默认的value其实就是一个Object对象
5.注意自定义类型比较要用equal而不是 put方法和get方法中提到
6.建议以后在写自定义对象的时候最好自己实现一下equals和hashcode最好也把toString也写一下
7.hashBucketVK - 引用类型的hash桶
8.hashset的底层还是hashmap 结语
哈希函数是一种将输入数据映射为固定大小哈希值的算法用于在哈希表中实现高效的数据查找、插入和删除。哈希冲突是指不同的输入数据经过哈希函数计算后得到相同的哈希值这可能导致数据存储冲突和性能下降。为了解决哈希冲突常用的方法包括开放寻址法和链表法它们能够有效地处理冲突并保证哈希表的性能。哈希函数、哈希表和解决哈希冲突的方法在实现数据结构和算法中发挥着重要作用。
