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

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

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

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

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

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

(lambda (x y) (cons x y))

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

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

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

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

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

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

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

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

$ 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
$

Лучше их в одно 128-битное слово склеить.

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

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 ...
}

Совсем не уникально: 10+20=11+19=12+18=13+17…

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

#define MEGA_HASH_KEY_SIZE (sizeof(void *) * 2 + 1)

Смысл? Для склеивания 2х указателей нужно всего sizeof(void *) * 2

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

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

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

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

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

Там опечатка: надо домножить еще на два.

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

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

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

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

Конкатенация указателей - это не хэш-функция.

Я не троллю. В каком мане это сказано?

Мощность множества всех хэшей <= мощность ОДЗ

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

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.

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

Смысл в том, чтобы сделать оба указателя небольшими, ориентируясь на область где они находятся (если есть таковая и она относительно не велика, для двух указателей со стека и из кучи не подойдёт). Пусть 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).

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

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

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

Вот у меня на машине sizeof(void*) == 8 и sizeof(int) == 4 :) нужно intptr_t использовать для таких вещей. Ну и 6 ^ 12 == 61 ^ 55.

Хм, я там [ u ] intptr_t написал.

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

sizeof(T)

BITS_IN_BYTE * sizeof(T)

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

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

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

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

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

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

Уверен, что ты мне ответил?

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

А не похоже?

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

Нет.

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

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

Вот примерно так, с учётом 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

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

    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?).

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

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

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

Тока 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.

бит

то есть hex.

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

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

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

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

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

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

Оч хорошая хеш 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 ); }

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

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