Реализация HashMap: --- хэш-код - PullRequest
Новая
       10

Реализация HashMap: --- хэш-код

1 голос
/ 12 февраля 2012 
template<class KEY, class VALUE>
unsigned int HashMap<KEY, VALUE>::hashCode(KEY key)
{
    unsigned int k = key & 0xffffffff; //error: no match for ‘operator&’ in ‘key & 4294967295u’
    k += ~(k<<9);
    k ^= (k>>14);
    k += (k<<4);
    k ^= (k>>10);
    return k;
};

Как видите, я пытаюсь реализовать hashCode, манипулируя битами в объекте.Очевидно, что битовые операторы нелегко применить к пользовательским объектам.

Я хочу взять некоторые биты объекта любого типа, учитывая его местоположение в памяти, и манипулировать битами, как я хочу.Затем я буду интерпретировать биты как int и применять к ним побитовые операторы.

Звучит ли это как хорошая идея?И как я могу получить биты из объектов ЛЮБОГО ТИПА в заданной области памяти?

Большое спасибо!

Ответы [ 3 ]

2 голосов
/ 12 февраля 2012

Нет, это ужасная идея, потому что она не соответствует определению типа равенства.Тип может быть определен так, чтобы несколько разных представлений можно было считать равными (например, std::string, который содержит пару указателей и ничего больше. Две строки могут быть равны (обе содержат "hello world", но имеют разные указатели, потому чтоони указывают на разные блоки памяти, и поэтому ваша реализация хеш-ключа вернет разный хеш-ключ для двух одинаковых объектов.не сможет найти объекты, которые они положили в таблицу.

1 голос
/ 12 февраля 2012

Это не очень хорошая идея.

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

Существуют способы реализации простого отражения в C ++ с использованием макросов, которые могутВы действительно хотите здесь (то есть найти всех членов и типы структуры), но я не знаю ни одного хорошего с открытым исходным кодом из головы.У нас есть одна в моей кодовой базе на работе (у которой есть шаблон, который делает именно то, что вы хотите, то есть создаете хеш-функцию для произвольной структуры), но я не могу поделиться им.

0 голосов
/ 12 февраля 2012

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

То, что вы здесь говорите, это то, что вы хотите манипулировать базовым битовым представлением структуры данных в виде последовательности битов.

Этот подход может работать только с примитивными типами, например, целыми числами, символами и т. Д.

В вашем примере KEY может быть чем угодно, а базовые биты равны размеру структуры, поэтому вашand операция не очень помогает.

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

В любом случае, на мой взгляд, код (даже если вы решили пойти по этому пути и какой-нибудь друг-эксперт по SO может помочь вам) будет слишком сложным.

Наилучшим подходом будет hash каждый из членов объекта. Этот подход, по крайней мере, используется в Java и прост в реализации

...