Jump to content
  • Advertisement
Sign in to follow this  
koka282

I do not understand the code (Hashtable)

This topic is 1472 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

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

i will try again ....

 

 

Thanks

Edited by koka282

Share this post


Link to post
Share on other sites
Advertisement

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 GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!