江苏龙网

  1. 主页 > 生活百科 > >

每个工程师都应该知道的关于Hashmap的知识( 二 )

工程师


插入东西现在，我们有很多事情：
· 我们可以采用任意对象并将其哈希/吸收/修改为适合我们数组的整数
· 我们知道数组存储条目的链接列表 。
· 条目包含键-值对 。
我们可以结合使用它们来描述键值对如何存储在哈希图中：
· 给定键-值对
· 计算密钥的哈希
· 将哈希值转换为介于0和数组大小之间的值
· 在转换后的哈希的索引处找到链接列表
【每个工程师都应该知道的关于Hashmap的知识】· 将键-值对作为条目添加到链接列表的末尾
就完成了 。
键值已存储，然后可以查询 。在继续进行哈希表查询之前，有必要讨论在哈希表中存储元素的时间复杂性 。
简短的答案是它是O（1）或恒定时间 。也就是说，随着哈希图变大，存储键值对的时间不会改变 。这是因为组成哈希表中事物存储的各种操作都是O（1）时间复杂度：
· 计算哈希为O（1）（或者至少它应该是一个复杂的主题，这里不再赘述） 。
· Abs / Mod为O（1）
· 从数组中获取元素是O（1） 。我在数组列表上还有另一个故事 。数组和数组列表不是一回事，但是它们具有许多时间复杂度特征 。
· 向链接列表的末尾添加元素是O（1） 。我在链接列表上的故事对此进行了讨论 。
随着这些操作的变大，哈希表的增长都不会变慢，因此插入哈希表的总体操作也不会随着哈希表的增长而变慢 。
拿东西现在，我们的哈希图充满了键-值对，如果提供键就可以得到我们的值，这将非常有用 。其工作方式如下：

每个工程师都应该知道的关于Hashmap的知识

文章插图
 
· 给定键（但无值）
· 计算密钥的哈希
· 将哈希值转换为介于0和数组大小之间的值
· 在转换后的哈希的索引处找到链接列表
· 开始浏览链接列表中的每个条目
· 对于每个条目，请询问输入键和条目中保持的键是否相等
· 如果它们不相等，则转到下一个条目
· 如果它们相等，则从条目中返回值
通过这些步骤，我们可以获取我们的密钥，并将其映射为一个值 。密钥的约束是您需要能够询问两个密钥是否相等 。在Java中，这不是问题，因为每个对象都实现一个.equals（）方法 。
此操作的时间复杂度是多少？ 与插入地图的情况相比，这是一个更复杂的问题 。时间复杂度非常取决于您在找到具有匹配键的条目之前必须在链接列表中迭代多少个条目 。
有2种极端情况：
· 所有条目都放在一个桶中
· 所有条目均已完美均匀地分布在所有可用存储桶中
所有条目都放在一个存储桶中一种可能的情况是，所有键都被散列/ abs /修改为相同的数组索引 。在这种情况下，所有条目都将添加到同一链接列表中，并且找到与我们的键匹配的条目将花费O（N）（或线性）时间 。在此讨论在链表中找到元素的原因是O（N） 。
线性时间复杂度意味着，随着哈希图变大，在其中查找元素所花费的时间也与哈希图的大小成比例地变大 。如果哈希图增长了100倍，那么花费的时间也将增长约100倍 。
这种情况并不理想，那么我们如何到达这里呢？
undefined
理想情况下，我们需要一个"好的"哈希函数，该函数返回均匀分布的哈希整数，这些整数将全部转换为数组中均匀分布的索引 。
所有条目均已完美均匀地分配从哈希映射中获取数据时，理想的情况是每个条目均已均匀分布在存储桶中 。这导致每个链接列表包含相同数量的条目的情况 。
对于哈希映射，这是最好的情况，因为可以在大致相等的时间内检索每个条目，并且该时间段是最小的 。
从具有均匀分布的条目的哈希图中检索项目的时间复杂度为O（N / k），其中，N是哈希图所保存的条目数，而k是该图具有的存储桶数 。
什么哈希图适合映射任意值顾名思义，它们擅长映射事物 。您可以将数组视为将整数0到N映射到任意值的一种方式 。如果您要处理整数，这很好，但否则就没有用 。
映射允许您从任意对象映射到另一个任意对象 。它可以是字符串，整数或具有多个字段的对象 。
只要可以将键用于生成哈希码，并且可以将其与其他键进行相等性检查，则可以在地图中使用该对象 。
在Java中，每个对象都需要实现.hashcode（）和.equals（）方法，因此Java中的每个对象都可以在映射中使用 。


推荐阅读


上一篇：深入了解定制 Bash

下一篇：梦见被针扎又拔出来 做梦梦到全身被针扎然后拔出来