Как вы говорите (и как предложил комментатор), проще всего сделать массив со статическим размером, равным максимальному значению символьного типа данных:
#include <limits.h>
void * mapping[1u << CHAR_BIT];
Предполагая 64-битные указатели и 8-битные char
с, это заняло бы 8 * 256 = 2048 байт памяти для всей карты (исключая, конечно, "пользовательские данные", которые вы храните).Для программы, работающей в 64-битной системе, 2 КБ памяти тривиальны, и простота реализации и скорость, которую вы получаете от этого, на мой взгляд, должны сбалансировать потраченную впустую память.
Самая простая вещьчтобы сделать, если вы все еще хотите ограничить «физический» размер массива, нужно было бы хешировать один символ, но затем вам нужно начать разбираться с коллизиями хешей, что сразу усложняет задачу.
Вы можете сделатьчто-то вроде:
struct ValueChain
{
struct ValueChain *next;
void *value;
char key;
}
#define MAP_SIZE 127 /* This should be prime. */
struct ValueChain* mapping[MAP_SIZE];
Здесь мы вдвое уменьшили размер массива указателей, но стоимость каждого значения увеличилась.Также вам понадобятся динамические выделения при вставке сопоставленных значений.
Вы можете дополнительно сжать его, выполнив, например,
#define MAP_SIZE 31
struct ValueChain mapping[MAP_SIZE];
Здесь каждое значение в массиве является полным ValueChain
"заголовок списка ", а не просто указатель на один.На 64-битной машине это, вероятно, использовало бы около 558 байтов для массива mapping
, но вам не нужно было бы делать какие-либо динамические выделения, пока вы не обнаружите коллизию.
Хэширование для них может быть простоconst char key = myChar % MAP_SIZE;
в первом приближении, я думаю.