Вызов функции c_str () против const char * в хэш-функции

Question

Я смотрел на хэш-функции в stackoverflow, когда нашел одну, которая была довольно интересной.Это включает приведение const char * к size_t * и затем разыменование size_t.Это затем немного сдвигается с определенной точностью.Это работает для const char *, каждый раз получая одно и то же значение.Однако, когда я использую фактический строковый тип и вместо этого вызываю c_str (), два полученных значения не совпадают.Кроме того, при каждом запуске кода строка создает разные значения при каждом запуске.Кто-нибудь знает, почему это происходит?

const string l = "BA";
const char* k = l.c_str();
const char* p = "BA";
cout << k << " " << *((size_t*)k) << endl;
cout << p << " " << *((size_t*)p) << endl;

Прогон 1:

BA 140736766951746
BA 7162260525311607106

Прогон 2:

BA 140736985055554
BA 7162260525311607106

Оригинальный вопрос: Естьхорошая хеш-функция для хеш-таблицы C ++?

Answer 1

Начну с того, что в:

const string l = "BA";
const char* k = l.c_str();
const char* p = "BA";
cout << k << " " << *((size_t*)k) << endl;
cout << p << " " << *((size_t*)p) << endl;

И *((size_t*)k), и *((size_t*)p) вызывают неопределенное поведение .Это так, поскольку в большинстве систем он получает доступ к данным за пределами массива char.Обратите внимание, что sizeof(size_t) > 3 * sizeof(char) для 32- и 64-битной системы, так что *((size_t*)k) обращается как минимум к одному байту за границей.

Во всем примере строковые литералы (в вашей системе) возможно выровнены попо крайней мере sizeof(size_t), с нулевым заполнением (не рассчитывайте на это, но, похоже, так).Это означает, что мусор после строкового литерала "BA" (и терминатор NUL) является символом (ами) NUL.Это согласуется для всех прогонов.

В случае k, который исходит от std::string, вам не так повезло.Строка короткая, поэтому большинство систем будет использовать оптимизация короткой строки .Это означает, что этот буфер char находится в объекте std::string.В вашем случае строка настолько короткая, что остальная ее часть все еще находится в буфере, выделенном для оптимизации короткой строки.Как кажется, оставшаяся часть буфера не инициализируется и содержит ненужные.Хлам остался до вызова функции.В результате, кроме первых 3 байтов BA\0, остальное - случайный мусор.

Вам повезло, что этот случай неопределенного поведения заканчивается дополнительным мусором, а не чем-то более озадачивающим (как всегдавозвращение нуля или вызов не связанных функций).Никогда не полагайтесь на UB.

Answer 2

*((size_t*)k) вызывает неопределенное поведение, нарушая строгое правило алиасинга.Этот код только действителен, если k на самом деле указывает на объект типа size_t.

При неопределенном поведении, странные цифры - это возможный результат (как и все остальное).

---

Полагаю, вы хотели что-то похожее на:

size_t x;
memcpy(&x, k, sizeof x);
cout << k << " " << x << '\n';

Теперь должно быть понятно, в чем проблема.Ваша строка содержит только 3 символа (2 плюс нулевой терминатор), однако вы пытаетесь прочитать более 3 символов, что также приводит к неопределенному поведению.

Answer 3

// Simple null terminated character that is represented in memory as:
//
// ['B', 'A', '\0']
const char* p = "BA";

// From the other side `std::string` isn't so simple
//
// c_str() returns a pointer to some kind of buffer.
//
// ['B', 'A', '\0', ... reserved_memory]
//
const std::string l = "BA";
const char* k = l.c_str();

// Then you do a C-style cast.
//
// (size_t*)k that gives you the address to the beginning of the underlying
// data of the std::string (possibly it will be pointer on the heap or on
// stack depending on the SSO) and after that you dereference it to receive
// the value. BTW it can lead to the undefined behavior because you
// attempt to receive the value for 8 bytes (depending on the size_t size)
// but your actual string may be less than it, e.g. 4 bytes. As a result
// you will receive the garbage.
std::cout << k << " " << *((size_t*)k) << std::endl;

// Two strings created as
//
// const char* foo = "foo";
// const char* bar = "foo";
//
// are stored in the Read only segment of data in your executable. Actually
// two different pointers will point to the same string in this segment. Also
// note the same undefined behavior mentioned earlier.
std::cout << p << " " << *((size_t*)p) << std::endl;