Advertisement Jump to content
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

Recommended Posts


i'm learning from

def new(num_buckets=256):
    """Initializes a Map with the given number of buckets."""
    aMap = []
    for i in range(0, num_buckets):
    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)
        # 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]

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 smile.png & sry for asking 

i will try again ....




Edited by koka282

Share this post

Link to post
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

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!