On Sat, 29 Nov 2014 15:50:59 -0800, bartekltg wrote:

>> Nie wydaje mi się żeby to wyliczenie Bartka dotyczące czasu używania
>> tablic było sensowne: można wyliczone hashe ułożyć w b-tree i zrobić
>> lookup log(n) po hashu z hasła usera. Nie da się?
>
> Nie, nie da się. To do cholery nie problem przeszukiwania! ;-)
> Nie da się bo nie masz takiej pojemnośći, by wszystkie hashe (z
> malutkiego przykladu) trzymać.
> Dlatego korzysta się z tablic tęczowych, to tradeof pomiędzy objętością
> bazy danych a potrzebną mocą.
> Myślisz o np 10^11 łańcuchach hashy, każdy mający 10^9 elementów. Na
> dysku trzymasz tylko pierwszy i ostatni element łancucha (coś rzędu
> wspomnianego terabajta).
>
> Jeśli teraz dostajesz zadanie, rozbij hash X, liczysz łańcuch od niego,
> i dla każdego elementu łancucha sprawdzamy, czy nie jest elementem
> końcowym któregoś z danych na dysku.
>
> I tu niespodzianka, Ty proponujesz robić to w log[n] odczytach z dysku,
> a ja zaproponowałem robić to _jednym_ odczytem z dysku;p Bardzo
> optymistyczne oszacowanie;-)

A ok, doczytam.