将IP地址映射到阵列索引

Question

我正在寻找一种将IP地址映射到数组中索引的好方法。假设我有一个32个大小的数组，我们可以从用户输入的最大可能IP地址将始终是<= 32。我想将此IP地址映射到数组中的某个索引位置，然后使用此索引位置来引用此IP地址。

做这件事最好的技术是什么？IP地址本质上只是一个整数。如果两个地址映射到相同的索引位置，则也需要处理冲突。

ip1 =>转换为某个整数表示i1 =>索引现在仅为i1 % 32

任何适合于转换IP地址的用例的散列技术也将是有用的。

谢谢你的帮助。

Answer 1

您是否期望为您的问题提供任何散列算法参考？

因为您有32个数组大小。

您可以只使用IP地址中的设置位数来索引阵列位置。但是所有的0和1都不是已使用的地址，因此您将丢失2个位置。您可以使用所有半字节的总和进行检查，忽略用于散列的进位位。您可以根据数组大小增加添加的位数。

您还可以仅将您的IP地址的2个字节作为散列的基础，因为单个子网中的高位字节可能是相同的。

在发生冲突的情况下，您需要使用指针数组而不是一维数组，以便可以使用相同的散列存储多个地址。

Answer 2

不可能有一个散列函数来使这成为可能。哈希函数仅将ip地址作为参数，而您需要了解其他元素才能完成您想要的操作:如果您的元素有32个位置和> 32个可能的值，则任何哈希函数都必须存在冲突。

如果这是可能的，hashmap实现将不必考虑冲突，直到大小将大于底层数组的最大大小。他们确实考虑到了:)

看看java hashmap如何将hashcode映射到底层数组的索引可能会很有帮助：

static int  indexFor(int h, int length) {
     return h & (length-1);
 }

如果你使用它，请记住使用2的幂来使它有效。Java从16开始，然后增加到32、64等等。