Pytanko o HASHOWANIE

Witam

Musze zrobic prosta tablice wskaznikow indeksowana stringami. Czy
ktos zorientowany w temacie moze mi powiedziec czy ma sens cos takiego, ze zamiast przechowywania stringow bede przechowywal hashe?

W tej tablicy bedzie powiedzmy gora 100 elementow i musze to zoptymalizowac glownie pod wzgledem szybkosci (a potem pod wzgledem rozmiarow).

No wiec czy jest szansa, ze znajde jakis algorytm hashowania ktorego wynik bedzie mial powiedzmy 8 znakow i dla okolo 100 stringow (3 do 30 znakow) da mi niepowtarzalne wyniki a przy tym hashowanie bedzie na tyle szybkie, zeby nie stracic tego co zyskam potem na przeszukiwaniu tablicy ?

Myslalem jeszcze zeby zrobic proste indeksowanie polegajace na podzieleniu tych tablicy wzgledem pierwszej litery stringa a wtedy te hashowanie byloby chyba tez przydatne bo wydaje mi sie, ze wtedy powinienem uzyskac lepszy rozklad na poszczegolne litery (w tych zrodlowych stringach moze byc np 80% zaczynajacych sie na jedna litere)

Czy ktos swiatly w tych dziedzinach moze mi pomoc ?

Zdaje mi się, że na 100 elementów to hashowanie jest kompletnie nie potrzebne

Czyli chcesz mieć tablicę asosjacyjną z tego co zrozumiałem. Samo haszowanie to raczej zły pomysł, chyba że dysponujesz nieograniczoną pamięcia w kompie ;-) Będą kolizje bo być muszą. Chcesz mieć długość hasza 8, co przy założeniu, że używasz tylko liter a-z daje 26^{8 możliwych wartości hasza, natomiast przestrzeń wszystkich możliwych napisów (długośc 3-30, alfabet a-z) ma wielkość 26}3 + ... 26^{30, co jest dużo większe od 26}8. Stąd kolizje. Możesz mieć tablicę np. 1071, drzew czerwono-czarnych i na podstawie hasza wrzucać słowo do odpowiedniego drzewa. Albo po prostu zwykła listę słów (zależy jak dużo będziesz trzymał par <slowo,obiekt>).

pzdr,

y.

Hmm.. tak dokladnie chodzi mi o tablice asocjacyjna

Chce to do bolu zoptymalizowac pod wzgledem szybkosci i te hashe to byl taki wstepny pomysl. Myslalem, ze dzieki temu uzyskam lepszy rozklad tych stringow na poszczegolne litery i beda mogl zrobic te indeksowanie po pierwszej literze...

A tak w ogole to wcale te hashe nie musialyby skladac sie z samych liter a przy 8 znakach o wartosciach 0-255 mozliwosci jest znacznie wiecej.

No i co ma hashowanie do ilosci pamieci? Te algorytmy maja takie wymagania pamieciowe ? Nie rozumiem tego.

O tych drzwkach poczytam ale juz mam wrazenie, ze to wszystko faktycznie bedzie armata na wrobla bo jak juz napisalem rekordow bedzie moze 100 (powiedzmy miedzy 30 a 300) ale przeszukiwan bardzo duzo i dlatego musze to jakos przyspieszyc

To co, że 0-255. Liczba różnych wartości hasza wyrażałaby się liczbą o 20 cyfrach, zaś samo 26^30 ma 43 cyfry, więc byłyby kolizje ;) Poza tym robienie ze stringa hasza będącego znowu stringiem jest bez sensu, bo tylko przekształcasz dane wejściowe i masz ten sam problem, czyli umieszczenia tak pohaszowanych stringów w tablicy. Lepiej wybrać sobie funkcję zwracającą integer modulo pewna stała p (niektórzy zalecają wybrać p nieparzyste, pierwsze) i mieć tablicę p list,drzew czerwono-czarnych, tudzież innych struktur danych (pozwalających na szybkie operacje insert, search, delete). Jak będziesz robił te swoją funkcję haszującą to zwróć uwagę czy równomiernie rozkłada dane, czyli co się będzie działo dla np. aaa, aaaa, aaaaa itd.

p.s.
pisząc o tej duuużej pamięci miałem na myśli to, że przy ustalonym alfabecie można słowu przypisać odpowiedni numer (być może bardzo duży, większy niż liczba atomów w naszym wszechświecie :P) i to w sposób jednoznaczny

pzdr,

y.

[code]To co, że 0-255. Liczba różnych wartości hasza wyrażałaby się liczbą o 20 cyfrach, zaś samo 26^30 ma 43 cyfry, więc byłyby kolizje ;) [/code]

A gdyby byl odwrotny przypadek to na 100% NIGDY nie wystapi cos takiego? Wiem, ze jest mozliwosc powtorzenia sie, zastanawiam sie tylko jakie to mniej wiecej bedzie prawdopodobnienstwo i jezeli niezbyt duze to jestem w stanie to jakos przebolec.

[code]Poza tym robienie ze stringa hasza będącego znowu stringiem jest bez sensu, bo tylko przekształcasz dane wejściowe i masz ten sam problem, czyli umieszczenia tak pohaszowanych stringów w tablicy.[/code]

Umieszczenie ich w tablicy to nie problem. Problemem jest to, zeby stringi byly jak najkrotsze.

[code]Lepiej wybrać sobie funkcję zwracającą integer modulo pewna stała p (niektórzy zalecają wybrać p nieparzyste, pierwsze) i mieć tablicę p list,drzew czerwono-czarnych, tudzież innych struktur danych (pozwalających na szybkie operacje insert, search, delete).[/code]

Kurcze widze, ze brakuje mi podstaw bo za cholere nic nie rozumiem.
Po co mi integer modulo p? Czemu akurat takie cos a nie inne ?

[code]A gdyby byl odwrotny przypadek to na 100% NIGDY nie wystapi cos takiego? Wiem, ze jest mozliwosc powtorzenia sie, zastanawiam sie tylko jakie to mniej wiecej bedzie prawdopodobnienstwo i jezeli niezbyt duze to jestem w stanie to jakos przebolec.[/code]

Jeśli funkcja haszująca dobrze miesza to losowe słowo może wpaść z jednakowym prawdopodobieństwem do jednej z szufladek. Przykład: Funkcja haszująca zwraca wartości {0,1,...,9}, losujesz sobie jakieś słowo i szansa, że wpadnie ono do 5-tej szufladki wynosi 1/10 (dla pozostałych szufladek również 1/10). Ogólnie mając p szufladek, dobrze mieszająca funkcję i wrzucając n obiektów dostajesz średnio w każdej szufladce n/p obiektów. Odwrotny przypadek nie gwarantuje braku kolizji (to zależy od wybranej funkcji). Masz x argumentów (różnych słów) i y różnych wartości jakie może przyjmować funkcja haszująca (x<y, liczba różnych funkcji f: y=f(x) wynosi y^x, czyli może być ich sporo ;) No i na pewno istnieje taka funkcja, która różnym x-om przypisuje różne y-reki. y-reków jest więcej dlatego każdy x dostanie swojego y-reka i jeszcze pare y-ków zostanie ;) Wskazanie takiej funkcji żeby była użyteczna z praktycznego punktu widzenia chyba nie jest takie łatwe ;)

[code]
Umieszczenie ich w tablicy to nie problem. Problemem jest to, zeby stringi byly jak najkrotsze. [/code]
Nie wiem czemu się uparłeś, że wartością hasza musi być jakiś string ;) Wartość liczbowa => odpowiedni indeks w tablicy.

[code]
Kurcze widze, ze brakuje mi podstaw bo za cholere nic nie rozumiem.
Po co mi integer modulo p? Czemu akurat takie cos a nie inne ?[/code]

Hmm, działanie modulo p zwraca liczby 0,1,...,p-1. Przyjmujemy sobie z góry, że mamy p szufladek indeksowanych od 0 do p-1. Funkcja haszująca zwraca nam jakieś wartości będące liczbami całkowitymi, jak to weźmiemy modulo p, to akurat trafimy do którejś z szufladek i tam wrzucamy stringa.

pzdr,

y.

Ooooook...

zaczyna mnie juz bolec musk

Umieszczenie ich w tablicy to nie problem. Problemem jest to, zeby stringi byly jak najkrotsze.

Nie wiem czemu się uparłeś, że wartością hasza musi być jakiś string ;) Wartość liczbowa => odpowiedni indeks w tablicy.

No bo to taki moj kaprys... ale powiedzmy, ze podlega to jeszcze negocjacjom :P

Hmm, działanie modulo p zwraca liczby 0,1,...,p-1. Przyjmujemy sobie z góry, że mamy p szufladek indeksowanych od 0 do p-1. Funkcja haszująca zwraca nam jakieś wartości będące liczbami całkowitymi, jak to weźmiemy modulo p, to akurat trafimy do którejś z szufladek i tam wrzucamy stringa.

kurcze no tak... to brzmi bardzo logicznie

zalozmy, ze wiem... chociaz na razie nie wiem ale sie dowiem...

a co z tym hashem ? w jaki sposob proponujesz go liczyc ? :)

Lepiej stosować sprawdzone rzeczy, dlatego proponuję funkcję J.P.Weinbergera ;) Kod nie jest mój (źródło: Internet ;)

[code]
#define PRIME_NUMBER 1031

static inline unsigned long int hashpjw(const char *string)
{
unsigned long int value, g;
const char *str = string;

value = 0;
while (*str != '\0')
{
value = (value << 4 ) + (unsigned long int) *str;
str++;

  g = value & ((unsigned long int) 0xf0000000);
  
  if (g != 0) {
  value = value ^ (g >> 24);
  value ^= g;
  }

}
return value % PRIME_NUMBER;
}

[/code]

PRIME_NUMBER to rozmiar tablicy jaki chcemy mieć

Jak widać zaproponowane haszowanie polega na operacjach bitowych, więc łatwo można to przerobić na haszowanie czegokolwiek (po prostu haszujemy zawartość określonego bloku pamięci)

pzdr,

y.

Dzieki dzieki...

Cos sobie chyba z tego juz zrobie