StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
9551631
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
4
CommunityOwnedDate
CreationDate
2012-03-04T01:53:08.667
FavoriteCount
0
LastActivityDate
2012-03-04T05:22:28.100
LastEditDate
2012-03-04T05:22:28.100
LastEditorUserId
978917
OwnerUserId
978917
ParentId
9551091
PostTypeId
2
Score
16
ViewCount
0
LastEditorDisplayName
text
Body
<blockquote> In my example code below, will every <code>$hash</code> be unique? </blockquote> Almost. (Which, I guess, means "no, but in a way that's easily fixed".) Your function consists of a sequence of independent steps; the overall function is bijective (reversible) if and only if every single one of those steps is. (Do you see why?) Now, each step has one of the following forms: <pre><code> $key = ($key ^ CONSTANT) ^ ($key >> NUM_BITS); $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS); </code></pre> with <code>NUM_BITS != 0</code>. We can actually treat these as variants of a single form, by viewing the former as almost equivalent to this: <pre><code> $key = invert_order_of_bits($key); # clearly bijective $constant = invert_order_of_bits(CONSTANT); $key = ($key ^ $constant) ^ ($key << NUM_BITS); $key = invert_order_of_bits($key); # clearly bijective </code></pre> So all we need is to show that this: <pre><code> $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS); </code></pre> is bijective. Now, XOR is commutative and associative, so the above is equivalent to this: <pre><code> $key = $key ^ ($key << NUM_BITS); $key = $key ^ CONSTANT; </code></pre> and <code>(x ^ y) ^ y == x ^ (y ^ y) == x ^ 0 == x</code>, so clearly XOR-ing with a constant value is reversible (by re-XOR-ing with the same value); so all we have to show is that this is bijective: <pre><code> $key = $key ^ ($key << NUM_BITS); </code></pre> whenever <code>NUM_BITS != 0</code>. Now, I'm not writing a rigorous proof, so I'll just give a single reasoned-out example of how to reverse this. Suppose that <code>$key ^ ($key << 9)</code> is <pre><code>0010 1010 1101 1110 0010 0101 0000 1100 </code></pre> How do we obtain <code>$key</code>? Well, we know that the last nine bits of <code>$key << 9</code> are all zeroes, so we know that the last nine bits of <code>$key ^ ($key << 9)</code> are the same as the last nine bits of <code>$key</code>. So <code>$key</code> looks like <pre><code>bbbb bbbb bbbb bbbb bbbb bbb1 0000 1100 </code></pre> so <code>$key << 9</code> looks like <pre><code>bbbb bbbb bbbb bb10 0001 1000 0000 0000 </code></pre> so <code>$key</code> looks like <pre><code>bbbb bbbb bbbb bb00 0011 1101 0000 1100 </code></pre> (by XOR-ing <code>$key ^ ($key << 9)</code> with <code>$key << 9</code>), so <code>$key << 9</code> looks like <pre><code>bbbb b000 0111 1010 0001 1000 0000 0000 </code></pre> so <code>$key</code> looks like <pre><code>bbbb b010 1010 0100 0011 1101 0000 1100 </code></pre> so <code>$key << 9</code> looks like <pre><code>0101 1000 0111 1010 0001 1000 0000 0000 </code></pre> so <code>$key</code> looks like <pre><code>0111 0010 1010 0100 0011 1101 0000 1100 </code></pre> So . . . why do I say "almost" rather than "yes"? Why is your hash-function not perfectly bijective? It's because in PHP, the bitwise shift operators <code>>></code> and <code><<</code> are not quite symmetric, and while <code>$key = $key ^ ($key << NUM_BITS)</code> is completely reversible, <code>$key = $key ^ ($key >> NUM_BITS)</code> is not. (Above, when I wrote that the two types of steps were "almost equivalent", I really meant that "almost". It makes a difference!) You see, whereas <code><<</code> treats the sign bit just like any other bit, and shifts it out of existence (bringing in a zero-bit on the right), <code>>></code> treats the sign bit specially, and "extends" it: the bit that it brings in on the left is equal to the sign bit. (N.B. Your question mentions "unsigned 32bit" values, but PHP doesn't actually support that; its bitwise operations are always on signed integers.) Due to this sign extension, if <code>$key</code> starts with a <code>0</code>, then <code>$key >> NUM_BITS</code> starts with a <code>0</code>, and if <code>$key</code> starts with a <code>1</code>, then <code>$key >> NUM_BITS</code> also starts with a <code>1</code>. In either case, <code>$key ^ ($key >> NUM_BITS)</code> will start with a <code>0</code>. You've lost exactly one bit of entropy. If you give me <code>$key ^ ($key >> 9)</code>, and don't tell me whether <code>$key</code> is negative, then the best I can do is compute two possible values for <code>$key</code>: one negative, one positive-or-zero. You perform two steps that use right-shift instead of left-shift, so you lose two bits of entropy. (I'm hand-waving slightly — all I've actually demonstrated is that you lose at least one bit and at most two bits — but I'm confident that, due to the nature of the steps between those right-shift steps, you do actually lose two full bits.) For any given output value, there are exactly four distinct input-values that could yield it. So it's not unique, but it's almost unique; and it's easily fixed, by either: <ul> <li>changing the two right-shift steps to use left-shifts instead; or</li> <li>moving both of the right-shift steps to the start of the function, before any left-shift steps, and saying that outputs are unique for inputs between 0 and 231−1 rather than inputs between 0 and 232−1.</li> </ul>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POPerfect Hash Function for Human Readable Order Codes
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USruakh
UserOwnerUserId
1. USruakh
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POPerfect Hash Function for Human Readable Order Codes
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.