Idealna funkcja mieszania i korzyści

Question

Rozważmy klasę:

public final class MyDate { 
     private int year, month, day; 

     public MyDate(int year, int month, int day) { 
      this.year = year; 
      this.month = month; 
      this.day = day; 
     } 

     //Some stuff 

     @Override 
     public int hashCode() { 
      return ((year << 4) | month) << 5 | day; 
     } 
} 

To doskonała funkcja skrótu, bo w pamięci mamy:

Więc na czerwono, 5 bits sklep dzień (1 do 31), w kolorze żółtym 4 bits przechowywać miesiąc (od 1 do 12), a pozostałe przechowują rok (od 1 do 16777215).

Jaka jest korzyść z doskonałego hashFunction? AFAIK, może zagwarantować dodanie/usunięcie/zawiera w O(1) w HashSet, ale czy mogę uzyskać inne korzyści z posiadania?

Widziałem, że wiele funkcji skrótu używa liczb pierwszych, jaki jest najlepszy sposób na ich zbudowanie (wyobrażam sobie, że stworzenie idealnej funkcji skrótu jest rzadkie/rzadkie)?

---

EDIT:

O liczb pierwszych -> odpowiedział here

Answer 1

Doskonałym funkcja hash gwarantuje, że będziesz miał żadnych kolizji. Jednak aby móc go używać, musisz dokładnie znać zestaw kluczowych wartości, które będą wymagać mieszania, co często nie jest możliwe.

Inne, nie tak doskonałe, ale nadal dobre funkcje skrótu (wraz z mechanizmem rozwiązywania kolizji) nie mają tego wymagania i są bardzo szybkie do obliczenia, więc często są bardziej odpowiednie.

Answer 2

Jak na Juampi jest szybki. Jak szybko? Około O (1). Redis jest doskonałym przykładem ciągłego wyszukiwania czasu w pamięci poprzez tablicę haszującą.

Jeśli nie masz kubka dokładnie jednego elementu na wynikach mieszania, musisz użyć równych wartości, aby porównać każdy element, aby uzyskać wynik O (1 plus z), gdzie z to rozmiar wiadra.

Ale tak bardzo powolne funkcje skrótu z pewnością nie są świetnym pomysłem po.