MESSAGE
| DATE | 2015-05-06 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [LIU Comp Sci] hashing multiplication
|
From owner-learn-outgoing-at-mrbrklyn.com Wed May 6 11:31:53 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 5E9CE1612E1; Wed, 6 May 2015 11:31:53 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 4F3211612ED; Wed, 6 May 2015 11:31:53 -0400 (EDT)
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id A034D1612E1
for ; Wed, 6 May 2015 11:31:27 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 216D412DA5;
Wed, 6 May 2015 11:31:26 -0400 (EDT)
Message-ID: <554A33CE.8070504-at-panix.com>
Date: Wed, 06 May 2015 11:31:26 -0400
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: "Jose A. Rodriguez"
Subject: [LIU Comp Sci] hashing multiplication
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com
I don't understand question 9. I've been working on it since 6AM and
even on the day that you presented this material. Variables drop in the
proof without clear definitions, and the last 2 lines seem to be
completely disconnected to what was presented before. I'm sure it my
fault, but I don't know what p,m,k,a,b, or even A stand for. Most of
all, I don't know what p is.
This is what I understand
h(k) = m(kA % 1) ==> and then you make that the floor
and I'm not sure why because % 1 makes a fraction EVERY TIME except for
whole numbers. floor 5.25%1 has to be 0.25
m is the table size - that I understand.
k is the key
kA % 1 is a fraction, specifically the fraction part of kA and when
multiplied by m that give you some value less than m, and now I see why
you need the floor.
this formula guarantees you hash less than m. It says nothing about
shared values, FWIW, or probing.
Up to this I understand.
Now, more assumptions
k must be less than a word. This should have been said on the top, IMO.
and it is kind of useless because it leaves very few keys
m = 2^p <=== Now this is where I start to get lost. What purpose is p?
A = s/2^w <==== Now what is s for?
Now what can be added to the notes is as follows:
if i follow your logic here
Since A is a real number such that 0< A < 1
if we multiply A times the maximum integer of the size of a word we get
a value, which we can call s, whose domain is 0< and less than 2^w
A*2^w = s
where 0 < s < 2^w
and 0 < A < 1
and where 0 < k < 2^w <== by definition
that means
kA = k s/2^w has a range of
0 < ks < 2^(2w) of to say ks, whatever s is, fits in two words
Now here is the really good part ;)
For no reason at all, lets turn this in to a polynumer equation or order w.
ks = a2^w +b(2^w)^0 ... just so I can understand it ;)
ks = a2^w + b where b is the lower word and a is the bits of the higher
word.
Fine, I actually understand this up to here. Then I'm completely lost.
It says the fractional part of kA = ks/2^w is b/2^w ????
you lost me here. The fractional part of kA is completely dependent on
a k and A. If k is 2, which is a valid prossible k,, and A is 0.5.
which is a completely valid A, then there is no fractional part of kA...
|
|
