Re: hash values and equality

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.dougwise.org!selfless.tophat.at!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<python-python-list@m.gmane.org>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.001
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'value,': 0.04; 'pointer': 0.05; 'correct.': 0.09; 'hash': 0.09; 'integer,': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:80.91.229.12': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'received:lo.gmane.org': 0.09; 'slot': 0.09; 'described': 0.14; '(is': 0.16; 'header:In-Reply-To:1': 0.21; 'memory': 0.22; 'objects': 0.23; "doesn't": 0.25; 'index': 0.25; 'stored': 0.25; 'object': 0.26; 'elements': 0.29; "python's": 0.29; 'array': 0.30; 'table.': 0.30; 'looks': 0.31; 'equal': 0.31; 'usage': 0.32; 'filled': 0.32; 'header:X -Complaints-To:1': 0.32; 'to:addr:python-list': 0.33; 'it?': 0.33; 'header:User-Agent:1': 0.35; 'table': 0.37; 'think': 0.38; 'received:org': 0.38; 'could': 0.38; 'but': 0.38; 'subject:: ': 0.38; 'christian': 0.39; 'header:Mime-Version:1': 0.39; 'to:addr:python.org': 0.39; 'your': 0.60; 'schrieb': 0.84; 'spell': 0.91
X-Injected-Via-Gmane	http://gmane.org/
To	python-list@python.org
From	Christian Heimes <lists@cheimes.de>
Subject	Re: hash values and equality
Date	Fri, 20 May 2011 21:01:22 +0200
References	<4DD2C2A5.3080403@stoneleaf.us> <BANLkTimvzZeN5dmm2xHP5xV8Kpw2Nb9kuQ@mail.gmail.com> <4DD2D89D.4000303@stoneleaf.us> <BANLkTintqgBLFtBx8+1b+R10nywuKdKHOw@mail.gmail.com> <4DD2F661.2050005@stoneleaf.us> <BANLkTikx8U4jWwLXXazpmtsL6MasDmyVyg@mail.gmail.com> <BANLkTi=_GqrNntRU7pv7x=kj3gHurk-Gaw@mail.gmail.com> <mailman.1822.1305870290.9059.python-list@python.org> <0deha8-6u9.ln1@satorlaser.homedns.org> <4DD68DAA.9050209@mrabarnett.plus.com>
Mime-Version	1.0
Content-Type	text/plain; charset=ISO-8859-1
Content-Transfer-Encoding	7bit
X-Gmane-NNTP-Posting-Host	f049071189.adsl.alicedsl.de
User-Agent	Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110424 Lightning/1.0b2.102ipre2 Thunderbird/3.1.10
In-Reply-To	<4DD68DAA.9050209@mrabarnett.plus.com>
X-Enigmail-Version	1.1.2
OpenPGP	id=AD16AB1B; url=http://cheimes.de/heimes.asc
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.12
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.1855.1305918095.9059.python-list@python.org> (permalink)
Lines	18
NNTP-Posting-Host	82.94.164.166
X-Trace	1305918096 news.xs4all.nl 49038 [::ffff:82.94.164.166]:58951
X-Complaints-To	abuse@xs4all.nl
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:5873

Show key headers only | View raw

Am 20.05.2011 17:50, schrieb MRAB:
> Is this strictly true? I thought that the hash value, an integer, is
> moduloed (Is that how you spell it? Looks weird!) with the number of
> array elements to give an index into the array, so different hashes
> could give the same index, and objects with different hashes could be
> stored in the same 'bucket'.

I don't think 'moduloed' is an existing word but your description is
mostly correct. The hash of the object and length of the hash table are
used to calculate the position in the hash table. However Python's
implementation doesn't use buckets to reduce memory usage and pointer
dereferencing. If a slot in the hash table is already filled with an
object that is not equal to the new object (a collision), the hash is
shifted and the new slot is checked. The implementation detail is well
described in Modules/dictobject.c.

Christian

Thread

hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-19 22:43 -0700
  Re: hash values and equality Peter Otten <__peter__@web.de> - 2011-05-20 08:38 +0200
    Re: hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-20 10:57 -0700
    Re: hash values and equality Peter Otten <__peter__@web.de> - 2011-05-20 22:25 +0200
    Re: hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-20 14:48 -0700
  Re: hash values and equality Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2011-05-20 08:33 +0200
    Re: hash values and equality MRAB <python@mrabarnett.plus.com> - 2011-05-20 16:50 +0100
    Re: hash values and equality Chris Angelico <rosuav@gmail.com> - 2011-05-21 02:20 +1000
    Re: hash values and equality Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 11:59 -0600
    Re: hash values and equality Ethan Furman <ethan@stoneleaf.us> - 2011-05-20 11:38 -0700
      Re: hash values and equality Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-21 20:24 +1200
        Re: hash values and equality Peter Otten <__peter__@web.de> - 2011-05-21 11:24 +0200
    Re: hash values and equality Christian Heimes <lists@cheimes.de> - 2011-05-20 21:01 +0200
    Re: hash values and equality MRAB <python@mrabarnett.plus.com> - 2011-05-20 21:17 +0100
      Re: hash values and equality Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-21 00:47 +0000
        Re: hash values and equality MRAB <python@mrabarnett.plus.com> - 2011-05-21 02:02 +0100
          Re: hash values and equality Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-21 01:55 +0000
    Re: hash values and equality John Nagle <nagle@animats.com> - 2011-05-21 15:55 -0700
      Re: hash values and equality Irmen de Jong <irmen.NOSPAM@xs4all.nl> - 2011-05-22 01:07 +0200
      Re: hash values and equality Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-22 00:24 +0000

csiph-web