hash - Hashing complexity regarding the no of searches in worst case -

hash - Hashing complexity regarding the no of searches in worst case -

a hash table has size of 11 , date fitted in postion {3,5,7,9,6} how many comparisons have made if info not found in list in worst case 2,11,6

that depends lot on how terminology's intended , hash table implementation...

"a hash table of size 11" might mean 11 elements (especially in c++ .size() function finding out how many elements in table), or 11 buckets, in case means latter;

"data fitted" might intended mean there's single datum (the singular of data) in each of bucket positions, or might mean there 1 or more (but if latter's intended , "size" isn't number of buckets, there's no answer).

"how many comparisons" means key-vs-key comparisons, implementation need perform comparisons of bucket content against no-[more]-value sentinels too

the implementation might handle collisions using list of colliding keys per bucket, or might rehash or cascade/jump through set of offsets (a displacement list) hashed-to-bucket

so, if assume 11 buckets, there's 1 info item @ each bucket position {3,5,7,9,6} , key-on-key comparisons, , nominally lists of colliding elements per bucket, worst can happen comparing against buckets existing entry, means key-on-key comparing key-vs-sentinel comparison. satisfy "2" answer.

if scheme uses displacement lists or rehashing, there's no protection against visiting same bucket several times (it's statistically unlikely), there no "worst case" limit short of implementation giving up.

if specific dead simple case displacement increments seek next bucket, might give after visiting string of populated buckets , finding first empty one... given {3,5,7,9,6} worst case compares keys @ 5 6 7 compares against sentinel @ 8, 3 or 4 total comparisons depending on how count it.

if size indicates number of elements, such 11 spread across {3,5,7,9,6} possible if individual bucket maintained list of colliding keys, if 4 of buckets had single key, remaining bucket might have 11-4 = 7, there 7 key-on-key comparisons before failure.

it's hard imagine reasonable interpretation of question yielding 6 or 11 comparisons, counting method.

if someone's asked in academic setting, there might specific implementation , notational conventions can apply when considering question. if such context missing, whomever's asking either lazy or not versed in basics of hash tables.

hash