hash()

[John Marshall]

Hi,

For strings of > 1 character, what are the chances
that hash(st) and hash(st[::-1]) would return the
same value?

My goal is to uniquely identify multicharacter strings,
all of which begin with "/" and never end with "/".
Therefore, st != st[::-1].

Thanks,
John

[Scott David Daniels]

Re: hash()

John Marshall wrote:[color=blue]
> For strings of > 1 character, what are the chances
> that hash(st) and hash(st[::-1]) would return the
> same value?[/color]

Why not grab a dictionary and do the stats yourself?

--Scott David Daniels
scott.daniels@a cm.org

[John Marshall]

Re: hash()

Scott David Daniels wrote:[color=blue]
> John Marshall wrote:
>[color=green]
>>For strings of > 1 character, what are the chances
>>that hash(st) and hash(st[::-1]) would return the
>>same value?[/color]
>
>
> Why not grab a dictionary and do the stats yourself?[/color]

I was actually interested in the mathematical/probability
side rather than the empirical w/r to the current
hash function in python. Although I imagine I could do
a brute force test for x-character strings.

John

[Christopher Subich]

Re: hash()

John Marshall wrote:
[color=blue]
> I was actually interested in the mathematical/probability
> side rather than the empirical w/r to the current
> hash function in python. Although I imagine I could do
> a brute force test for x-character strings.[/color]

Hah. No.

At least on the version I have handy (Py 2.2.3 on Itanium2), hash
returns a 64-bit value. Brute-forcing that in any reasonable length of
time is rather impossible.

[Scott David Daniels]

Re: hash()

John Marshall wrote:[color=blue]
> Scott David Daniels wrote:[color=green]
>> ... Why not grab a dictionary and do the stats yourself?[/color]
> I was actually interested in the mathematical/probability
> side rather than the empirical w/r to the current
> hash function in python.[/color]
Well, the probability depends on the universe you are choosing from.
That was why I was suggesting a dictionary: words may well have a
different distribution than arbitrary strings.

--Scott David Daniels
scott.daniels@a cm.org

[Raymond Hettinger]

Re: hash()

[John Marshall][color=blue]
> For strings of > 1 character, what are the chances
> that hash(st) and hash(st[::-1]) would return the
> same value?[/color]

Python's string hash algorithm is non-commutative, so a collision with
a reversed string is not likely. The exact answer depends on the
population of strings being hashed, but it's not hard to compute
collision statistics for a sampling of those strings:

collisions = len(sample) - len(set(hash(s) for s in sample))


FWIW, here is how Python computes string hash values:

static long
string_hash(PyS tringObject *a)
{
register int len;
register unsigned char *p;
register long x;

len = a->ob_size;
p = (unsigned char *) a->ob_sval;
x = *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= a->ob_size;
if (x == -1)
x = -2;
return x;
}


[color=blue]
> My goal is to uniquely identify multicharacter strings,
> all of which begin with "/" and never end with "/".
> Therefore, st != st[::-1].[/color]

Just use a set -- no string reversal is needed for detection of unique
multicharacter strings..


Raymond