Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #29372 > unrolled thread
| Started by | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| First post | 2017-02-02 19:29 +0100 |
| Last post | 2017-02-04 07:33 -0800 |
| Articles | 4 — 2 participants |
Back to article view | Back to pl.comp.programming
Implementacja tablicy haszującej w pliku Borneq <borneq@antyspam.hidden.pl> - 2017-02-02 19:29 +0100
Re: Implementacja tablicy haszującej w pliku Borneq <borneq@antyspam.hidden.pl> - 2017-02-02 19:31 +0100
Re: Implementacja tablicy haszującej w pliku Borneq <borneq@antyspam.hidden.pl> - 2017-02-03 09:46 +0100
Re: Implementacja tablicy haszującej w pliku "M.M." <mmarszik@gmail.com> - 2017-02-04 07:33 -0800
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2017-02-02 19:29 +0100 |
| Subject | Implementacja tablicy haszującej w pliku |
| Message-ID | <o6vtq7$c6f$1@node2.news.atman.pl> |
Normalnie gdy jest w pamięci, liczę hasz, potem numer bucket.
Czy capacity powinno być potęgą dwójki czy lepiej nie?
gdy jest potęgą to mogę zamiast liczyć mod, liczyć:
bucketIdx = hash & (Capacity-1);
potem mam
Bucket = record
hash
key
value
next -> Bucket
end;
hash, chyba niepotrzebne, potrzebne key, by sprawdzić czy to właściwa
wartość dla value.
Ale jest lista next->next->next->Bucket
Jak to będzie w pliku? Musiał by być wskaźnik na inne miejsce tablicy i
ruch głowicy a to miejsce będzie na końcu pliku? Jak działać gdy ilość
elementów zmieni się znacznie?
Plik miałby capacity+reszta rekordów?
[toc] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2017-02-02 19:31 +0100 |
| Message-ID | <o6vtul$c6f$2@node2.news.atman.pl> |
| In reply to | #29372 |
W dniu 02.02.2017 o 19:29, Borneq pisze: > Plik miałby capacity+reszta rekordów? jest jakaś metoda matematycznej statystyki oszacować ile będzie ta reszta? Na przykład gdy capacity=ilość elementów, wtedy ile będzie pustych i ile będzie w tym samym kubełku?
[toc] | [prev] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2017-02-03 09:46 +0100 |
| Message-ID | <o71g0e$e1i$1@node1.news.atman.pl> |
| In reply to | #29372 |
W dniu 02.02.2017 o 19:29, Borneq pisze: > Normalnie gdy jest w pamięci, liczę hasz, potem numer bucket. tablica hash pozwala na lokalizację obiektu, ale nie na wyświetlenie ich w kolejności, jak indeks będący tablicą posortowaną.
[toc] | [prev] | [next] | [standalone]
| From | "M.M." <mmarszik@gmail.com> |
|---|---|
| Date | 2017-02-04 07:33 -0800 |
| Message-ID | <e2835972-0634-498f-8995-c1d4f294977b@googlegroups.com> |
| In reply to | #29380 |
On Friday, February 3, 2017 at 9:46:07 AM UTC+1, Borneq wrote: > W dniu 02.02.2017 o 19:29, Borneq pisze: > > Normalnie gdy jest w pamięci, liczę hasz, potem numer bucket. > > tablica hash pozwala na lokalizację obiektu, ale nie na wyświetlenie ich > w kolejności, jak indeks będący tablicą posortowaną. Tak, ale są wyjątki od tej reguły. Gdy np. chcesz w hashtable przechowywać maksymalnie 100 unikalnych liczb z przedziału od 0 do 1000. Wtedy jako hash bierzesz po prostu wartość tej liczby i możesz wyświetlić w kolejności - ale to szczególny przypadek. Generalnie gdy przechowujesz małe liczby w hash-table, rzędu M*N, gdzie N to rozmiar tablicy, możesz wyświetlić je posortowane w M przebiegach tablicy lub w M przebiegach danych - zależy od typu tablicy. Pewnie istnieją jeszcze inne szczególne przypadki które umożliwiają wyświetlenie danych przechowywanych w hash-table w kolejności sortowania. Pozdrawiam
[toc] | [prev] | [standalone]
Back to top | Article view | pl.comp.programming
csiph-web