[ новости /+++ | форум | теги | ]

Каталог документации / Раздел "Программирование, языки" / Оглавление документа

Вперед: 2.3 Другие особенности Назад: GNode

2.2.3 Хэш-таблицы

typedef guint (*GHashFunc) (gconstpointer key);

В дополнение к GHashFunc требуется GCompareFunc для проверки ключей на равенство. Немного неприятно то, что GHashTable не использует GCompareFunc таким же образом, что и GSList и GTree, хотя название функции такое же. Здесь от GCompareFunc ожидается, что она будет оператором равенства, возвращая TRUE, если ее аргументы равны. Она не должна быть функцией сравнения в стиле "qsort()". Функция сравнения ключей используется для нахождения правильной пары ключ-значение когда из-за конфликтов в хэше, в ячейке оказывается более одной пары.

Для создания и удаления GHashTable, используйте конструктор и деструктор, приведенные в списке функций 2..21. Запомните, что glib не знает, как удалять данные, содержащиеся в вашей хэш-таблице; она удаляет только саму таблицу.

GHashTable *g_hash_table_new(GHashFunc hash_func,
                             GCompareFunc key_compare_func)
void g_hash_table_destroy(GHashTable *hash_table)

Готовые к использованию хэш-функции и функции сравнения предоставлены для наиболее часто встречающихся ключей: целых чисел, указателей и строк. Все они приведены в списке функций 2..22. Функции для целых чисел принимают указатель на gint, а не сам gint. Если вы передадите NULL в качестве аргумента хэш-функции в функцию "g_hash_table_new()", то по умолчанию будет использоваться "g_direct_hash()". Если вы передадите NULL в качестве аргумента функции сравнения ключей, тогда будет использоваться простое сравнение указателей (эквивалентное "g_direct_equal()", но без вызова функции).

guint g_int_hash(gconstpointer v)
gint g_int_equal(gconstpointer v1, gconstpointer v2)
guint g_direct_hash(gconstpointer v)
gint g_direct_equal(gconstpointer v1, gconstpointer v2)
guint g_str_hash(gconstpointer v)
gint g_str_equal(gconstpointer v1, gconstpointer v2)

Манипулировать хэшем просто. Процедуры сведены в списке функций 2..23. Вставки не копируют ключ или значение; они вводятся в таблицу точно как вы их передали, перезаписывая любую уже существующую пару ключ-значение с тем же ключом (такой же определяется вашей хэш-функцией и функцией сравнения, запомните это). Если это проблема, вы должны делать поиск и удаление перед вставкой. Будьте особенно осторожны, если вы динамически выделяете ключи или значения.

Простая функция "g_hash_table_lookup()" возвращает значение, которое она находит, связанное с ключом key, или NULL, если нет значения. Иногда это не так. Например, NULL может быть самим по себе допустимым значением. Если вы используете строки как ключи, особенно динамически выделяемые строки, знание того, что ключ сожержится в таблице может быть недостаточно; вы, наверное, захотите получить точный "gchar *", который используется в хэш-таблице для представления ключа "foo". Вторая функция поиска предоставляется для подобных случаев. "g_hash_table_lookup_extended()" возвращает TRUE, если поиск был успешным; если она возвращает TRUE, она помещает найденные ключ и значение в переданные указатели.

void g_hash_table_insert(GHashTable *hash_table,
                         gpointer key, gpointer value)
void g_hash_table_remove(GHashTable *hash_table,
                         gconstpointer key)
gpointer g_hash_table_lookup(GHashTable *hash_table,
                             gconstpointer key)
gboolean g_hash_table_lookup_extended(GhashTable *hash_table,
                                      gconstpointer lookup_key,
                                      gpointer *orig_key,
                                      gpointer *value)

GHashTable хранит внутренний массив, размер которого -- простое число. Она также хранит счетчик числа пар ключ-значение, хранимых в таблице. Если среднее число пар на доступные выбросы ячеек ниже 5#5 (или около того), массив делается меньше; если оно превышает 3, то массив делается больше для уменьшения конфликтов. Изменение размеров происходит автоматически когда вы вставляете или удаляете пары из таблицы. Это гарантирует то, что память, используемая хэш-таблицей, расходуется оптимально. К сожалению, если вы проводите большое количество вставок или удалений, перестраивать хэш-таблицу становится неэффективно. Для решения этой проблемы, таблица может быть заморожена, что означает, что изменение размеров временно не производится. Когда вы закончили добавлять или удалять элементы, вы просто размораживаете таблицу, что влечет за собой одиночное вычисление оптимального размера. (Однако, будьте осторожны; замороженная таблица может закончится из-за слишком большого количества конфликтов, если вы добавляете огромное количество данных. Это может быть хорошо, если вы размораживаете перед тем как производить поиск.) Функции в списке функций 2..24.

void g_hash_table_freeze(GHashTable *hash_table)
void g_hash_table_thaw(GHashTable *hash_table)

---

Партнёры:

Хостинг: