LINUX.ORG.RU

C. Уникальный хэш от двух указателей без коллизий.

 , ,


0

1

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

★★★★

Берешь памяти sizeof(pointer)*2, записываешь туда последовательно два адреса и получаешься стопроцентно уникальный хеш для двух указателей.

staseg ★★★★★ ()
Ответ на: комментарий от staseg

памяти sizeof(pointer)*2, записываешь туда последовательно два адреса и получаешься стопроцентно уникальный хеш

Да. Мне это сейчас и самому в голову пришло.. Хотя наверное придётся вместо указателей брать какие-нить там ассоциированные short int16 id, чтобы впихнуть их в обычный инт...

Bad_ptr ★★★★ ()

для уточнения тз :)

поинтеры какого размера 32? 64?

ожидаемое число различных указателей в самой программе?

qulinxao ★★☆ ()
Ответ на: комментарий от Bad_ptr

Можно поробовать выкинуть лишнюю инфу из указателей.

  • данные выравниваются по слову (или двойному) - можно выкинуть младший бит (два).
  • сами указатели указывают на область стека или кучи - можно вычитать базовый адрес;
  • начало области процесса указывает на ядро - тоже можно учесть.
vahtu ()
Ответ на: комментарий от qulinxao

поинтеры какого размера 32? 64? ожидаемое число различных указателей в самой программе?

Просто чё-то сидел и ничего в голову не приходило.
Да, вообще всегда хочется универсальности, чтобы можно было и любого размера и любого количества...
Хотя согласен, придётся пойти всё же более практичным путём. Указатели там на некие объекты... В общем придётся допустить, что там не будет миллионов миллиардов объектов(что действительно вряд ли) и сделать для них соответствующего размера id..

Bad_ptr ★★★★ ()
Ответ на: комментарий от Bad_ptr

С учётом того, что ты уже сверху написал, очевидно, что образования и знаний у тебя совершенно не достаточно, для того, чтобы пойти практичным путём. Лучше бы тебе написать, чего ты этим хочешь добиться.

aedeph_ ★★ ()
Ответ на: комментарий от vahtu

А ещё можно вычитать указатели и искать хэш ужет от одного (меньшего) и их разности - врядли она большой будет.

vahtu ()
Ответ на: комментарий от aedeph_

Тонко, тонко ;)

А производительность Вашего решения и моего не сравнивали:

$ cat a.c
#define MEGA_HASH_KEY_SIZE (sizeof(void *) * 2 + 1)

void mega_hash(char *buf, unsigned long bufsz, const void * const p1, const void * const p2)
{
	snprintf(buf, bufsz, "%x%x", p1, p2);
}

main(int argc, char **argv)
{
	void *ptr1 = 0xff;
	void *ptr2 = 0xff00;
	char buf[MEGA_HASH_KEY_SIZE] = {0};
	int i, nb_repeat = atoi(argv[1]);
	for (i = 0; i < nb_repeat; ++i)
		mega_hash(buf, sizeof(buf), ptr1, ptr2);
	printf("%s\n", buf);
}
$ gcc a.c -o megahash
a.c: In function ‘mega_hash’:
a.c:5: warning: incompatible implicit declaration of built-in function ‘snprintf’
a.c:5: warning: format ‘%x’ expects type ‘unsigned int’, but argument 4 has type ‘const void * const’
a.c:5: warning: format ‘%x’ expects type ‘unsigned int’, but argument 5 has type ‘const void * const’
a.c: In function ‘main’:
a.c:10: warning: initialization makes pointer from integer without a cast
a.c:11: warning: initialization makes pointer from integer without a cast
a.c:16: warning: incompatible implicit declaration of built-in function ‘printf’
$ time ./megahash 1000000
ffff00

real	0m0.165s
user	0m0.162s
sys	0m0.002s
$ time ./megahash 10000000
ffff00

real	0m1.614s
user	0m1.612s
sys	0m0.001s
$
bk_ ★★ ()

Как предположение:

uintptr_t foo(void *p1, void *p2) {
    if (POINTER_ON_HEAP(p1) && POINTER_ON_HEAP(p2))
        return ((uintptr_t)p1 - HEAP_START_ADDRESS) + ((uintptr_t)p2 - HEAP_START_ADDRESS);
    else if (POINTER_ON_STACK(p1) && POINTER_ON_STACK(p2))
        return ((uintptr_t)p1 - STACK_START_ADDRESS) + ((uintptr_t)p2 - STACK_START_ADDRESS);
    else ...
}
quasimoto ★★★★ ()
Ответ на: комментарий от Eddy_Em

Как более кроссплатформенный вариант - да. Но конкретного ТЗ нет.

bk_ ★★ ()

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

В твоем случае можно сделать так:

  • Применить по одной итерации xorshift к каждому указателю - получим 2 псевдослучайных числа размерности указателя.
  • Скомбинировать их, например, с помощью XOR. Если надо, еще поXORить с SEED-значением, чтобы избавиться от повторяемости результатов.
  • Отбросить ненужные разряды результата. Например, если нужен 8-битный хэш, взять младшие 8 бит.

Результат будет иметь близкое к идеальному распределение коллизий.

Но тебе вряд ли нужно именно это. По крайней мере, мне сложно представить подобную ситуацию за исключением экзотических задач (типа реализации хешей в стиле JS для своего языка программирования).

f0e ()
Ответ на: комментарий от f0e

Ну, по сути, автору и не нужно хеширование, потому что оно рассчитано на строки произвольной длины, а когда имеем дело всегда с двумя значениями заранее известной величины, то их конкатенация - вполне подходящая для сравнения пар операция.

cdshines ★★★★ ()
Ответ на: комментарий от Bad_ptr

дык, ведь xor, если порядок произвольный

int
hash(void *a, void *b)
{
        return (int)a ^ (int)b;
}

от коллизий не спасает, но зато быстро ;)

beastie ★★★★★ ()
Ответ на: комментарий от bk_

Википедия утверждает следующее:

A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length.

При желании можно найти и более авторитетные источники. Но проще использовать здравый смысл и немного подумать своей головой.

f0e ()
Ответ на: комментарий от Eddy_Em

Смысл в том, чтобы сделать оба указателя небольшими, ориентируясь на область где они находятся (если есть таковая и она относительно не велика, для двух указателей со стека и из кучи не подойдёт). Пусть P = {min .. max}; p_1, p_2 \in P тогда можно получить уникальное (p_1 - min) * (max - min + 1) + (p_2 - min), которое будет иметь минимум = 0 и максимум = (max - min) * (max - min + 2) ~ размер области ^ 2. А если ещё p_1 - min и p_2 - min помещаются в какой-нибудь меньший тип T можно составить из них слово - (T)(p_1 - min) << sizeof(T) | (T)(p_2 - min).

quasimoto ★★★★ ()
Ответ на: комментарий от bk_

Случай «=» называется перестановкой, а не хэш-функцией. И в качестве хэш-функции непригоден. На практике мощность множества аргументов >> мощности множества хэшей.

f0e ()

ты сначала определи - какой размер должен получиться хеш
если размер неважен - то 2 поинтера в 64 битах - это 128 битное целое вообще без коллизий

а вот если тебе нужно 8 битный хеш - иль 16 битный то другое дело
имхо ничего более простого чем xor байтов и ненайти

ae1234 ★★ ()
Ответ на: комментарий от cdshines

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

f0e ()
Ответ на: комментарий от quasimoto

Смысл в том, чтобы сделать оба указателя небольшими

Ещё зависит от объектов, на которые они указывают. Я предлагал бит отрезать, но если у него структуры, допустим, 256 байт - можно смело байт от каждого оттяпать - коллизий не будет.

vahtu ()

Ну если хеш можно больше, тогда конкатенируй два числа. Если нельзя больше, то без коллизий не обойтись, потому просто бери xor

vertexua ★★★★☆ ()

Прогони каждый через итерацию линейного конгруэнтного метода, результаты сложи.

anonymous ()
Ответ на: комментарий от f0e

Но тогда и вопрос задавать незачем - ответ очевиден же.

так и есть. :) просто заклинило меня...

Bad_ptr ★★★★ ()
Ответ на: комментарий от vahtu

Если посмотреть на /proc/${pid}/maps среднестатистического приложения - стек занимает сотни килобайт, куча - десятки и сотни мегабайт, то есть адреса на самом деле небольшие, если все указатели известные (эти в куче, эти на стеке), то можно сочинить хорошую функцию используя всякие битовые сдвиги и or-ы.

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Я об этом же, просто часть информации в указателях не нужна. В пределе можно запихнуть этот хэш хоть в 32 бита без коллизий.

vahtu ()
Ответ на: комментарий от quasimoto

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

P. S. Я прям вижу, как ТС идёт делать конкатенацию, посмеиваясь над своей несообразительностью. И сходу выделяет 2^(2*sizeof(void*)) памяти под хеш таблицу.

quiet_readonly ★★★★ ()
Ответ на: комментарий от vahtu

Вот примерно так, с учётом 2-байтного alignment:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <assert.h>

#define BITS_IN_BYTE 8

#define HEAP_START 0x0
#define HEAP_END 0xfffffffe

/*
 * 64 bit, sizeof(void*) == sizeof(uint64_t)
 */
typedef uint32_t uinthalfptr_t;
#define UINTHALF_MAX UINT32_MAX

#define ALIGNED 4

static inline uintptr_t foo(void *a, void *b)
{
    uintptr_t x = (uintptr_t)a, y = (uintptr_t)b;

    if (x >= HEAP_END || y >= HEAP_END)
        return 0;

    return (uintptr_t)((uinthalfptr_t)(x - HEAP_START) >> ALIGNED)
             << BITS_IN_BYTE * sizeof(uinthalfptr_t)
           | (uintptr_t)((uinthalfptr_t)(y - HEAP_START) >> ALIGNED);
}

int main(void)
{
    assert(HEAP_END - HEAP_START < UINTHALF_MAX);

    char *xs = malloc(1);
    int *ys = malloc(7);

    printf("%p %p %p\n", xs, (void*)ys, (void*)foo(xs, ys));

    sleep(1000);
}
$ ./a.out
0x1b3a010 0x1b3a030 0x1b3a01001b3a03
quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Точнее вот так

    if (x < HEAP_START || y < HEAP_START || x >= HEAP_END || y >= HEAP_END)
        return 0;

ну и выставить, например

#define HEAP_START 0x2000000
$ ./dg
0x213c010 0x213c030 0x13c0100013c03

0x2000000 отнялось, но нужно настоящий адрес где-то брать (из /proc/.../maps?).

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Ну да. Тока HEAP_START явно не 0 - есть ведь первый гигабайт (или скока там) для области ядра. Посмотри на первый указатель. Кстати можно специально выделить байтик и принять его за начало кучи, что бы с константами не возиться.

И ещё: получившуюся старшую часть нужно смещать на ALIGNED*2, а то от незначащих бит избавился, а потом назад смещаешь и там нули :).

vahtu ()
Ответ на: комментарий от vahtu

В смысле вычесть из BITS_IN_BYTE * sizeof(uinthalfptr_t) ещё раз ALIGNED.

vahtu ()
Ответ на: комментарий от vahtu

Тока HEAP_START явно не 0 - есть ведь первый гигабайт (или скока там) для области ядра.

Он рандомизируется, я не знаю откуда его достать, кроме как из /proc.

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

В принципе да. И со стеком тоже, но тут мы сильно завязываемся на «API», которое nonsence :)

получившуюся старшую часть нужно смещать на ALIGNED*2, а то от незначащих бит избавился, а потом назад смещаешь и там нули

Да, лишний бит остаётся, нужно так:

    printf("%x\n", x);
    printf("%x\n", x >> 4);
    printf("%lx\n", (uint64_t)(x >> 4) << (32 - 4));
    printf("%x\n", y);
    printf("%x\n", y >> 4);
    printf("%lx\n", (uint64_t)(x >> 4) << (32 - 4) | y >> 4);
fffffff0
fffffff
fffffff0000000
aaaaaaa0
aaaaaaa
fffffffaaaaaaa

и тогда, по идее, разница между HEAP_END и HEAP_START может быть больше чем 32 бита - 34.

quasimoto ★★★★ ()

Хэш крайне неэкономичен к объему памяти (чтобы минимизировать коллизии, количество слотов в хэш-таблице должно быть много больше чем предполагаемое количество элементов), и ещё нужно разбираться с коллизиями. Тебе точно это нужно?

no-dashi ★★★★★ ()

посоветуйте какую-нибудь сказочную хэшфункцию

... э-э-э ... XOR?

Macil ★★★★★ ()

кажется без колизий не получится, но если есть какой-нибудь приемлемый диапазон, можешь построить perfect hash

OxiD ★★★★ ()

1. всякую пару указателей u,v заменяй на min(u,v),max(u,v)-min(u,v) так выигрывается чуть меньше бита.

. остальное специфично насколько крупные/мелькие обьекты , сколько вообще обьектов и т.п.

qulinxao ★★☆ ()

Оч хорошая хеш crc32 - там нет коллизий

Она ни когда не вернет одинаковое значения для для каких либо 2х разных числел, но она 32х битная и не очень быстрая

uint32 * crc32_table = NULL;

int crc32_init( uint32 polygen ) { uint bit, c = 256; uint32 crc; if( polygen == 0 ) polygen = 0xedb88320;

if( ( crc32_table = cs_malloc( 256 * sizeof( * crc32_table ) ) ) == NULL ) return 1;

while( c-- ) { crc = c; bit = 8; while( bit-- ) if( crc & 1 ) crc = crc >> 1 ^ polygen; else crc = crc >> 1; crc32_table[ c ] = crc; } return 0; }

void crc32_free() { if( crc32_table == NULL ) return; cs_free( crc32_table ); crc32_table = NULL; }

uint32_t crc32_calc( uint32 crc, const void * buffer, size_t size ) { if( crc32_table == NULL ) crc32_init( 0 ); crc = ~crc; while( size-- ) crc = crc32_table[ * ( uint8 * ) buffer++ ^ ( crc & 255 ) ] ^ crc >> 8; return ~crc; }

uint32_t hash( uint32_t x ) { static char buffer[] = «HASH»; return crc32_calc( x, buffer, sizeof( buffer ) - 1 ); }

peter_t ()
Ответ на: Оч хорошая хеш crc32 - там нет коллизий от peter_t

> Оч хорошая хеш crc32 - там нет коллизий
Любая хеш функция будет иметь коллизии, потому что множество значений функции меньше множества значений аргумента (за исключением случая когда оба множества состоят из одинакового числа элементов).

> ни когда
> каких либо
Хотя, кому я объясняю...

Kadi ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.