HASH(9) | FreeBSD Kernel Developer's Manual | HASH(9) |
名称
hash, hash32, hash32_buf, hash32_str, hash32_strn, hash32_stre, hash32_strne, jenkins_hash32, jenkins_hash — 一般的なカーネルハッシュ関数書式
#include < sys/hash.h> uint32_t
hash32_buf( const void *buf, size_t len, uint32_t hash);
uint32_t
hash32_str( const void *buf, uint32_t hash);
uint32_t
hash32_strn( const void *buf, size_t len, uint32_t hash);
uint32_t
hash32_stre( const void *buf, int end, const char **ep, uint32_t hash);
uint32_t
hash32_strne( const void *buf, size_t len, int end, const char **ep, uint32_t hash);
uint32_t
jenkins_hash( const void *buf, size_t len, uint32_t hash);
uint32_t
jenkins_hash32( const uint32_t *buf, size_t count, uint32_t hash);
解説
hash32() 関数は、カーネル内で適正なハッシュアルゴリズムのための一貫性がありそして一般的なインタフェースを与えるために使用されます。これらの関数は、メモリブロックと同様に ASCII ヌル文字 で終了する文字列をハッシュするために使用することができます。hash32_buf() 関数は、一般的なバッファハッシュ関数として使用されます。引数 buf は位置を渡すために使用され、 len はバッファの長さです。引数 hash は、既存のハッシュを拡張するために使用されるか、または新しいハッシュを開始するための初期値 HASHINIT が渡されます。
hash32_str() 関数は、 hash で与えられる初期のハッシュ値とともに buf で渡された ヌル文字 で終了する文字列をハッシュするために使用されます。
hash32_strn() 関数は、予想される文字列の最大の長さである、 len 引数を取ることを除いて、 hash32_str() 関数に似ています。
hash32_stre() と hash32_strne() 関数は、パス名の構成要素をハッシュするためにカーネルによって使用されるヘルプ関数です。これらの関数には、ハッシュされる文字列の end によって与えられた文字を見つけるとき終了するという追加の終了条件があります。引数 ep が NULL でないなら、ハッシュ関数がハッシュを終了したバッファ中の位置が設定されます。
jenkins_hash() 関数は、 hash32_buf() のような同じセマンティックスがありますが、よりよい配布でより進歩したハッシュアルゴリズムを提供します。
jenkins_hash32() は、 jenkins_hash() 関数と同じハッシュアルゴリズムを使用しますが、 uint32_t のサイズがある配列でのみ動作します、したがって、よりシンプルで、より速くなります。その最初の引数で uint32_t 値の配列を、2 番目の引数でこの配列のサイズを受け付けます。
戻り値
hash32() 関数は、バッファまたは文字列の 32 ビットのハッシュ値を返します。使用例
LIST_HEAD(head, cache) *hashtbl = NULL; u_long mask = 0; void sample_init(void) { hashtbl = hashinit(numwanted, type, flags, &mask); } void sample_use(char *str, int len) { uint32_t hash; hash = hash32_str(str, HASHINIT); hash = hash32_buf(&len, sizeof(len), hash); hashtbl[hash & mask] = len; }
制限
hash32() 関数は、32 ビットのみの関数です。それらは、特に 32 ビットの上端で、64 ビットには不十分な性能であることが分かります。現在の時点で、これらのハッシュ値が配列の索引に通常使用されるとき、これは大きな制限とは考えられません、これらのハッシュ値が他の手段に使用されるなら、この制限は再び取り上げられるべきです。歴史
hash 関数は、 NetBSD 1.6 ではじめて登場しました。 hash32 関数の現在の実装は、 OpenBSD 3.2 に最初にコミットされ、その後、 FreeBSD 6.1 に取り込まれました。 jenkins_hash 関数は、 FreeBSD 10.0 で追加されました。作者
hash32 関数は、 によって書かれました。 jenkins_hash 関数は、 Bob Jenkins によって書かれました。September 4, 2012 | FreeBSD |