DOUBT IN HASHTABLE CLASS

#1

bhaiya , jese isme hamne function likhey hai bhot saaare, to insert function bhi O(string_length()) time le rha hai search function bhi O(size of linkedlist) time le rha hai, rehash bhi O(tablesize) , to fir ham insert, search , delete operations ko O(1) kese bol rhe hai?

#2

hello @CODER_JATIN

bro O(1) is the amortised time complexity (read about load factor).
in worst case it will remain O(n) only.

#3

hmmm, matlab worst case mai to bhaiya O(N) hi hogi naa?

#4

ha , but agar hamne hash function kaafi acha design kiya hai, jo data ko equally ditribute kar raha ho pure table me tab us case me on average O(1) perfomance achieve kar sakte hai.
isiliye hash function design karna sabse important task hota hai hashing me

#5

hmm matlab agar hmaare hashtable mai collision hui hi ni, fir to linkedlist bnegi hi nhi , tab O(1) Hoga?

#6

ye to keval ek single case ho gya,
tum ek baar load factor padho tumhe samjh aa jayega ki kab O(1) performance dega aur kab o(n)

#7

Okay Bhaiya.

or jo bhaiya ne collision handling scheme btaayi hai , usse bhi collision ho to rhe hi hai , to koi esa method bhi hai jisme collisions 0 ho jaaye?

#8

its not possible bro. kyunki table ka size of limited hi hai na.
0 collision tabhi passible hai jab no of entries kam ho table ke size se.
otherwise collision hamesha hoga, hum uska kaise handel karte hai wo hamari time complexity ko affect karega

#9

okay bhaiya :slight_smile:

int hashFn(string key)
{
int idx=0;
int p=1;
for(int j=0;j<key.length();j++)
{
idx=idx+(key[j]p)%table_size;
idx=idx%table_size;
p=(27p)%table_size;

	}

	// cout<<"Index generated for "<<key<<" is "<<idx<<"\n";

	return idx;
}

bhaiya is function mai ham baar baar % kyo kar rhe hai table size se ,?

ye to mujhe pta hai ki property hoti hai ki
(a+b+c)%m= (a%m+b%m+c%m)%m,
lekin ye har step pe kese kyo mod kar rhe hai ham?

#10

kyunki index hamara [0…tablesize-1] tak hi hai na, ise bada index nahi hai hamare table me isiliye % kar rahe hai table size se

#11

Okay ustaad ji :slight_smile:
or bhaiya ek cheez or ,
https://ide.codingblocks.com/s/441639 , is code mai line no 25 pe jo if condition hai vo smjhado

#12

@CODER_JATIN

	if(temp!=NULL)
			{
				delete oldtable[i];
			}

ye hai correct syntax.
yaha pe hum if statement me check kar rahe hai ki kya koi list hai bhi ya nahi .
agar list hai to hum use delete command ki help se erase kar rahe hai
delete oldtable[i] ; recusively pure lisk ko delete kar dega.

#13

Lekin bhaiya , is if condition se pehle hamne ek while(temp!=NULL) bhi to chalai hai to while loop khatam hone ke baad to hamesha temp NULL hi hoga

#14

yaha pe oldtable[i] karlo.

#15

hanji bhaiya ye to smjh aa gya lekin mai ye puch rha hu ki , if condition se pehle jab while loop chalegi to temp ne to NULL hi hojana fir if condition ka kya fayda hua?

#16

wahi to correction bataya bro, temp ki jagah pe oldtable[i] ko check karo temp hamesha null hi rahega while ke baad

#17

OKAY SIR JI , DHANYAWAAD :0

#18

THANK YOU :slight_smile: … …

#19

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.