The OpenNET Project / Index page

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

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

Hash Tables

Hash Tables — Связь между ключами и значениями для быстрого поиска.

Краткое описание


#include <glib.h>


            GHashTable;
GHashTable* g_hash_table_new                (GHashFunc hash_func,
                                             GEqualFunc key_equal_func);
GHashTable* g_hash_table_new_full           (GHashFunc hash_func,
                                             GEqualFunc key_equal_func,
                                             GDestroyNotify key_destroy_func,
                                             GDestroyNotify value_destroy_func);
guint       (*GHashFunc)                    (gconstpointer key);
gboolean    (*GEqualFunc)                   (gconstpointer a,
                                             gconstpointer b);
void        g_hash_table_insert             (GHashTable *hash_table,
                                             gpointer key,
                                             gpointer value);
void        g_hash_table_replace            (GHashTable *hash_table,
                                             gpointer key,
                                             gpointer value);
guint       g_hash_table_size               (GHashTable *hash_table);
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);
void        g_hash_table_foreach            (GHashTable *hash_table,
                                             GHFunc func,
                                             gpointer user_data);
gpointer    g_hash_table_find               (GHashTable *hash_table,
                                             GHRFunc predicate,
                                             gpointer user_data);
void        (*GHFunc)                       (gpointer key,
                                             gpointer value,
                                             gpointer user_data);
gboolean    g_hash_table_remove             (GHashTable *hash_table,
                                             gconstpointer key);
gboolean    g_hash_table_steal              (GHashTable *hash_table,
                                             gconstpointer key);
guint       g_hash_table_foreach_remove     (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);
guint       g_hash_table_foreach_steal      (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);
void        g_hash_table_remove_all         (GHashTable *hash_table);
void        g_hash_table_steal_all          (GHashTable *hash_table);
gboolean    (*GHRFunc)                      (gpointer key,
                                             gpointer value,
                                             gpointer user_data);
#define     g_hash_table_freeze             (hash_table)
#define     g_hash_table_thaw               (hash_table)
void        g_hash_table_destroy            (GHashTable *hash_table);
GHashTable* g_hash_table_ref                (GHashTable *hash_table);
void        g_hash_table_unref              (GHashTable *hash_table);

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

Описание

GHashTable обеспечивает связь между ключами и значениями для наиболее быстрого поиска значения полученного ключа.

Помните что не ключи не их значения не копируются при помещении в GHashTable, поэтому они должны существовать для жизнеспособности GHashTable. Это значит использование статических строк допустимо, а временные строки (например создаваемые в буферах и возвращаемые GTK+ виджетами) должны быть скопированы с помощью g_strdup() перед вставкой в таблицу.

Если ключи и значения распределяются динамически, вы должны обязательно убедиться в их освобождении после удаления из GHashTable, а также когда они перезаписываются при новой вставке в GHashTable. Также не желательно смешивать статические строки и динамически-распределённые строки в GHashTable, потомучто тогда трудно определить должна ли строка освобождаться.

Для создания GHashTable, используйте g_hash_table_new().

Для вставки ключа и значения в GHashTable, используйте g_hash_table_insert().

Для поиска значения соответствующего полученному ключу используйте g_hash_table_lookup() и g_hash_table_lookup_extended().

Для удаления ключа и значения, используйте g_hash_table_remove().

Для вызова функции для каждой пары ключа и значения используйте g_hash_table_foreach().

Для уничтожения GHashTable используйте g_hash_table_destroy().

Детали

GHashTable

typedef struct _GHashTable GHashTable;

Структура GHashTable является непрозрачной структурой данных представляющей Hash Table. Доступ к ней может осуществляться только функциями описанными ниже.


g_hash_table_new ()

GHashTable* g_hash_table_new                (GHashFunc hash_func,
                                             GEqualFunc key_equal_func);

Создаёт новую GHashTable с количеством ссылок равным 1.

hash_func : функция для создания хэш значения из ключа. Хеш значения используются для определения места хранения ключей внутри структуры данных GHashTable. Функции g_direct_hash(), g_int_hash() и g_str_hash() обеспечивают некоторые основные типы ключей. Если hash_func это NULL, то используется g_direct_hash().
key_equal_func : функция проверяющая эквивалентность двух ключей. Используется при поиске ключа в GHashTable. Функции g_direct_equal(), g_int_equal() и g_str_equal() обеспечивают основные типы ключей. Если key_equal_func это NULL, ключи сравниваются непосредственно в стиле g_direct_equal(), но без накладных расходов вызова функции.
Возвращает : новая GHashTable.

g_hash_table_new_full ()

GHashTable* g_hash_table_new_full           (GHashFunc hash_func,
                                             GEqualFunc key_equal_func,
                                             GDestroyNotify key_destroy_func,
                                             GDestroyNotify value_destroy_func);

Создаёт новую GHashTable, похожа на g_hash_table_new() с количеством ссылок равным 1 и позволяет определять функции для освобождения памяти распределённой для ключа и значения которые получит вызов когда удалит элементы из GHashTable.

hash_func : функция для создания хеш значения из ключа.
key_equal_func : функция для проверки эквивалентности двух ключей.
key_destroy_func : функция освобождающая распределённую память для ключа используемая при удалении элемента из GHashTable или NULL если вам не нужно выполнять такую функцию.
value_destroy_func : функция освобождающая память, распределённую для значения, используемую при удалении элемента из GHashTable или NULL если вам не нужно выполнять такую функцию.
Возвращает : новая GHashTable.

GHashFunc ()

guint       (*GHashFunc)                    (gconstpointer key);

Специальный тип хеш функции которая помещается в g_hash_table_new() когда создаётся GHashTable.

В функцию помещается ключ и она должна вернуть хеш значение guint. Функции g_direct_hash(), g_int_hash() и g_str_hash() обеспечивают хеш-функции которые могут использоваться когда ключ gpointer, gint и gchar* соответственно.

ПОПРАВЬТЕ МЕНЯ: Здесь необходимо больше подробностей. Хеш-значения должны быть равномерно распределены по довольно большому диапазону? Модуль берётся с размером хеш таблицы (простое число) для поиска области памяти в которую помещается ключ. Функция должна быть очень быстрой, так как вызывается для каждого разыскиваемого ключа.

key : ключ.
Возвращает : хеш значение соответствующее ключу.

GEqualFunc ()

gboolean    (*GEqualFunc)                   (gconstpointer a,
                                             gconstpointer b);

Определяет тип функции используемой для проверки эквивалентности двух значений. Функция должна возвращать TRUE если оба значения эквивалентны или иначе FALSE.

a : первое значение.
b : значение для сравнения.
Возвращает : TRUE если a = b; иначе FALSE.

g_hash_table_insert ()

void        g_hash_table_insert             (GHashTable *hash_table,
                                             gpointer key,
                                             gpointer value);

Вставляет новый ключ и значение в GHashTable.

Если ключ уже существует в GHashTable его текущее значение переписывается новым. Если вы поместите value_destroy_func когда создаёте GHashTable, старое значение освобождается с помощью этой функции. Если вы поместите key_destroy_func когда создаёте GHashTable, помещаемый ключ освобождается с помощью этой функции.

hash_table : GHashTable.
key : вставляемый ключ.
value : значение связанное с ключом.

g_hash_table_replace ()

void        g_hash_table_replace            (GHashTable *hash_table,
                                             gpointer key,
                                             gpointer value);

Вставляет новый ключ и значение в GHashTable аналогично g_hash_table_insert(). Разница в том, что если ключ уже существует в GHashTable, он переписывается новым значением. Если вы поместили value_destroy_func когда создавали GHashTable, старое значение освобождается с помощью этой функции. Если вы поместили key_destroy_func когда создавали GHashTable, старый ключ освобождается с помощью этой функции.

hash_table : GHashTable.
key : ключ для вставки.
value : значение связываемое с ключом.

g_hash_table_size ()

guint       g_hash_table_size               (GHashTable *hash_table);

Возвращает количество элементов находящихся в GHashTable.

hash_table : GHashTable.
Возвращает : количество пар ключ/значение в GHashTable.

g_hash_table_lookup ()

gpointer    g_hash_table_lookup             (GHashTable *hash_table,
                                             gconstpointer key);

Находит ключ в GHashTable. Помните что эта функция не может отличить ключ который не представлен от ключа который представлен но имеет значение NULL. Если вам нужно знать о таком различии, используйте g_hash_table_lookup_extended().

hash_table : GHashTable.
key : ключ для поиска.
Возвращает : связанное значение, или NULL если ключ не найден.

g_hash_table_lookup_extended ()

gboolean    g_hash_table_lookup_extended    (GHashTable *hash_table,
                                             gconstpointer lookup_key,
                                             gpointer *orig_key,
                                             gpointer *value);

Находит ключ в GHashTable, возвращает оригинальный ключ и связанное значение gboolean которое TRUE если ключ был найден. Это полезно если вам нужно освободить память распределённую для оригинального ключа, например перед вызовом g_hash_table_remove().

hash_table : GHashTable.
lookup_key : ключ для поиска.
orig_key : возвращает оригинальный ключ.
value : возвращает значение связанное с ключом.
Возвращает : TRUE если ключ был найден в GHashTable.

g_hash_table_foreach ()

void        g_hash_table_foreach            (GHashTable *hash_table,
                                             GHFunc func,
                                             gpointer user_data);

Вызывает полученную функцию для каждой пары ключ/значение в GHashTable. В функцию помещается ключ и значение каждой пары, а также параметр user_data. Хеш таблица не может меняться пока функция перемещается через неё (вы не можете добавлять/удалять элементы). Для удаления всех элементов соответствующих предикату, используйте g_hash_table_foreach_remove().

hash_table : GHashTable.
func : функция вызываемая для каждой пары ключ/значение.
user_data : пользовательские данные помещаемые в функцию.

g_hash_table_find ()

gpointer    g_hash_table_find               (GHashTable *hash_table,
                                             GHRFunc predicate,
                                             gpointer user_data);

Вызывает полученную функцию для пар клю/значение в GHashTable, пока predicate не вернёт TRUE. В функцию помещается ключ и значение каждой пары, и полученный параметр user_data. Хеш таблица не может изменяться пока функция перемещается через неё (вы не можете добавлять/удалять элементы).

hash_table : GHashTable.
predicate : функция для проверки каждой пары ключ/значение на определённое свойство.
user_data : пользовательские данные помещаемые в функцию.
Возвращает : Значение первой возвращаемой пары ключ/значение, для которой функция вычислила TRUE. Если пара с требуемым свойством не найдена, возвращается NULL.

Начиная с версии 2.4


GHFunc ()

void        (*GHFunc)                       (gpointer key,
                                             gpointer value,
                                             gpointer user_data);

Определяет тип функции помещаемойв g_hash_table_foreach(). Она вызывается с каждой парой ключ/значение, вместе с параметром user_data который помещается в g_hash_table_foreach().

key : ключ.
value : значение соответствующее ключу.
user_data : пользовательские данные помещаемые в g_hash_table_foreach().

g_hash_table_remove ()

gboolean    g_hash_table_remove             (GHashTable *hash_table,
                                             gconstpointer key);

Удаляет ключ и связанное с ним значение из GHashTable.

Если GHashTable был создан используя g_hash_table_new_full(), ключ и значение освобождаются используя вставленную функцию уничтожения, иначе вы должны убедиться что освободили все динамически распределённые значения самостоятельно.

hash_table : GHashTable.
key : удаляемый ключ.
Возвращает : TRUE если ключ был найден и удалён из GHashTable.

g_hash_table_steal ()

gboolean    g_hash_table_steal              (GHashTable *hash_table,
                                             gconstpointer key);

Удаляет ключ и связанное с ним значение из GHashTable, без вызова функции уничтожения ключа и значения.

hash_table : GHashTable.
key : ключ для удаления.
Возвращает : TRUE если ключ был найден и удалён из GHashTable.

g_hash_table_foreach_remove ()

guint       g_hash_table_foreach_remove     (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);

Вызывает полученную функцию для каждой пары ключ/значение в GHashTable. Если функция вернула TRUE, то ключ/значение удаляется из GHashTable. Если ключ или значение помещаются в функцию уничтожения при создании GHashTable, она используется для освобождения распределённой памяти удаляемых ключей и значений.

hash_table : GHashTable.
func : функция вызываемая для каждой пары ключ/значение.
user_data : пользовательские данные помещаемые в функцию.
Возвращает : количество удаляемых пар ключ/значение.

g_hash_table_foreach_steal ()

guint       g_hash_table_foreach_steal      (GHashTable *hash_table,
                                             GHRFunc func,
                                             gpointer user_data);

Вызывает полученную функцию для каждой пары ключ/значение в GHashTable. Если функция вернула TRUE, то пара ключ/значение удаляется из GHashTable, но функция уничтожения ключа или значения не вызывается.

hash_table : GHashTable.
func : функция вызываемая для каждой пары ключ/значение.
user_data : пользовательские данные помещаемые в функцию.
Возвращает : количество удаляемых пар ключ/значение.

g_hash_table_remove_all ()

void        g_hash_table_remove_all         (GHashTable *hash_table);

Удаляет все ключи и связанные с ними значения из GHashTable.

Если GHashTable была создана с использованием g_hash_table_new_full(), ключи и значения освобождаются используя помещённую функцию уничтожения, иначе вы должны убедиться что любые динамически распределённые значения освободили самостоятельно.

hash_table : GHashTable

Начиная с версии 2.12


g_hash_table_steal_all ()

void        g_hash_table_steal_all          (GHashTable *hash_table);

Удаляет все ключи и связанные с ними значения из GHashTable без вызова функции уничтожения ключа и значения.

hash_table : GHashTable.

Начиная с версии 2.12


GHRFunc ()

gboolean    (*GHRFunc)                      (gpointer key,
                                             gpointer value,
                                             gpointer user_data);

Определяет тип функции помещаемой в g_hash_table_foreach_remove(). Она вызывается с каждой парой ключ/значение, вместе с параметром user_data помещённым в g_hash_table_foreach_remove(). Она должна вернуть TRUE если пара ключ/значение должна быть удалена из GHashTable.

key : ключ.
value : значение связанное с ключом.
user_data : пользовательские данные помещаемые в g_hash_table_remove().
Возвращает : TRUE если пара ключ/значение должна быть удалена из GHashTable.

g_hash_table_freeze()

#define     g_hash_table_freeze(hash_table)

Внимание

g_hash_table_freeze устарела и не должна использоваться во вновь создаваемом коде.

Эта функция устарела и будет удалена в следующих релизах GLib. Она ничего не делает.

hash_table : GHashTable

g_hash_table_thaw()

#define     g_hash_table_thaw(hash_table)

Внимание

g_hash_table_thaw устарела и не должна использоваться во вновь создаваемом коде.

Эта функция устарела и будет удалена в следующих релизах GLib. Она ничего не делает.

hash_table : GHashTable

g_hash_table_destroy ()

void        g_hash_table_destroy            (GHashTable *hash_table);

Уничтожает все ключи и значения в GHashTable и уменьшает количество её ссылок на 1. Если ключи и/или значения распределены динамически, вы должны либо освободить сначала их или создать GHashTable с уничтожающим уведомлением используя g_hash_table_new_full(). В последнем случае функция уничтожения, помещённая вами, будет вызвана для всех ключей и значений в течении фазы разрушения.

hash_table : GHashTable.

g_hash_table_ref ()

GHashTable* g_hash_table_ref                (GHashTable *hash_table);

Автоматически увеличивает количество ссылок hash_table на одну. Эта функция MT-безопасна и может быть вызвана из любого потока.

hash_table : правильная GHashTable.
Возвращает : передачу в GHashTable.

Начиная с версии 2.10


g_hash_table_unref ()

void        g_hash_table_unref              (GHashTable *hash_table);

Автоматически уменьшает количество ссылок hash_table на одну. Если количество ссылок сброшено до 0, все ключи и значения будут уничтожены, а вся память, распределённая для хеш таблицы, освобождена. Эта функция MT-безопасна и может быть вызвана из любого потока.

hash_table : правильная GHashTable.

Начиная с версии 2.10


g_direct_equal ()

gboolean    g_direct_equal                  (gconstpointer v1,
                                             gconstpointer v2);

Сравнивает два аргумента gpointer и возвращает TRUE если они равны. Она может быть помещена в g_hash_table_new() как параметр key_equal_func, используя в качестве указателя ключ в GHashTable.

v1 : ключ.
v2 : ключ для сравнения с v1.
Возвращает : TRUE если два ключа равны.

g_direct_hash ()

guint       g_direct_hash                   (gconstpointer v);

Конвертирует gpointer в хеш значение. Она может быть помещена в g_hash_table_new() как параметр hash_func, используя в качестве указателя ключ в GHashTable.

v : gpointer key
Возвращает : хеш значение соответствующее ключу.

g_int_equal ()

gboolean    g_int_equal                     (gconstpointer v1,
                                             gconstpointer v2);

Сравнивает два значения gint и возвращает TRUE если они равны. Она может быть помещена в g_hash_table_new() как параметр key_equal_func, используя в качестве указателей на целочисленные ключи в GHashTable.

v1 : указатель на gint ключ.
v2 : указатель на gint ключ для сравнения с v1.
Возвращает : TRUE если оба ключа равны.

g_int_hash ()

guint       g_int_hash                      (gconstpointer v);

Конвертирует указатель на gint в хеш значение. Она может быть помещена в g_hash_table_new() как параметр hash_func, используя в качестве указателей на целочисленные значения ключи в GHashTable.

v : указатель на gint ключ
Возвращает : хеш значение соответствующее ключу.

g_str_equal ()

gboolean    g_str_equal                     (gconstpointer v1,
                                             gconstpointer v2);

Сравнивает две строки и возвращает TRUE если они равны. Она может быть помещена в g_hash_table_new() как параметр key_equal_func, используя в качестве строк ключи в GHashTable.

v1 : ключ.
v2 : ключ для сравнения с v1.
Возвращает : TRUE если два ключа равны.

g_str_hash ()

guint       g_str_hash                      (gconstpointer v);

Конвертирует строку в хеш значение. Она может помещаться в g_hash_table_new() как параметр hash_func, используя в качестве строки ключ в GHashTable.

v : строка ключ.
Возвращает : хеш значение соответствующее ключу.



Спонсоры:
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2021 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру