2

私は高速になるように設計されたCでプログラムを書いています。

データフロー内の IP アドレスの出現回数を保存したいと考えています。たとえば、約 2 000 000 の IP アドレスを含む 100MB のバイナリ ファイルを分析します (ただし、プログラムは x-GB ファイルにも使用される可能性があります)。

私の考えはハッシュテーブルを使用することなので、これらのハッシュ関数が必要です:

20b_int indexToIPv4HashTable = hashIPv4(32b_int addr4);
20b_int indexToIPv6HashTable = hashIPv6(128b_int addr6);

この関数がいつか衝突しても問題はないと思います (Separate chaining を使用してこれを解決します)。

  • どのハッシュ関数を使用すればよいですか?
  • この問題にはハッシュ テーブルを使用することをお勧めします。

ちょっとした数学:

  • 20b index = 1 048 576 要素 (足りるか? )
  • 32b 要素 = 4B 要素 = 4MB テーブル サイズ (プログラムが現在のコンピュータで実行される場合、このサイズは問題ありませんか? )

注: IP アドレスでマスクが指定されている場合があります。例: IPv4/24 --> 現在、2^32 ではなく 2^24 の異なる IPv4 アドレスしかありません。マスクが設定されている場合、別のハッシュ テーブル サイズを使用する必要がありますか?

絶対に優先するのはスピードです。

4

1 に答える 1

3

ところで、上記の 32 ビット インデックス サイズの 4Mb ではなく、4Gb を意味していると思います。また、エントリごとに 1 バイトしか必要としないことを前提としています (最大 255 ヒット)。

アドレスの分布を知らずに、どのハッシュが優れているかを知ることは困難です。それらがアドレス空間全体に多かれ少なかれランダムに分散している場合 (そして、ほとんどの IPv6 アドレスが割り当てられていないことはわかっています)、アドレスのいくつかのビットを選択してそれを使用します。

例として、ipv4 の場合はアドレスに均等に分散された 5 つの 4 ビット領域を選択し、v6 の場合はその中間のどこかから下位 16 ビット + 4 ビットを選択します。

しかし、crc32 命令を使用する最新の x86 を使用している場合、ほぼ確実に十分なハッシュが生成され、高速です。

#define HASH_MASK ((1<<20)-1)

static inline int hash32( unsigned int foo )
{
  return __builtin_ia32_crc32si( 0, foo ) & HASH_MASK;
}

static inline int hash128( const char *data )
{
  int res = 0, i;
  for( i=0; i<4; i++, data+=4 )
    res = __builtin_ia32_crc32si( res, *(int32_t *)data ); 
  return res & HASH_MASK;
}

これは非常に移植性が低く、x86 でしか動作しないだけでなく、一部の x86 マシンでしか動作しないことに注意してください (gcc を使用している場合は、-msse4.2 も必要です)。

1 つの注意: 1 秒あたりに大量のエントリを処理していない限り (つまり、大量のエントリを処理している場合を除きます)、ハッシュ関数の速度は問題になりません。ハッシュ バケット内のデータの拡散は影響を与える可能性がありますが、リンク リスト バケット ハッシュ テーブルの単純なサイズ変更なしの実装でさえ、リンクが 100 以上にならない限り、少なくとも 1 秒あたり数億のヒットを処理できます。長いです。実際、ファイルが読み取られるハードドライブの速度が制限要因になる可能性が最も高くなります。

于 2014-02-27T13:45:09.687 に答える