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

TL：DR他们将键映射到值。
哈希映射可能是映射概念最常用的实现。它们允许将任意对象与其他任意对象关联。
这对于执行诸如通过某些公共属性将数据分组或连接在一起之类的工作非常有用。
基础结构执行以下操作：
· 计算密钥的哈希
· 修改散列以给出0到存储桶数组大小之间的整数
· 遍历所选存储桶中的链表，比较键的相等性
· 当/如果键匹配，则返回与该键关联的值。
基本结构

文章插图

命名我称这些为哈希图，但根据语言或上下文的不同，它们可以具有不同的名称。
在C＃或Python中，粗略的等效项是一个Dictionary 。
在JAVAscript中，可以使用内置的Map类，但是可以以类似于哈希图的方式使用JavaScript对象。在后台，Javascript不使用哈希图，因为它可以进行一些优化。
Java有一个名为HashMap的类，它也有HashTable，这基本上是相同的。但是，通常建议在HashTable上使用HashMap 。
如果看到称为Dictionary / hashmap / hashtable的内容，则可以将它们视为此故事中描述的数据结构（主要是）。
哈希函数顾名思义，哈希图会执行"哈希"操作。此操作需要一个任意对象并返回一个整数。哈希函数的工作方式可能会填满自己的故事，甚至可能更多。
出于本故事的目的，可以将哈希函数视为执行以下操作的黑盒：
Integer hash = hashFunction(someArbitraryObject);
那为什么有用呢？好吧，如果您可以将任何对象转换为整数，则可以使用该整数导航到数组的索引。这就是hashmap的作用，基本步骤如下：
· 把握关键和价值
· 计算密钥的哈希
· 使用散列查找数组的索引
· 将键和值存储在数组中
这里有一点复杂。哈希函数可以返回哈希值，该哈希值的范围介于整数的最大负值和正值之间。我们不希望数组中包含数十亿个元素，因为这将占用太多空间。我们也没有数组中负索引的概念。
理想情况下，我们希望索引介于0到某个数组的合理大小之间，例如100 。
undefined
为此，我们需要两个函数，绝对函数和模数。
绝对函数将使任何负数成为正数，因此-34671变为+34671 。
模函数用于计算数字相对于另一个的余数。例如，如果我们使用100作为要模数的数字，则：

文章插图

· 0模量100 = 0
· 1模数100 = 1
· 2模数100 = 2
· 3模数100 = 3
· …
· 47模数100 = 47
· …
· 99模数100 = 99
直到达到100 。在100处，模数导致返回值循环回到0 。
所以，
· 100模量100 = 0
· 101模数100 = 1
· 102模数100 = 2
· …
· 147模数100 = 47
· …
· 199模量100 = 99
依此类推，直到达到200 。在200处，返回值循环回到0，并开始向上计数回到99，直到我们要模数的值达到300，然后返回值回到0，然后重复并重复，然后重复。
因此，模数函数可用于将任何（正）整数映射到介于0和我们要模数的值之间的范围内。
给定一个绝对函数和一个模函数，我们可以将我们的散列整数转换为和整数，该范围是我们想要的：

Integer sizeOfArray = array.size();// hashedInteger is somewhere between -BigNumber -> +BigNumberInteger hashedInteger = hashFunction(key);// absInteger is somewhere between 0 -> +BigNumberInteger absInteger = absolute(hashedInteger);// modInteger is somewhere between 0 -> sizeOfArrayInteger modInteger = modulus(absInteger, sizeOfArray);

一旦我们的整数处于数组大小的范围内，就需要将键和值存储在该数组中。
一系列的水桶因此，哈希表的另一部分是"存储桶数组" 。这是一个包含其他列表的数组。这些其他列表通常是链接列表，您可以在我的故事中找到有关链接列表的更多信息。