hash - Is it possible to implement universal hashing for the complete range of integers? -

-

i reading universal hashing on integers. prerequisite , mandatory precondition seems choose prime number p greater set of possible keys.

i not clear on point.

if our set of keys of type int means prime number needs of next bigger data type e.g. long.

but whatever hash need down-casted int index hash table. doesn't down-casting affect quality of universal hashing (i referring distribution of keys on buckets) somehow?

if our set of keys integers means prime number needs of next bigger data type e.g. long.

that not problem. necessary otherwise hash family cannot universal. see below more information.

but whatever hash need down-casted int index hash table.

doesn't down-casting affect quality of universal hashing (i referring distribution of keys on buckets) somehow?

the answer no. try explain.

whether p has data type or not not important hash family universal. important p equal or larger u (the maximum integer of universe of integers). important p big enough (i.e. >= u).

a hash family universal when collision probability equal or smaller 1/m.

so idea hold constraint.

the value of p, in theory, can as big long or more. needs integer , prime.

  • u size of domain/universe (or number of keys). given universe u = {0, ..., u-1}, u denotes size |u|.
  • m number of bins or buckets
  • p prime must equal or greater n
  • the hash family defined h = {h(a,b)(x)} h(a,b)(x) = ((a * x + b) mod p) mod m. note a , b randomly chosen integers (from possible integers, theoretically can larger p) modulo prime p (which can make them either smaller or larger m, number of bins/buckets); here data type (domain of values not matter). see hashing integers on wikipedia notation.
  • follow proof on wikipedia , conclude collision probability _p/m_ * 1/(p-1) (the underscores mean truncate decimals). p >> m (p considerably bigger m) probability tends 1/m (but not mean probability better larger p is).

in other terms answering question: p being bigger data type not problem here , can required. p has equal or greater u , a , b have randomly chosen integers modulo p, no matter number of buckets m. these constraints can construct universal hash family.

maybe mathematical example help

  • let u universe of integers correspond unsigned char (in c example). u = {0, ..., 255}

  • let p (next possible) prime equal or greater 256. note p can of these types (short, int, long signed or unsigned). the point data type not play role (in programming type denotes domain of values.). whether 257 short, int or long doesn't matter here sake of correctness of mathematical proof. have chosen larger p (i.e. bigger data type); not change proof's correctness.

    1. the next possible prime number 257.
    2. we have 25 buckets, i.e. m = 25. means hash family universal if collision probability equal or less 1/25, i.e. approximately 0.04.
    3. put in values _p/m_ * 1/(p-1): _257/25_ * 1/256 = 10/256 = 0.0390625 smaller 0.04. universal hash family chosen parameters.

we have chosen m = u = 256 buckets. have collision probability of 0.003891050584, smaller 1/256 = 0,00390625. hash family still universal.

let's try m being bigger p, e.g. m = 300. collision probability 0, smaller 1/300 ~= 0.003333333333. trivial, had more buckets keys. still universal, no collisions.

implementation detail example

we have following:

  • x of type int (an element of |u|)
  • a, b, p of type long

  • m we'll see later in example

    1. choose p bigger max u (element of |u|), p of type long.
    2. choose a , b (modulo p) randomly. of type long, < p.
    3. for x (of type int u) calculate ((a*x+b) mod p). a*x of type long, (a*x+b) of type long , ((a*x+b) mod p of type long. note ((a*x+b) mod p)'s result < p. let's denote result h_a_b(x).
    4. h_a_b(x) taken modulo m, means @ step depends on data type of m whether there downcasting or not. however, not matter. h_a_b(x) < m, because take modulo m. hence value of h_a_b(x) modulo m fits m's data type. in case has downcasted there won't loss of value. , have mapped key bin/bucket.

Comments

Post a Comment

Popular posts from this blog

python - No exponential form of the z-axis in matplotlib-3D-plots -

-
Image
i have similar problem described in how prevent numbers being changed exponential form in python matplotlib figure : i don't want (in special case) weird scientific formatting of axis. problem different have problem @ z -axis. 2-d plots can use ax.get_yaxis().get_major_formatter().set_useoffset(false) . , there no function ax.get_zaxis() what use format z -axis same way? edit: example: from mpl_toolkits.mplot3d import axes3d import numpy np import sys import matplotlib import matplotlib.pyplot pyplot def func(xi, ti): res = 10e3 + np.cos(ti) * np.sin(xi) return res if __name__ == '__main__': timespacing = 20 timestart = 0 timeend = 1 time = np.linspace(timestart, timeend, timespacing) widthspacing = 50 widthstart = 0 widthend = 3 width = np.linspace(widthstart, widthend, widthspacing) reslist = [] matplotlib.rcparams['legend.fontsize'] = 10 fig = pyplot.figure() ax = fig.gca(projection = '3d...
Read more

php - Best Light server (Linux + Web server + Database) for Raspberry Pi -

-
i install web server database on raspberry pi (little computer). computer has 1gb ram. i want know best combination: linux distribution , web server , dbms run local server multiple users minimal latency, use php on server. , best settings performance , not have bugs (memory usage, disable plugin, disable service, etc)? i thought light debian , lighttpd server , sqlite database. solution? i think lighttpd + sqlite great choice. linux distro, debian @ centos or tiny core linux , although i'm not sure of compatibility pi. obviously, can't go wrong raspbian if want use in production , more stable performance, few more pi's , set them in cluster .
Read more

c# - "Newtonsoft.Json.JsonSerializationException unable to find constructor to use for types" error when deserializing class -

-
i developing app in xamarin android. have splash screen serialize class , pass mainactivity using intent . when try deserialize in mainactivity error message : "serializationexception unable find constructor use types" serialization : void loaddata() { currency currency = new currency(this); intent = new intent(this, typeof(mainactivity)); intent.putextra("currency", newtonsoft.json.jsonconvert.serializeobject(currency)); startactivity(intent); } deserialization : cur = newtonsoft.json.jsonconvert.deserializeobject<currency> (intent.getstringextra("currency")); // error here class constructor : public currency(context context) { thiscontext = context; } i began experiencing problem after added parameter context context constructor. has caused this? how can solve it? possible serialize/deserialize class has parameters? you need have empty constructor in currency class in order deserialize it. ...
Read more