структуры данных — функция хеширования для переполнения стека карт

Question

структуры данных — функция хеширования для переполнения стека карт

Я пытаюсь определить хэш-функцию, которая принимает входные данные (i, k) и определяет уникальное решение.

Возможные входные данные для (i, k) находятся в диапазоне от 0 до 100. Рассмотрим каждый (i, k) как позицию узла в триномиальном дереве.

Ex: (0, 0) can diverge to (1, 1) (1, 0) (1, -1).
(1, 1) can diverge to (2, 2) (2, 1) (2, 0).

Образец приведен здесь:

http://www.google.com/imgres?imgurl=http://sfb649.wiwi.hu-berlin.de/fedc_homepage/xplore/tutorials/stfhtmlimg1156.gif&imgrefurl=http://sfb649.wiwi.hu-berlin.de/fedc_homepage/xplore/tutorials/stfhtmlnode41.html&h=413&w=416&sz=4&tbnid=OegDZu-yeVitZM:&tbnh=90&tbnw=91&zoom=1&usg=__9uQWDNYNLV14YioWWbrqPgfa3DQ=&docid=2hhitNyRWjI_DM&hl=en&sa=X&ei=xAfFUIbyG8nzyAHv2YDICg&ved=0CDsQ9QEwAQ

Я использую карту

map <double, double> hash_table

Мне нужно, чтобы значение ключа определялось из пар (i, k) для хеширования к значению для этого (i, k)

До сих пор я мог только придумать линейные функции, такие как:
двойная Hash_function (int i, int k)

{
//double val = pow(i, k) + i;
//return (val % 4294967296);
return (i*3.1415 + k*i*9.12341);
}

Однако я не могу определить уникальный ключ с определенным (i, k). Какие функции я могу использовать, чтобы помочь мне сделать это?

0

c++data-structures hash hashmap hashtable

Решение

Другие решения

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

1

Если я & k 0-100, чем ваш ключ может быть простым коротким (даже со знаком) и уникально генерируется с чем-то вроде short key = i | k << 8,

0

Источник

Accepted Answer

Математически говоря, вы ищете биекция. Это не хеш-функция в смысле информатики, поскольку ожидается, что хеш-функции иногда будут вызывать коллизии (если это не идеальная хеш-функция).

Что вы пометили hash_table это не хеш-таблица std::map это другая структура данных, называемая упорядоченной картой, и она может использовать любой тип ключа, для которого оператор меньше чем < обеспечивает строгий слабый порядок. Вы можете, на самом деле, использовать std::pair от utility заголовок:

std::map<std::pair<int, int>, double> table;

Чтобы вставить в таблицу, вы должны использовать:

table[std::make_pair(i, j)] = value;

2