为什么HashMap搜索比数组搜索更好

摘要

想象一下：你有一份清单，上面写了你需要找到的东西，但是它们都乱七八糟地放在一个盒子里（比如你的旧玩具收藏）。现在，如果你想找到那个特别的玩具，你会怎么做？你可能不得不将整个盒子全部倒出来，直到你找到它，对吗？当你在搜索某物时，Array基本上就是这样工作的。但是，如果你有一张神奇的地图，在那里你可以说出玩具的名字，地图会立即指向你它的位置呢？不用自己花精力...

想象一下：你有一份清单，上面写了你需要找到的东西，但是它们都乱七八糟地放在一个盒子里（比如你的旧玩具收藏）。现在，如果你想找到那个特别的玩具，你会怎么做？你可能不得不将整个盒子全部倒出来，直到你找到它，对吗？当你在搜索某物时，Array基本上就是这样工作的。

但是，如果你有一张神奇的地图，在那里你可以说出玩具的名字，地图会立即指向你它的位置呢？不用自己花精力就可以！这几乎就是HashMap的作用。让我为你分解一下。

在Array中搜索

当你有一个Array时，就像把所有的玩具排成一排。如果你想找到一个特定的，你从头开始，检查每个玩具，直到你找到你要找的东西。

val array = arrayOf("car", "doll", "ball", "robot")
val searchItem = "ball"
var found = false
for (item in array) {
    if (item == searchItem) {
        found = true
        break
    }
}
if (found) {
    println("$searchItem found in array")
} else {
    println("$searchItem not found in array")
}

你要浏览每个玩具，直到找到你的球。如果球在尾部，你会花更长的时间。这种方法并不难，但是效率不高，特别是如果你的玩具很多（或Array）很长。

时间复杂性：在最坏的情况下，如果子项是最后一个子项或根本不在数组中，您可能必须搜索每个子项。这为您提供了O(n)的时间复杂度，这意味着搜索时间随着Array的大小而线性增长。

在HashMap中搜索

现在，让我们来谈谈HashMap。想象一下，你有这张神奇的地图，每个玩具都有一个特殊的代码（如条形码），可以告诉你它在盒子里的确切位置。因此，你只需扫描代码，你就知道去哪里找。

val hashMap = hashMapOf("car" to 1, "doll" to 2, "ball" to 3, "robot" to 4)
val searchKey = "ball"
if (hashMap.containsKey(searchKey)) {
    println("$searchKey found in HashMap with value ${hashMap[searchKey]}")
} else {
    println("$searchKey not found in HashMap")
}

时间复杂性：HashMap搜索在O(1)时间内工作，这意味着通常需要相同的时间来找到您的物品，无论您的集合有多大。

Hash是如何工作的？

您可能想知道，“HashMap实际上是如何工作的？”秘密在于一种叫做hash函数的东西。让我来分解一下：

哈希函数
当您将子项添加到HashMap时，Hash函数会将密钥（如玩具名称）转换为数字。这个数字被称为Hash Code。
桶分配
然后，Hash Code用于确定在HashMap中存储子项的位置。把它想象成将你指向存储玩具的特定桶的地图。
直接访问
当您想再次找到您的玩具时，您提供密钥，Hash函数会快速计算Hash Code，指向正确的桶，并检索玩具。
碰撞处理
有时，两个键可能会产生相同的Hash Code（想象两个名字相似的玩具）。这被称为碰撞。HashMaps通过将两个子项都存储在同一个存储桶中来处理这个问题，但要单独跟踪它们，因此您仍然可以找到您需要的确切子项。

为什么HashMap如此高效

让我们回到我们的玩具例子。想象一下，你有一个装有1000个玩具的盒子，你需要找到一个特定的玩具：

Array搜索：您可能需要查看每个玩具，最多需要1000步。HashMap搜索：多亏了Hashing功能，无论你有多少个玩具，你都可以直接跳到正确的桶，通常只需1步。
即使您的收藏量增长到10,000或100,000个玩具，HashMap仍然会在几乎相同的时间内找到您的玩具。当您需要搜索大量数据时，这种效率就是为什么HashMaps如此强大。

为什么HashMap更快

使用哈希直接访问：
HashMap使用Hash函数将玩具名称转换为唯一的Code。然后，它使用此代码直接跳转到玩具存储的地方，而不是搜索所有内容。
一致的性能：
无论您有10个子项还是10,000个子项，在HashMap中查找子项所需的时间几乎保持不变，使其效率极高。
处理大量数据：
如果你有一百万个玩具，想象一下搜索它们需要多长时间。但有了HashMap，这就像拥有一个超能力，你可以一动就能找到任何玩具。

Array和HashMap都有其特定的使用场景。但是，如果您只关心速度和效率，特别是在搜索大量数据时，HashMaps就像您的秘密武器。因此，下次您正在构建一些东西并需要决定如何存储数据时，请记住，虽然Array是可靠的，但在快速找到东西时，HashMaps可以使您变得轻松得多。

标签：HashMap Array