Глава 18 Хеш-отображения: xmap и xintmap

Ориентация главы

Отображения решают «найти значение по ключу»: таблица маршрутов находит статистику по пути, таблица сессий — состояние по ID, кэш — запись по ключу. XRT даёт два семейства: xmap с ключом — произвольной байтовой строкой (xbytesview, включая вложенные нули), итерация в порядке вставки; xintmap с ключом — нативным int64 (без вычисления хеша), итерация в порядке возрастания ключей — и на разреженных ключах это самый быстрый «разреженный массив». Оба делят один ритм употребления — герой главы GetOrAdd: «найти или создать» за один шаг, возвращающий указатель на нуль-инициализированный слот значения; сценарии счёта — просто ++. Это высокочастотный контейнер, по употребимости уступающий только массиву, и центральная клетка таблицы выбора главы 23.

18.1引入

Подсчёт попаданий маршрутов HTTP-сервиса: каждый запрос прибывает, по пути находится счётчик маршрута и инкрементируется; путь, которого никогда не было, получает новый счётчик. В записи «сперва проверить наличие, при отсутствии вставить, после вставки инициализировать» каждое звено имеет путь отказа, и две трети кода — защита размером с ноготь. Хуже то, что «поиск дважды» — Has ищет раз, Add внутри локализует ещё раз, и горячий путь напрасно жжёт двойное хеширование.

GetOrAdd склеивает три шага в один: ключ существует — возвращается имеющийся слот; не существует — вставляется нуль-инициализированный новый слот, и возвращается он; выходной параметр сообщает, была ли это вставка. Сценарий счёта становится двумя строками: взять слот, прибавить. Это наглядный пример «форма API решает форму кода» — хороший интерфейс делает правильную запись самой короткой.

18.2概念

Два семейства, два вида ключей

В мире байтовых ключей «пути, имена полей, отпечатки» — законные ключи: xbytesview не требует нуль-терминации; двоично-безопасное соглашение главы 3 действует и для ключей. Целочисленные ключи перепрыгивают хеширование и локализуют напрямую; на малых непрерывных ключах это самый быстрый разреженный массив; итерация — по возрастанию ключей, «экспорт всех сессий в порядке ID» обходится без шага сортировки.

Значения инлайн: ноль попозиционных выделений

Как и у xarray со значимой семантикой, значения отображения хранятся инлайн в слотах — Init нужен только размер значения. Вставка десяти тысяч записей статистики маршрутов — выделения уровня контейнера (рост массива корзин), а не десяти тысяч. Жизненный цикл значений следует контейнеру: один Unit возвращает всё. Хотите хранить большие объекты или объекты, принадлежащие elsewhere? Сделайте типом значения указатель (sizeof(ptr)) и дополните его дескрипторами slot_map главы 17 — комбинация «отображение локализует + дескриптор достаёт» во всей полноте предстанет в таблице соединений главы 67.

Трёхчастный контракт итерации

Итерация выдаёт ключ как заимствованное представление (xbytesview), значение как указатель внутрь слота — срок действия обоих ограничен итерацией (после следующего Next или End нет гарантий). «Не менять контейнер во время итерации» — дисциплина семантики снимка: вставки и удаления инвалидируют снимок; если нужно обходить с правками, сперва соберите обрабатываемые позиции в массив (глава 14), а правьте после конца итерации.

Повторные ключи и семантика неудач

Семейство вставки xmap при существующем ключе возвращает имеющийся слот (без перезаписи, без ошибки) — «вставка как взятие слота» ведёт себя как GetOrAdd минус флаг создания. Удаление идёт по ключу; отсутствующий ключ — неудача. Все пути неудач оставляют контейнер нетронутым (второе и третье из трёх соглашений контейнеров главы 14 действуют здесь как обычно).

18.3示例

Первая полная программа: статистика маршрутов и итерация в порядке вставки

Из репозиторного образца examples/containers/map/main.c:

 */

#include <stdio.h>
#include <xrt.h>



/* 路由统计：整条结构作为值内联在槽中（不是指针）。 */
typedef struct routestat {
	size_t Requests;
	int Status;
} routestat;



int main(void)
{
	xmap tRoutes;
	xmapiter tIterator;
	xbytesview Path;         /* 借用：迭代时交出的键视图 */
	routestat* pStat;
	bool bNew;               /* 出参：本次是否新插入 */

	if ( !xrtMapInit(&tRoutes, sizeof(routestat)) ) {
		return 1;
	}

	



	 */
	pStat = (routestat*)xrtMapGetOrAdd(&tRoutes, XRT_BYTES_LITERAL("/health"), &bNew);
	if ( pStat == NULL ) {
		xrtMapUnit(&tRoutes);
		return 2;
	}
	pStat->Requests++;
	pStat->Status = 200;

	/* 第二个路由同样一步就位。 */
	pStat = (routestat*)xrtMapGetOrAdd(&tRoutes, XRT_BYTES_LITERAL("/metrics"), &bNew);
	if ( pStat == NULL ) {
		xrtMapUnit(&tRoutes);
		return 3;
	}
	pStat->Requests = 8;
	pStat->Status = 204;

	


	 */
	if ( !xrtMapIterBegin(&tRoutes, &tIterator) ) {
		xrtMapUnit(&tRoutes);
		return 4;
	}
	while ( (pStat = (routestat*)xrtMapIterNext(&tIterator, &Path)) != NULL ) {
		printf(
			"%.*s requests=%zu status=%d\n",
			(int)Path.Size,
			(const char*)Path.Data,
			pStat->Requests,
			pStat->Status
		);
	}
	xrtMapIterEnd(&tIterator);
	xrtMapUnit(&tRoutes);
	return 0;
}

Что только что произошло. (1) xrtMapInit(&tRoutes, sizeof(routestat)) передаёт только размер значения — вся структура routestat лежит инлайн в слоте, а не указателем. (2) GetOrAdd("/health") при первом обращении: вставка нуль-инициализированного слота (bNew=true), и после возврата указателя слота вы прямо делаете Requests++ и пишете код состояния — соглашение «новый слот уже обнулён» убирает три шага инициализации. Второй маршрут так же укладывается в две строки. (3) Итерация выводит в порядке вставки /health, /metrics — не в хаосе хеш-значений; свойство исходит из внутренней цепи порядка, а его ценность — стабильность: экспорт конфигураций, генерация отчётов, тестовые утверждения — всё воспроизводимо точно. (4) IterNext выдаёт представление ключа и указатель значения парой; печать ключа через %.*s — поза главы 3. (5) IterEnd освобождает ссылку снимка, Unit возвращает контейнер — трёхчастная итерация плюс уборка контейнера, без пропусков.

Вторая полная программа: целочисленные ключи и итерация по ключам

Из examples/containers/int_map/main.c, ID сессий от отрицательных до миллионных:

 */

#include <stdio.h>
#include <xrt.h>



/* 稀疏会话状态直接保存在整数键对应的内联值槽中。 */
typedef struct sessionstate {
	unsigned Requests;
	bool Authenticated;
} sessionstate;



int main(void)
{
	xintmap tSessions;
	xintmapiter tIterator;
	sessionstate* pState;
	int64 iSessionId;       /* 借用：迭代时交出的键 */
	bool bNew;

	if ( !xrtIntMapInit(&tSessions, sizeof(sessionstate)) ) {
		return 1;
	}

	


	 */
	pState = (sessionstate*)xrtIntMapGetOrAdd(&tSessions, 1000001, &bNew);
	if ( pState == NULL ) {
		xrtIntMapUnit(&tSessions);
		return 2;
	}
	pState->Requests++;
	pState->Authenticated = true;

	/* 负数键同样合法；新槽 Authenticated 保持零值 false。 */
	pState = (sessionstate*)xrtIntMapGetOrAdd(&tSessions, -9, &bNew);
	if ( pState == NULL ) {
		xrtIntMapUnit(&tSessions);
		return 3;
	}
	pState->Requests = 3;

	


	 */
	if ( !xrtIntMapIterBegin(&tSessions, &tIterator) ) {
		xrtIntMapUnit(&tSessions);
		return 4;
	}
	while ( (pState = (sessionstate*)xrtIntMapIterNext(&tIterator, &iSessionId)) != NULL ) {
		printf(
			"session=%lld requests=%u authenticated=%s\n",
			(long long)iSessionId,
			pState->Requests,
			pState->Authenticated ? "yes" : "no"
		);
	}
	xrtIntMapIterEnd(&tIterator);
	xrtIntMapUnit(&tSessions);
	return 0;
}

Что только что произошло. (1) Ключи -9 и 1000001 разнесены на миллион — целочисленное отображение совершенно нечувствительно к разреженности; это и есть употребление «разреженного массива»: индексы не обязаны быть непрерывными, память расходуется по фактическому числу записей. (2) Вывод идёт в порядке возрастания ключей: -9 перед 1000001, в обратность порядку вставки — в этом сущность разделения труда с порядком вставки xmap; выбирая, сперва спросите «какой порядок обхода мне нужен — порядок бизнеса (вставки) или порядок ключей (сортированный)». (3) Ритм GetOrAdd в точности совпадает с байтовым — выучите один ритм, и вы водите оба семейства.

Форма производительности и ёмкость

Портрет сложности хеш-отображения ровен: операции с одним ключом амортизированно O(1) (вычисление хеша + локализация корзины), итерация O(n) со стабильным порядком. Стратегия ёмкости совпадает с трёхчастным набором главы 14: Reserve растит заранее, избавляя от повторных перехеширований при загрузке, Trim ужимает после перехода в только-чтение. Две практические детали: во-первых, хеширование ключа выполняется внутри контейнера (байтовые ключи идут семейством SipHash, ключ держит сам контейнер) — вызывающему не нужно предварительно считать хеш, вы передаёте сам ключ; во-вторых, итерация xintmap по порядку ключей означает, что «экспорт списка сессий, сортированного по ID», обходится без сортировки — на логарифмических объёмах данных эта экономия нередко весит больше самих поисков. Поместите оба семейства в таблицу выбора главы 23: локация по ключу по плечу обоим; нужен порядок вставки — xmap, нужен порядок ключей и предельная скорость — xintmap.

От образцов к инженерии: три хозяина отображения

Где живёт дескриптор отображения, таков его роль. Временная статистика внутри функции: дескриптор на стеке + Unit в конце — одношаговые задачи вроде подсчёта слов получают двухстрочный жизненный цикл. Таблицы долгой жизни: висят на объекте сервиса — Init при старте, Unit при остановке; таблицы маршрутов и сессий — эта форма: они живут сквозь запросы, и дисциплина итерации (три части, запрет вставок-удалений) должна пониматься под внешней синхронизацией глав конкурентности (том 6). Слоты со указателями: объявите тип значения sizeof(ptr) и кладите в слот указатель на объект или значение дескриптора slot_map главы 17 — в составной структуре «отображение локализует, дескриптор достаёт» отображение отвечает только за прыжок «ключ → дескриптор», сами объекты живут в пуле или slot_map. Три формы покрывают подавляющее большинство инженерных употреблений; таблица соединений главы 67 — третья форма в конкурентном масштабе.

18.4契约

• Семантика GetOrAdd: при наличии возвращается имеющийся слот; при отсутствии вставляется нуль-инициализированный слот и возвращается; выходной параметр bNew различает оба случая.
• Значения инлайн: значения живут в слотах, один Unit возвращает всё; при типе значения ptr владение объектом остаётся у вызывающего.
• Три части итерации: Begin/Next/End, без пропусков; на время итерации запрет вставок-удалений; представление ключа и указатель значения действуют до конца итерации.
• Обещание порядка: xmap — порядок вставки, xintmap — возрастание ключей; вывод воспроизводим точно и годится в тестовые утверждения.
• Двоично-безопасные ключи: байтовые ключи могут содержать вложенные нули; длина — по представлению, не по нуль-терминатору.
• Формы хозяина: временная статистика (дескриптор на стеке), долгоживущие таблицы (на объекте сервиса), ключ-к-дескриптору (значения держат ptr) — у каждой формы своя дисциплина уборки.

Частый вопрос: почему нет «потокобезопасного отображения»

Ни один контейнер тома 3 не потокобезопасен — это не недосмотр, а слоистое решение. Блокировка внутри контейнера означает, что каждый GetOrAdd проходит через замок; однопоточная программа платит за синхронизацию впустую. А правильная гранулярность многопоточной программы обычно не в одиночной контейнерной операции — «найти + решить + записать» нужна внешняя согласованность, которую контейнерный замок не гарантирует. Поэтому XRT отдаёт синхронизацию примитивам тома 6: читающих много — оберните всю таблицу rwlock, межпоточную передачу — в канал, подлинную конкурентность — осколками (по отображению на поток, периодические слияния). Таблица выбора главы 23 ещё раз напомнит об этом в колонке «потоки» — выбирайте контейнер без мыслей о конкурентности, пишите конкурентность без надежд на контейнер.

Типичные ошибки

routestat* pSaved = NULL;
xbytesview KeySaved;
xrtMapIterBegin(&tRoutes, &tIterator);
while ( (pStat = xrtMapIterNext(&tIterator, &Path)) != NULL ) {
	pSaved = pStat;      /* сохранение указателя итерационного периода */
	KeySaved = Path;
}
xrtMapIterEnd(&tIterator);
pSaved->Requests++;      /* итерация закончена - срок указателя тоже */

xrtMapIterBegin(&tRoutes, &tIterator);
while ( (pStat = xrtMapIterNext(&tIterator, &Path)) != NULL ) {
	Process(&Path, pStat);   /* использовать и выбрасывать внутри итерации */
}
xrtMapIterEnd(&tIterator);
/* для долгого хранения: на итерации копируйте ключи/значения в массив, обрабатывайте массив после */

xrtMapIterBegin(&tRoutes, &tIterator);
while ( (pStat = xrtMapIterNext(&tIterator, &Path)) != NULL ) {
	if ( pStat->Requests == 0 ) {
		xrtMapRemove(&tRoutes, Path);   /* удаление из отображения посреди итерации */
	}
}

xarray tDead;
xrtArrayInit(&tDead, sizeof(xbytesview));
xrtMapIterBegin(&tRoutes, &tIterator);
while ( (pStat = xrtMapIterNext(&tIterator, &Path)) != NULL ) {
	if ( pStat->Requests == 0 ) {
		xrtArrayPush(&tDead, &Path);    /* сперва собрать ключи (память-источник ключей обязана жить до конца удалений) */
	}
}
xrtMapIterEnd(&tIterator);
for ( size_t i = 0; i < tDead.Count; i++ ) {
	xrtMapRemove(&tRoutes, *(xbytesview*)xrtArrayGet(&tDead, i));
}
xrtArrayUnit(&tDead);

Практические задания

Итоги