[so] [Tema1] Nelamurire comanda 'rezise halve'

[Mihai Barbulescu]

2017-02-25 14:30 GMT+02:00 Mihai Barbulescu <b12mihai at gmail.com>:
> 2017-02-25 14:20 GMT+02:00 Olaru Catalin via so <so at cursuri.cs.pub.ro>:
>>
>> Buna ziua,
>>
>> Am o nelamurire in privinta comenzii 'resize halve' la tema1. Enuntul spune "Dacă dimensiunea hash-ului este impară (2k+1), după înjumătațire dimensiunea lui va fi k."
>>
>> Daca vom avea la un moment dat un hash de dimensiune 1 si vom primi comanda resize halve, atunci dimensiunea noua ar trebui sa devina 0, ceea ce nu prea are sens, pentru ca nu am avea unde sa bagam cuvintele deja existente in tabel.
>>
>> Intrebarea concreta este: Se garanteaza ca nu vom intalni niciodata cazul acesta? Daca nu, cum il abordam?
>>
>
> Salut Catalin,
>
> Nu exista un astfel de test cu hash de dimensiune 1. Poti pentru
> moment sa presupui ca nu vei intalni acest caz.
> Voi reverifica si eu testele pentru.
>
> Vom avea in vedere clarificarea in enunt la lansarea temei.
>

E actualizat si in enunt acum ce trebuie sa faceti exact. De fiecare
data cand chemam resize_halve nu trebuie sa va faceti griji
dimensiunea hashtable-ului va fi >=2 :

resize halve: înjumătățește dimensiunea hash-ului (bucket-urile vor fi
parcuse în ordine și cuvintele sunt redistribuite; memoria în surplus
va fi dealocată). Se garantează în teste că dimensiunea hash-ului va
fi mai mare sau egală cu 2 de fiecare dată când e chemată această
comandă pe hashtable.

http://ocw.cs.pub.ro/courses/so/teme/tema-1?&#enunt



-- 
Cu stimă,
Mihai Bărbulescu