tablice haszujące

[piotrek20008]

Mam 4 zdania o tablicach haszujących i mam wskazać, które są prawdziwe.

1. Różnym kluczom odpowiadają zawsze różne wartości funkcji haszującej.

2. Jeżeli 2 klucze mają różne wartości funkcji haszującej, to nie mogą być równe.

3. Jeżeli próbujemy umieścić w tablicy haszującej klucz dla którego wartość haszująca jest identyczna z innym kluczem, już znajdującym się w tablicy, to może ale nie musi dojść do kolizji

4 Prawdopodobieństwo kolizji zwiększa się wraz ze wzrostem stopnia zapełnienia tablicy haszującej

Według mnie prawidłowe to: 3 i 4 ale nie wiem

[Fingon]

Wydaje mi się, że 2,3,4 są prawidłowe.

[paladin]

3. zależy od implementacji tablicy i definicji "kolizji".

[Crizz]

Oczywiście, że 2. również jest prawidłowe, w przeciwnym wypadku funkcja haszująca nie byłaby funkcją (i przy okazji byłaby bezużyteczna, bo jednoznaczność jest głównym wymogiem dla takiej funkcji).