认识达内从这里开始

算法是大多数人在学习软件编程开发技术的时候都需要熟练掌握的一个编程知识点，而本文我们就通过案例分析来简单了解一下，哈希算法基础知识分享。

数据线性分布

假如我们现在有一组服务器，我们想提出一个在这组服务器之间进行数据存储和查找的策略。让我们从一个简单的方案开始。假设我们一个接一个地填满服务器，即仅当当前服务器已满时，我们才开始将数据写入下一个服务器。

在下图中，我们有一个简单的服务器，一次只能存储4条记录。当服务器变满时，我们添加一个新服务器并向其添加新数据。

好吧，这种方法在任何服务器上写入数据时都非常有效。当您被要求读取特定数据时会发生什么?您需要识别存储给定数据的服务器，然后获取它。你如何识别服务器?您会遍历所有服务器并线性扫描每个服务器吗?这会影响读取性能。

例如：在上面的例子中，如果你被要求查找“NewYork”，因为键和服务器之间没有直接映射，你将不得不线性扫描所有服务器并搜索这个键。

这样的效率是不是很糟糕，那么有没有更好的解决方案呢。

数据哈希分布

哈希算法想必大家都知道，Java中的HashMap就是采用的哈希算法。那么根据这个思路，我们提出了一个新的解决方案，数据根据哈希进行存储管理。

我们看到如果我们有N个服务器，则获取记录的时间复杂度将为O(N)。我们希望在O(1)中高效地读写数据。我们先想到的是提供O(1)查找和写入的HashMap数据结构。

让我们看看Hashing是否可以解决我们的问题。假设我们有N个存储数据的服务器和一个具有分发数据策略的应用程序。该方法类似于HashMap使用的方法。先，对键进行哈希处理，然后确定数据将存放的存储桶。应用程序将先对密钥进行哈希处理，然后通过计算hash(data)%N来确定哪个服务器。

上述算法将给出写入数据的服务器编号。此外，在检索数据时，它将使用相同的逻辑，获取服务器编号并获取数据。读取和写入都在O(1)中完成。

让我们来看一个例子。假设我们有三个名为S0、S1和S2的服务器。我们的钥匙是世界城市名称。使用哈希，我们计算需要将密钥分配到的存储桶或服务器。

密钥的哈希和计算桶

密钥分配

但这在分布式系统中总是有效的吗?我们会遇到以下问题：

如果我们添加更多服务器，则hash(data)%N会有所不同。这意味着我们将不得不在添加新服务器时重新分配所有数据。

如果删除其中一台服务器，我们将遇到同样的问题。由于此处服务器的数量N是可变的，因此所有密钥都会受到影响。

以下是添加新服务器时发生的情况的说明。随着服务器数量从3台增长到4台，桶的计算逻辑将变为Hash%4。

新旧密钥分配

在添加新服务器时，我们观察到三个键中的两个受到了影响。如果我们添加一个新服务器，键Madrid的桶将是0(S0)而不是1(S1)。我们必须将此密钥移动到服务器S1以确保我们的应用程序找到它。因此，我们必须重新散列所有现有密钥并将它们分配给不同的服务器。在坏的情况下，这可能会影响系统中的所有密钥。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!请读者仅作参考。更多内容请加抖音达内三江区域学习了解。