Szukam dobrej funkcji hash

Thread View: pl.comp.lang.c

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by Borneq Sat, 11 Jun 2016 12:23

#308661

Author: Borneq
Date: Sat, 11 Jun 2016 12:23

19 lines
1382 bytes

Musi być:
- prostsza od CRC
- szybka
- dosyć mało kolizji, różniąca się dla podobnych ciągów
- szybko działająca w kodzie C/C++ a nie assemblera i MMX

Czy może być taka?
uint32_t hashRor(uint8_t *bytes, size_t count)
{
	uint32_t result  = 0xFFFFFFFF;
	if (count > 0)
		for (size_t i = 0; i < count; i++)
			result ^= ((result >> 4) || (result << 28)) ^ (bytes[i] << 24);
	//bo (result >> 4)||(result << 28) = result ror 4
	return result;
}

Niestety C nie ma funkcji ROR więc zamiast jednego ROR potrzeba aż 3 
operacji.

Re: Szukam dobrej funkcji hash

#308662

Author: Borneq
Date: Sat, 11 Jun 2016 12:37

16 lines
1469 bytes

W dniu 11.06.2016 o 14:23, Borneq pisze:
> Musi być:
> - prostsza od CRC
> - szybka
> - dosyć mało kolizji, różniąca się dla podobnych ciągów
> - szybko działająca w kodzie C/C++ a nie assemblera i MMX

Będę korzystał z FNV-1: http://isthe.com/chongo/tech/comp/fnv/
ale mam pytanie: Hasz wymagany do unordered_map ma byc liczbą size_t, 
która ma 32 lub 64 bity. Od tego zależy liczba FNV_prime. Jak 
skompilować warunkowo dla 32 lub 64 bitów lub zależnie od sizeof(size_t)?
To chyba prosto:
	if (sizeof(size_t) != 8)
		printf("4");
	else
		printf("8");

Re: Szukam dobrej funkcji hash

#308663

Author: M.M.
Date: Sat, 11 Jun 2016 16:49

30 lines
2372 bytes

On Saturday, June 11, 2016 at 2:37:48 PM UTC+2, Borneq wrote:
> W dniu 11.06.2016 o 14:23, Borneq pisze:
> > Musi być:
> > - prostsza od CRC
> > - szybka
> > - dosyć mało kolizji, różniąca się dla podobnych ciągów
> > - szybko działająca w kodzie C/C++ a nie assemblera i MMX
> 
> Będę korzystał z FNV-1: http://isthe.com/chongo/tech/comp/fnv/
> ale mam pytanie: Hasz wymagany do unordered_map ma byc liczbą size_t, 
> która ma 32 lub 64 bity. Od tego zależy liczba FNV_prime. Jak 
> skompilować warunkowo dla 32 lub 64 bitów lub zależnie od sizeof(size_t)?
> To chyba prosto:
> 	if (sizeof(size_t) != 8)
> 		printf("4");
> 	else
> 		printf("8");

Co myślicie o takiej? Na pewno jest bardzo szybka:

uint64 keys[256] = {random_values};

uint64 mkHash( unsigned char begin[] , unsigned size ) {
  uint64 hash = 0;
  for( unsigned i=0 ; i<size ; i++ )
    hash ^= keys[ (data[i]+hash) & 0xFF ];
  return hash;
}

Pozdrawiam

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads