[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Hash Table Collisions (n.runs-SA-2011.004)
- From: Roberto Ierusalimschy <roberto@...>
- Date: Mon, 9 Jan 2012 19:49:12 -0200
> my gut feeling is that you're right for strings longer than 1k or so;
> but strings less than 80 doesn't seem unreasonable to compare and use
> as key.
>
> does 32 has any nice advantage as a limit? or would 64 work as well?
Any value would do. It does not even have to be a power of 2. And there
would be no visible difference between both kinds of strings (except for
[hopefully small] performance differences).
The main balance is between computing the hash for all strings up to N
bytes, regardless of whether they will be used as a key (as it is
done today) versus doing string equality comparisons (including when
hashing) with memcmp instead of pointer equality.
-- Roberto
- References:
- Re: Hash Table Collisions (n.runs-SA-2011.004), Vladimir Protasov
- Re: Hash Table Collisions (n.runs-SA-2011.004), Miles Bader
- Re: Hash Table Collisions (n.runs-SA-2011.004), Ashwin Hirschi
- Re: Hash Table Collisions (n.runs-SA-2011.004), Miles Bader
- Re: Hash Table Collisions (n.runs-SA-2011.004), David Kolf
- Re: Hash Table Collisions (n.runs-SA-2011.004), Miles Bader
- Re: Hash Table Collisions (n.runs-SA-2011.004), Alexander Gladysh
- Re: Hash Table Collisions (n.runs-SA-2011.004), Roberto Ierusalimschy
- Re: Hash Table Collisions (n.runs-SA-2011.004), Roberto Ierusalimschy
- Re: Hash Table Collisions (n.runs-SA-2011.004), Javier Guerra Giraldez