C/C++ 用のシンプルな 1 ヘッダーのハッシュマップ実装。
コードに#include "hashmap.h"
だけです。
現在サポートされているコンパイラは、gcc、clang、msvc です。
現在サポートされているプラットフォームは Linux、macOS、Windows です。
ハッシュマップは任意のデータ キーで動作するように作成されています。ポインターとサイズを指定するだけで、そのデータがハッシュ化されます。デフォルトのハッシュは、可能であればハードウェア組み込み関数を使用する crc32 バリアントであり、デフォルトの比較子はmemcmp
のみを使用するため、構造体キーのパディングをゼロにすることをお勧めします。
ハッシュマップを作成するには、 hashmap_create
関数を呼び出します。
const unsigned initial_size = 2 ;
struct hashmap_s hashmap ;
if ( 0 != hashmap_create ( initial_size , & hashmap )) {
// error!
}
initial_size
パラメータは、ハッシュマップの初期サイズを設定するだけです。複数のキーが同じハッシュ エントリにヒットすると、サイズが大きくなる可能性があります。ハッシュマップのサイズは、指定されたinitial_size
超える最も近い 2 の累乗に切り上げられます。
拡張作成関数hashmap_create_ex
もあります。
struct hashmap_s hashmap ;
struct hashmap_create_options_s options ;
memset ( & options , 0 , sizeof ( options ));
// You can set a custom hasher that the hashmap should use.
options . hasher = & my_hasher ;
// You can set a custom comparer that the hashmap should for comparing keys.
options . comparer = & my_comparer ;
// You can also specify the initial capacity of the hashmap.
options . initial_capacity = 42 ;
if ( 0 != hashmap_create_ex ( options , & hashmap )) {
// error!
}
ハッシュマップに項目を入れるには、 hashmap_put
関数を使用します。
int meaning_of_life = 42 ;
char question = 6 * 8 ;
if ( 0 != hashmap_put ( & hashmap , "life" , strlen ( "life" ), & meaning_of_life )) {
// error!
}
if ( 0 != hashmap_put ( & hashmap , "?" , strlen ( "?" ), & question )) {
// error!
}
異なるタイプの複数のエントリが同じハッシュマップ内に存在できることに注意してください。ハッシュマップは型指定されません。任意のvoid*
データをキーの値として保存できます。
ハッシュマップからエントリを取得するには、 hashmap_get
関数を使用します。
void * const element = hashmap_get ( & hashmap , "x" , strlen ( "x" ));
if ( NULL == element ) {
// error!
}
要素が見つからない場合、関数はNULL
を返します。要素を取得するために使用されるキーは、要素をハッシュマップに配置するために使用されるポインタと同じである必要はないことに注意してください。ただし、ヒットが発生するには文字列スライスが一致する必要があります。
ハッシュマップからエントリを削除するには、 hashmap_remove
関数を使用します。
if ( 0 != hashmap_remove ( & hashmap , "x" , strlen ( "x" ))) {
// error!
}
要素が見つからない場合、関数はゼロ以外を返します。要素を取得するために使用されるキーは、要素をハッシュマップに配置するために使用されるポインタと同じである必要はないことに注意してください。ただし、ヒットが発生するには文字列スライスが一致する必要があります。
hashmap_iterate
関数を使用して、ハッシュマップに格納されているすべての要素を反復処理できます。
static int iterate ( void * const context , void * const value ) {
// If the value is 42...
if ( 42 == * ( int * ) value ) {
// Store into our user-provided context the value.
* ( void * * ) context = value ;
// Return 0 to tell the iteration to stop here.
return 0 ;
}
// Otherwise tell the iteration to keep going.
return 1 ;
}
int * value ;
if ( 0 != hashmap_iterate ( & hashmap , iterate , & value )) {
if ( * value != 42 ) {
// error!
}
} else {
// if we got here it means we never found 42 in the hashmap
}
コールバック関数からゼロ以外を返すことで、ハッシュマップの反復を早期に終了できます。おそらく、ハッシュマップからすべての要素を処理して削除するか、特定の値のみを検索したい場合があります。それ以外の場合、コールバックからゼロが返された場合、反復にはハッシュマップ全体が含まれます。
ハッシュマップの内容を出力する必要があるなど、一部のアプリケーションでは、値に加えてキーとキーの長さにアクセスする必要があります。この目的のために、 hashmap_iterate_pairs
という 2 番目の反復子が追加されました。
また、コールバック関数から -1 を返すと、現在の項目を自動的に削除できます。これは、動的に割り当てられたオブジェクトをマップに保存し、マップを破棄するときにメモリを解放する必要がある場合に特に便利です。
int log_and_free_all ( void * const context , struct hashmap_element_s * const e ) {
int counter ;
for ( counter = 0 ; counter < e -> key_len ; counter ++ ) {
fputc ( e -> key [ counter ], ( FILE ) context );
}
fprintf (( FILE ) context , "=%s pair has been freedn" , ( char * ) e -> data );
free ( e -> data );
return -1 ;
}
void shut_down () {
if ( 0 != hashmap_iterate_pairs ( & hash , log_and_free_all , ( void * ) log )) {
fprintf ( stderr , "failed to deallocate hashmap entriesn" );
}
fclose ( log );
hashmap_destroy ( & hash );
}
ハッシュマップに入れられたエントリの数を取得するには、 hashmap_num_entries
関数を使用します。
unsigned num_entries = hashmap_num_entries ( & hashmap );
ハッシュマップに割り当てられた実際のバケット数 (容量) を取得するには、 hashmap_capacity
関数を使用します。
unsigned num_entries = hashmap_capacity ( & hashmap );
ハッシュマップを使い終わったときにハッシュマップを破棄するには、 hashmap_destroy
関数を使用します。
hashmap_destroy ( & hashmap );
このコードはほぼすべて、Elliott Back による今はなきブログ投稿に基づいて、素晴らしい Pete Warden によって書かれました。作成者はさらに次の変更を適用しました。
これは、パブリック ドメインにリリースされた無料で制限のないソフトウェアです。
誰でも、ソース コード形式またはコンパイルされたバイナリとして、商用か非商用かを問わず、目的や手段を問わず、このソフトウェアを自由にコピー、変更、公開、使用、コンパイル、販売、配布することができます。
著作権法を認める管轄区域では、このソフトウェアの作成者は、ソフトウェアに関するすべての著作権をパブリック ドメインに捧げます。私たちは、一般大衆の利益のため、そして私たちの相続人や後継者に不利益をもたらすために、この献身を行います。私たちは、この献身が、著作権法に基づくこのソフトウェアに対する現在および将来のすべての権利を永久に放棄する明白な行為であることを意図しています。
ソフトウェアは「現状のまま」提供され、明示的か黙示的かを問わず、商品性、特定目的への適合性、および非侵害の保証を含むがこれらに限定されない、いかなる種類の保証も行われません。いかなる場合においても、作者は、契約行為、不法行為、その他のいずれであっても、ソフトウェアまたはソフトウェアの使用またはその他の取引に起因または関連して生じる、いかなる請求、損害、またはその他の責任に対しても責任を負わないものとします。
詳細については、http://unlicense.org/を参照してください。