🚀 go-pugleaf

Showstoppa wrote:
> witam
> chcialbym sie dowiedziec jakie sa roznice miedzy hashtable a
> arraylist ? jakies sa zalety i wady obu tablic ?
>
> chcialbym odpalic w aplikacji kilka watkow i miec jakos dostep do nich
> przez umieszczenie ich w tablicy.
[...]

Witam!

Haszowanie, hashing, inaczej algorytmy mieszające to właściwie cała
metodologia tworzenia algorytmów do efektywnego wyszukiwania. W ArrayList
jest stosowany z algorytm liniowy, brutalny, wyczerpujący, czy jak go zwać,
aby znaleźć odpowiedni element. W najgorszym wypadku trzeba przeszukać całą
tablice aby dowiedzieć się, że elementu w tablicy nie ma. Czyli po prostu
pętla po wszystkich elementach. Inne algorytmy to wyszukiwanie połówkowe
(binarne) albo drzewa. Te algorytmy opierają się na tym, że dane są
posortowane albo  są organizowane w drzewa w odpowiedniej kolejności.
Np. o specjalne drzewa oparte są indeksy w bazach danych, B-Tree. W bazach
danych ważne są także aspekty dyskowe stosowanych algorytmów, ponieważ ruch
głowicy dysku długo trwa. O ile mi wiadomo sterta (heap) czyli pamięć
dynamiczna to także drzewo binarne pełne. Czyli dwa elementy w każdym węźle.
A są także algorytmy mieszające. Algorytmy mieszające za pomocą specjalnej
funkcji zgadują położenie elementu. Oczywiście podobna funkcja służy do
umieszczenia elementu. Jest to metoda zamiany danych na adres w strukturze.
Najbardziej brutalny sposobem było by odwzorowanie bezpośrednie (jeśli
dobrze pamiętam nazwę). Czyli np. każdy układ liter w nazwisku, składającym
się np. z 20 znaków, ma obliczony inny adres. Oczywiście wtedy taka
struktura była by ogromna, a osób o nazwiskach Aaaaaa raczej jest mało.
Dlatego zwykle pod danym adresem znajduje się wiele elementów.
Czasem ludzie stosują algorytmy haszujące, np. kiedy szukamy hasła w
encyklopedii wiemy mniej-więcej gdzie położyć polec na podstawie położenia
litery w alfabecie. Z algorytmów haszujacy korzystają także bazy danych. O
ile wiem haszowanie ma jakieś zastosowanie także w kryptografii. Chyba
funkcje skrótu czy inne sumy kontrolne także mają z tym coś wspólnego.

Generalnie stosują algorytmy przyspieszające wyszukiwanie wydłużamy
aktualizacje danych i często używamy dodatkowej pamięci do przechowywania
np. indeksów.

Tyle co zapamiętałem z książki o algorytmach i strukturach danych. Zwykle i
tak stosuje się proste pętle bo tablice są małe, a dużą ilość danych
przerzuca się na bazy danych.

-- 
Pozdrawiam,
Marek Janaszewski
[ j_m...@gazeta.pl ]