Въпрос относно HashTable имплементацията?


14
Здравейте, колеги!
Искам да попитам относно някои неща, с които се сблъсках при имплементацията на хеш таблицата от домашните. А именно:
1. Load фактора какво ще следи ... колко процента от масива е запълнен или колко е процентното съдържание на ключове. Например, началния ни размер е 16. Ако следим запълнеността на масива, то на 12 запълнени позиции, вече ще сме изпълнили това условие за 75 %. Но на 12 позиции, реално може да имаме такива, в които има Листове с по 2-3 елемента в тях (колизии) и примерно общо 19 ключа. Аз съм го направил да се преоразмерява, когато вече трябва да слагаме на 13-та позиция нещо ... не знам дали е правилно. В моя тестов клас, на 12 позиции имам близо 17-18 ключа. После при auto-grow-а се разпределят по-добре и почти няма колизии. Но правилно ли е това или трябва на 12-ти добавен ключ, на 13-тия вече да се удвои хеш таблицата и да изпълни всичко наново.
2. Count property-то да връща запълнените позиции в масива или общия брой ключове? На 12 позиции с 19 ключа, 12 или 19 трябва да е Count, като се има предвид, че имаме друго property Keys, което ще пази лист с тия 19 ключа.
Благодаря! :)



Отговори



6
Count връща колко елемента имаш в хеш-таблицата. Ако си вкарал 15 елемента и те направят 15 колизии, ще ти върне 15, не 1. Load факторът е базиран на Count.

от Iliev (1241 точки)


0
Аха. Значи ти мислиш, че ще удвояваме размера, когато минем 12-тия елемент без значение колко позиции ще сме заели в масива. Може и така да е.
Мерси! :)

от Ivaylo.Angelov (1890 точки)

0
Моля :))) Удвояваме размера, когато count/capacity надвиши 0.75.

от Iliev (1241 точки)



8

1.Load-а съм го направил за 75% заети позиции в масива, защото де факто това с повечето елементи на един индекс идва като добавка към хеш таблицата, за да се справи с колизиите, а самата хештаблица според мен трябва да си следи запълненоста като заети позиции в масива.

2. Count свойството според мен трябва да връща общия брой на запазените елементи в таблицата, защото иначе не знам каква работа би свършила на потребителя на хештаблицата информацията, че вътрешно са заети еди си колко клетки от масива с който се представя таблицата :)

Това е моята логика нямам претенции да е вярна, но поне на мен ми се струва логична laugh


от mstefanov (761 точки)


0
Значи за 1 сме двама, които мислим така. За 2 мисля, че ти си прав и ще го направя и аз най-вероятно така. Защото все пак наистина потребителя ще иска да знае колко елемента има в тая хеш таблица, а него как е реализирана примерно не го интересува толкова много. А и колизиите ще станат прикрити.
Добре, много ти благодаря! :)

от Ivaylo.Angelov (1890 точки)


5
Има и един много кофти момент, за който се сетих. Примерно имаме currentCapacity = 16. Имаме 12 заети. На 13 правим удвояване. currentCapacity става 32. Но по някаква причина трием елемент и стават отново 12. Но currentCapacity си стои 32. И реално на следващото добавяне ще направи пак удвояване, което ще е ненужно.
В крайна сметка мисля да оставя maxLoad базиран на заетостта на масива, за Count е ясно, че ще връща броя елементи общо. А пък за триенето, auto downgrade е малко мъка и не знам дали ми се пише и дали си струва да се пробвам с него засега. :D

от Ivaylo.Angelov (1890 точки)


0
Защо да удвоява пак? Аз съм го направил, като добавя елемент и изчислява лоуда и ако е > 0.75 прави Expand(), но ти ако си експанднал до 32 и елементите ти намалеят ще ти падне и лоуда и няма да имаш основание да удвояваш. Така че ако си го направил да експандва спрямо лоуда няма значение дали заетите елементи са 12 или 13, а дали лоуда е 0.70 или 0.76 примерно :)

от mstefanov (761 точки)

0
Разбрах да. Аз го бях направил по малко по-тъп начин и затова се прецакваше. Наивна грешка. Сега го оправих. :) Мерси!

от Ivaylo.Angelov (1890 точки)


6
Автоматичното преоразмеряване се прави само за да се увеличи размера. Размерът не се намалява дори и след Clear(), остава същия. Ако изрично искаш да премахнеш празните елементи, се ползва TrimExess().

от Iliev (1241 точки)


0
Да, просто имах малко пропуски в кода, които го издънваха. Мерси много за помощта! :)

от Ivaylo.Angelov (1890 точки)