Простая реализация хэш-карты с одним заголовком для C/C++.
Просто #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
.
Также существует расширенная функция создания 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
.
Кроме того, возврат -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 );
Этот код почти полностью был написан замечательным Питом Уорденом на основе ныне несуществующей записи в блоге Эллиота Бэка. Авторы внесли следующие дополнительные изменения:
Это бесплатное и ничем не обремененное программное обеспечение, общедоступное.
Любой человек имеет право копировать, изменять, публиковать, использовать, компилировать, продавать или распространять это программное обеспечение в виде исходного кода или в виде скомпилированного двоичного файла для любых целей, коммерческих или некоммерческих, и любыми способами.
В юрисдикциях, которые признают законы об авторском праве, автор или авторы этого программного обеспечения передают все права, связанные с авторскими правами на программное обеспечение, в общественное достояние. Мы делаем это на благо общества в целом и в ущерб нашим наследникам и преемникам. Мы намерены, чтобы это обязательство стало явным актом бессрочного отказа от всех нынешних и будущих прав на это программное обеспечение в соответствии с законом об авторском праве.
ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПРЕДОСТАВЛЯЕТСЯ «КАК ЕСТЬ», БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ, ЯВНЫХ ИЛИ ПОДРАЗУМЕВАЕМЫХ, ВКЛЮЧАЯ, НО НЕ ОГРАНИЧИВАЯСЬ, ГАРАНТИЯМИ ТОВАРНОЙ ЦЕННОСТИ, ПРИГОДНОСТИ ДЛЯ ОПРЕДЕЛЕННОЙ ЦЕЛИ И НЕНАРУШЕНИЯ ПРАВ. АВТОРЫ НИ ПРИ КАКИХ ОБСТОЯТЕЛЬСТВАХ НЕ НЕСУТ ОТВЕТСТВЕННОСТИ ЗА ЛЮБЫЕ ПРЕТЕНЗИИ, УБЫТКИ ИЛИ ДРУГУЮ ОТВЕТСТВЕННОСТЬ, БУДЬ В ДЕЙСТВИЯХ ПО КОНТРАКТУ, ПРАВИЛАМ ИЛИ ДРУГИМ ОБРАЗОМ, ВОЗНИКАЮЩИЕ ИЗ, ИЗ ИЛИ В СВЯЗИ С ПРОГРАММНЫМ ОБЕСПЕЧЕНИЕМ ИЛИ ИСПОЛЬЗОВАНИЕМ ИЛИ ДРУГИМИ ДЕЛАМИ С ПРОГРАММНЫМ ОБЕСПЕЧЕНИЕМ.
Для получения дополнительной информации посетите http://unlicense.org/.