Public Group

# I do not understand the code (Hashtable)

This topic is 1566 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi,

i'm learning from http://learnpythonthehardway.org/book/ex39.html

def new(num_buckets=256):
"""Initializes a Map with the given number of buckets."""
aMap = []
for i in range(0, num_buckets):
aMap.append([])
return aMap

def hash_key(aMap, key):
"""Given a key this will create a number and then convert it to
an index for the aMap's buckets."""
return hash(key) % len(aMap)

def get_bucket(aMap, key):
"""Given a key, find the bucket where it would go."""
bucket_id = hash_key(aMap, key)
return aMap[bucket_id]

def get_slot(aMap, key, default=None):
"""
Returns the index, key, and value of a slot found in a bucket.
Returns -1, key, and default (None if not set) when not found.
"""
bucket = get_bucket(aMap, key)

for i, kv in enumerate(bucket):
k, v = kv
if key == k:
return i, k, v

return -1, key, default

def get(aMap, key, default=None):
"""Gets the value in a bucket for the given key, or the default."""
i, k, v = get_slot(aMap, key, default=default)
return v

def set(aMap, key, value):
"""Sets the key to the value, replacing any existing value."""
bucket = get_bucket(aMap, key)
i, k, v = get_slot(aMap, key)

if i >= 0:
# the key exists, replace it
bucket[i] = (key, value)
else:
# the key does not, append to create it
bucket.append((key, value))

def delete(aMap, key):
"""Deletes the given key from the Map."""
bucket = get_bucket(aMap, key)

for i in xrange(len(bucket)):
k, v = bucket[i]
if key == k:
del bucket[i]
break

def list(aMap):
"""Prints out what's in the Map."""
for bucket in aMap:
if bucket:
for k, v in bucket:
print k, v


i searched for hash function, hash table,hashmap

return hash(key) % len(aMap)

How does it work?

& what he mean with the bucket when i read about hash  i think i couldn't  understand what he mean with bucket

(Given a key this will create a number and then convert it to

an index for the aMap's buckets)

but i want to know how does it work

i run it and tried many times I understood things, and things I did not understand

& if u don't understand what i mean please tell me  & sry for asking

i will try again ....

Thanks

Edited by koka282

##### Share on other sites

In a hashtable, a "bucket" is just a fancy name for an index of the array.  They are also commonly known as "slots."  Other than that "AuthenticOwl" nicely sums up how a hashtable works.

EDIT: And as "AuthenticOwl" mentioned, summing the ASCII values of a string is usually not an ideal approach to hashing as there is a high risk of collision.  Also, if you want to understand how the code works, take it line by line.

Edited by ByteTroll

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 21
• 15
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634097
• Total Posts
3015515
×