java - 使用 hashmap 实现优先级队列

Question

这可能是一个非常幼稚的问题或者没有意义。但我真的很困惑优先队列的实现。 为什么我们不能使用以键为优先级、以值作为具有该优先级的数据的 HashMap 。我在这里缺少一些基本知识吗？例如:如果A的优先级是1，B是3，c是4我们可以简单地保留 1,3,4 作为键，A,B,C 分别作为 hashmap 的值来实现优先级队列。请清除我的逻辑

Answer 1

该实现的问题在于它没有利用 HashMap 功能轻松访问给定键的任何元素。由于您正在创建一个队列，您之后将不会有优先级 1、3、4，并且只需要找到 map 的最高优先级，必须完全迭代它才能做到这一点!

map 的工作原理是这样的:它创建一个巨大的数组，所有位置都有空值(非常非常大)。然后，它使用公式获取您的 key (通常是字符串或字符串表示形式)并将其转换为数字。一个简单的方法是对每个字母的字符代码求和，尽管这对于 map 来说是一个糟糕的选择，您可以稍后查找原因。然后，它用数组的模数(余数)大小(例如，Java 中的 n % 大小)来限制该数字，使其成为数组中的有效位置，然后将元素放在那里。这样，就很容易进行密集搜索，因为你不需要搜索，你就知道每个元素在哪里。

因此，如果没有 HashMap 搜索的明显优势，使用 Map 实现队列将非常占用内存。此外，遍历它非常非常昂贵，因为您需要遍历一个巨大的数组并忽略空值；您不确定实际值在哪里。想象一下在您的示例中，优先级从 0 到 100。即使您永远不会有 100 个任务，您也会有一个 100 个位置的数组来迭代，检查每个位置是否有具有该优先级的任务。

更好的方法是使用一个简单的列表并将优先级存储在数据中。假设优先级不随时间变化，您只需在添加时迭代一次，找到正确的位置，并始终访问第一个(或最后一个)元素，即已知最高优先级的元素。

关于性能的最后一点，最好在添加时进行迭代，即使您添加的时间与搜索的时间完全相同。因为当你搜索最高优先级时，你需要一直走到最后，因为可能最后一个元素更大。请注意，HashMap 不会以整齐的新月顺序存储您的项目，即使您的键是数字字符串或整数也是如此。它被专门设计不这样做，以避免冲突(两个相似的对象具有相同的键，因此需要将列表添加到大数组的特定位置)。但是，当您添加时，假设您的列表已经排序，您只需要迭代直到到达正确的目的地。