Zastanawiałem się, jak najlepiej podejść do zadania decydowania o operacjach, które funkcja mieszająca powinna wykonać na danych wejściowych, oczywiście w oparciu o prawdopodobny format wejściowy.

Czy są jakieś zasady (książki), których jeszcze nie znalazłem?

Jak mogę oszacować koszt takiej funkcji?

Czy mogę jakoś przewidzieć prawdopodobieństwo kolizji, znając zestaw znaków używany do danych wejściowych?

Z góry dziękuję za jedzenie za moją myśl. :)

1
Gung Foo 28 wrzesień 2012, 03:15

2 odpowiedzi

Najlepsza odpowiedź

...

Cześć Gung Foo,

Po prostu spójrz na starcie CRC32 vs FNV1A_Yorikke na:

http://www.sanmayce.com/Fastest_Hash/index.html#KT_torture3

Jak mogę oszacować koszt takiej funkcji?

W skrócie: ciężkie i wszechstronne klucze/obciążenia. Ogólnie rzecz biorąc, funkcja skrótu (przeglądania tabeli) ma trzy główne aspekty do rozważenia:

  • Zderzenia zarówno dyspersji, jak i maksymalnej głębokości szczeliny najgrubszej;

  • Czas rozgrzewania, tj. koszt początkowy/narzut;

  • Prędkość liniowa.

1
Georgi 22 październik 2012, 20:14

Ogólna zasada dotycząca generowania hashcode polega na tym, aby wynikowa wartość była jak najbardziej unikalna. Dwie rzeczy, które są pożądane w hashcode/funkcji haszującej

  1. Hashcode powinien być jak najbardziej unikalny (i jak najmniejszy). Biorąc to pod uwagę, (w idealnym świecie) użycie elementu danych, którego typ danych zajmuje niewiele miejsca i który można zagwarantować, że będzie unikalny dla dowolnej instancji wartości, jest szybkim i skutecznym sposobem na uzyskanie kodu skrótu. Czasami jednak nie jest to bezpieczna praktyka.
  2. Funkcja skrótu powinna być doskonała tj. powinna być w stanie wygenerować unikalną wartość, wszystkie wartości są generowane w ramach mały zasięg.
0
kolossus 28 wrzesień 2012, 18:59