Mam małe pytanie w związku z wyznaczaniem hashCode dla konkretnych słów dodawanych do słownika.
Jeśli mamy małe, duże litery oraz spacje w słowach (ciąg znaków) to jak zrobić by litery od a do z były interpretowane jako liczby od 1 do 26, od A do Z 27 do 52, a spacja 53?
Próbowałem znaleźć odpowiednia komendę, ale nie widzę takowej.
Ponadto mam problem z samą funkcją mieszającą. Ma ona:
Zamiana słowo key na liczbę naturalną - num,
np.
niech key = ‘cats’,
litery występujące mają następujące kody: c=3, a=1, t=20, s=19
Dla słowa ‘cats’ wyznacz liczbę num = 3*27^3+1*27^2+20*27^1+19*27^0
(mnożymy kody poszczególnych znaków przez odpowiednią potęgę 27,
a następnie dodajemy wyniki mnożenia)
Oblicz
h(key) = num % m ;
przy czym: m = liczba pierwsza odległa od potęgi dwójki, oraz
m w przybliżeniu 2 * n ,
gdzie: n – jest przewidywaną liczbą przechowanych elementów.
Tak wygląda:
public int hash(String key)
{
int wartosc = 0;
int len = key.length() - 1;
for(int j = 0; j < key.length(); j++ )
{
wartosc += toDig(key.charAt(j)) * Math.pow(53, len);
len--;
}
// 2.
return wartosc;
}
NIe rozumiem jak mam określić m. Rozumiem, że n jest równe ilości przechowywanych elementów, ale nawet wtedy kiedy duplikaty zostają odrzucone? Tzn. mogę ustalić na początku ilość elementów włącznie z duplikatami, ale duplikatów nie zapisuję. Czy wtedy n = wszystkie słowa włącznie z duplikatami?
Tak wygląda funkcja zamieniająca litery na liczby:
private int toDig(char a)
{
int ile = 0;
if(Character.isLowerCase(a))
{
ile = a - ('a' - 1);
} else if(Character.isUpperCase(a)) {
ile = a - ('A' - 27);
} else if(a == ' '){
ile = 53;
}
return ile;
}
Dla ‘a’ nie sypnie się? Zdaje się, że powinno być -(‘a’ +1) i -(‘A’ + 27).
Nie jestem pewny co ty rozumiesz przez duplikat, jeśli ABC, ABC, to takich duplikatów nie liczysz, jeśli natomiast znajdziesz dwa różne słowa będące tym samym to je rehashujesz przykład słowo aa = 1*27^1 + 1*27^0 = 28, słowo B 28*27^0 = 28, przy dodaniu B musisz użyć funkcji rehashującej, żeby trafiło w inne miejsce. n = wszystkie elementy wyłączając duplikaty pierwszego typu, to jest nie dodajemy do słownika 2 razy tego samego słowa, ale dodajemy dwa różne słowa mające ten sam hash.
Witam. Program udało mi się napisać i po wielu testach stwierdzam, że działa. Tworzy on narzuconą przez użytkownika ilość drzew BST i tam przechowuje kolejne słowa. Posiada operacje: Insert, Search, Delete. Mam z nim natomiast inny problem i zarazem pytanie do was: jak usprawnić kod, by działał szybciej? Co można pozamieniać, co usunąć, itd.? Zrezygnowałem z własnej funkcji hashującej na rzecz wbudowanej funkcji hashCode. Program przyjmuje: ilość zestawów, ilość drzew, słowa w ilości narzuconej przez użytkownika (przyjmowanie słów kończy się po wpisaniu znaku “#”), ilość operacji, operacje w formie: INSERT x, SEARCH x, DELETE x.