duplicate char * in C

Question

Здравствуйте, я пытаюсь создать хэш-функцию в C, чтобы удалить дубликаты из набора строк a.k.a char *. Идея состоит в том, чтобы вернуть хеш-функцию, чтобы быть индексом массива, так что если две строки одинаковы, они указывают на одну и ту же позицию в массиве. Но я застрял в том, как я могу это достичь.

В моем первом подходе я попытался создать массив целых чисел с размером, равным количеству заданных строк, а затем сделать int, возвращаемое функцией хеша, по модулю размера массива, но с тех пор оно не сработало для небольшого числа строк было создано много столкновений.

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

Есть ли идея лучше?

Answer 1

Возможно, вы захотите string interning. Некоторые библиотеки называют их «кварками» (например, Glib) или «атомами» (например, в X11: XInternAtom). См. Также symbols (например, в Lisp или Scheme).

Вы можете хранить все ваши интернированных строки в глобальной хэш-таблице, и имеют некоторую функцию

const char* internized_string(const char*str); 

который дал некоторую строку str возвращает каноническую интернирована строку, которая сравнение равно (с strcmp) к нему. Но два вызова interned_string на одинаковых (но не идентичных) строках будут возвращать один и тот же адрес. Он будет работать, сначала выполнив поиск аналогичной строки в хеш-таблице; если ни один не найден, добавьте новую копию (возможно, используя strdup) в хеш-таблицу и верните ее.

Вы можете использовать hash table, balanced tree (т.е. red black tree или AVL tree и т.д ....) а trie или hash array mapped trie, или любой эффективный container реализовать свой глобальный сбор интернированных строк.

BTW, если вы закодированы в C++11, у вас будет много стандартных containers, предоставляемых стандартной библиотекой C++.

Если вы хотите скопировать код самостоятельно, вы можете использовать хеш-таблицу в качестве массива buckets; обычно вы хотите, чтобы размер массива был простым. Каждое ведро может быть связанным списком или непрерывным массивом указателей на строки. Вы полностью упорядочиваете всю хэш-таблицу, когда она заполняется (например, когда среднее значение, или, возможно, максимальный размер ковшей достигает некоторого порога, например 3 или 8), увеличивая массив ведра до большего размера простого размера. просто больше, чем 3/2 старого (и пополняем новую таблицу из старой). Избегайте collisions (но согласитесь, чтобы некоторые из них).

В C имеется множество бесплатных библиотек программного обеспечения хеш-таблицы; например uthash, klib, tommyds, ulib, libstrhash, glib и др. И т.п ... GIYF. Изучите (по крайней мере, для вдохновения) исходный код некоторых из них и, возможно, используйте его.