5 Replies - 810 Views - Last Post: 24 June 2013 - 09:13 PM Rate Topic: -----

#1 Connectification  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 02-June 13

Hashing in Python?

Posted 19 June 2013 - 11:12 PM

I am having a trouble of understanding the application of hashing. I vaguely get that it is something like create a bucket list that will linked to element in other lists so we can do a more effective searching.

The professor gave out a hashing program like this
def create():
    global numBuckets
    hSet = []
    for i in range(numBuckets):
        hSet.append([])

def hashElem():
    global numBucket
    return e % numBuckets ## Why did he do it???

def insert(hSet, i):
    global numBucket
    hSet[hashElem(i)].append(i)

def remove(hSet, i):
    newBucket = []
    for j in hSet[hashElem(i)]
        if j != i:
           newBucket.append(j)
    hSet[hashElem(i)] = newBucket

def member(hSet, i):
    return i in hSet[hashElem(i)]



That's about it. It would be great if you guys can explain for me the functionality of this program and give me some explanations so I can fully understand hashing. Thank you

Is This A Good Question/Topic? 0
  • +

Replies To: Hashing in Python?

#2 chan 06  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 63
  • Joined: 07-October 12

Re: Hashing in Python?

Posted 19 June 2013 - 11:39 PM

Hashing is this symbol # that represents comments for your program.

However what you meant was modulus symbol %.

Very basic way to explain is: it is the remainder when you divide two numbers.

An example is:
a = 4
b = 2
print(a%B)/>


You would realize that you will get the value 0 back. Since 4 divide by 2 gives you 2 therefore no remainder is left.

This post has been edited by chan 06: 19 June 2013 - 11:39 PM

Was This Post Helpful? -2
  • +
  • -

#3 Mekire  Icon User is offline

  • D.I.C Head

Reputation: 116
  • View blog
  • Posts: 212
  • Joined: 11-January 13

Re: Hashing in Python?

Posted 20 June 2013 - 12:26 AM

chan 06 said:

Hashing is this symbol # that represents comments for your program.

The op is actually referring to hash tables.
Other than that I'm not certain quite what's going on here as there are a number of strange things; e was never defined; the use of the global keyword does nothing here; the create function returns None.

Were these meant to be part of a class?

-Mek
Was This Post Helpful? 0
  • +
  • -

#4 Connectification  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 02-June 13

Re: Hashing in Python?

Posted 20 June 2013 - 02:33 AM

I'm sorry for not being clearer. It's hashing that I was asking about, not hash. It is something like this:

http://stackoverflow...thon-dictionary
http://www.teachingt...pt_name=Hashing

The program that I copied above supposed to be a program that use hashing to do an effective search in a list. But I have no idea how it work
Was This Post Helpful? 0
  • +
  • -

#5 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7807
  • View blog
  • Posts: 13,200
  • Joined: 19-March 11

Re: Hashing in Python?

Posted 24 June 2013 - 08:56 PM

View Postchan 06, on 20 June 2013 - 01:39 AM, said:

Hashing is this symbol # that represents comments for your program.

However what you meant was modulus symbol %.

Very basic way to explain is: it is the remainder when you divide two numbers.

An example is:
a = 4
b = 2
print(a%B)/>/>


You would realize that you will get the value 0 back. Since 4 divide by 2 gives you 2 therefore no remainder is left.



If you don't know, don't guess.
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7807
  • View blog
  • Posts: 13,200
  • Joined: 19-March 11

Re: Hashing in Python?

Posted 24 June 2013 - 09:13 PM

Think of a hash function as a function mapping a large range of values to a much smaller set, in such a way as to produce as even a distribution across the smaller range as possible.
The mapping must be consistent, but it should ideally look random, in that no "bucket" should be favored.

One simple technique for doing this, generally the first one you'll come across, is to convert the object in question into an integer in some fashion (this is itself can be a problem requiring some thought) and then multiplying the result by some prime greater than the size of the range you want to hash into. The result of that multiplication, modulo the size of the range, produces a reasonably even distribution.

For example, if you wanted to hash the integers from 0..100 into 10 "slots", you could use the hash function:

h(n) = (n*33) % 10

I hope this helps you start to understand the code you're playing with. Experiment with the math a little if you're still having trouble.
Was This Post Helpful? 3
  • +
  • -

Page 1 of 1