table - Expected number of hash collisions -

-


table - Expected number of hash collisions -

i sense i'm way overthinking problem, here goes anyway...

i have hash table m slots in internal array. need insert n elements hash table. assuming have hash function randomly inserts element slot equal probability each slot, what's expected value of total number of hash collisions?

(sorry more of math question programming question).

edit: here's code have simulate using python. i'm getting numerical answers, having problem generalizing formula , explaining it.

import random import pdb n = 5 m = 8 num_iter = 100000 def get_collisions(table): col = 0 item in table: if item > 1: col += (item-1) homecoming col def run(): table = [0 x in range(m)] in range(n): table[int(random.random() * m)] += 1 #print table homecoming get_collisions(table) # main total = 0 in range(num_iter): total += run() print float(total)/num_iter

you'll find reply here: quora.com. expected number of collisions m buckets , n inserts is

n - m * (1 - ((m-1)/m)^n).

table hash collision

Comments

Post a Comment

Popular posts from this blog

How do I check if an insert was successful with MySQLdb in Python? -

-
How do I check if an insert was successful with MySQLdb in Python? - i have code: cursor = conn.cursor() cursor.execute(("insert new_files (videos_id, filename, " "is_processing) values (%s,%s,1)"), (id, filename)) logging.warn("%d", cursor.rowcount) if (cursor.rowcount == 1): logging.info("inserted values %d, %s", id, filename) else: logging.warn("failed insert values %d, %s", id, filename) cursor.close() fun is, cursor.rowcount always one, though updated database create videos_id unique key. is, insert fails because in tests same videos_id going appear (and when check database, nil inserted). whatever reason, rowcount 1 - logging.warn have spits out rowcount of 1. so, question: can utilize rowcount work out if insert went fine? if so, (presumably) doing wrong? otherwise, how check if insert went fine? your code not commit after modifications (your modifications rolled back). should...
Read more

delphi - blogger via idHTTP : error 400 bad request -

-
delphi - blogger via idHTTP : error 400 bad request - i'm trying post blogger using idhttp component, however, i'm getting "http/1.0 400 bad request" error. procedure tform1.button1click(sender: tobject); var request,response,req : tstringlist; auth,blogid : string; begin blogid := '00000000000000000000000'; request := tstringlist.create; response := tstringlist.create; req := tstringlist.create; idhttp1.request.connection := 'keep-alive'; idhttp1.request.contenttype := 'application/x-www-form-urlencoded'; idssliohandlersocket1.ssloptions.method := sslvsslv23; request.clear(); request.values['accounttype'] := 'google'; request.values['email'] := 'xxx@gmail.com'; request.values['passwd'] := 'yyy'; request.values['service'] := 'blogger'; response.text :=idhttp1.post('https://www.google.com/accounts/clientlogin',request); auth := resp...
Read more

postgresql - ERROR: operator is not unique: unknown + unknown -

-
postgresql - ERROR: operator is not unique: unknown + unknown - i have postgis database , have compute new values rows in new column. these values should average of values of several columns. query: insert bdps (da_m) values (avg('da_1'+'da_2'+'da_3'+'da_4'+'da_5'+'da_6'+'da_7')); in query bdps database, da_m new column , da_1 da_7 existing columns have double precision type. da_m created using alter table bdps add together column da_m double precision; i next error: error: operator not unique: unknown + unknown line 2: values (avg('da_1'+'da_2'+'da_3'+'da_4'+'da_5'+'da_6'+'da_7... ^ hint: not take best candidate operator. might need add together explicit type casts. ********** error ********** error: operator not unique: unknown + unknown sql state: 42725 hint: not take best candidate operator. might need add togethe...
Read more