Question

I am on lecture 9 but I couldn't understand "Hashing". Can anyone explain it to me??

Answer 1

there is a great wikipedia article:
http://en.wikipedia.org/wiki/Hash_function

i'll take a stab at it but the first para of the wikipedia article is probably better - it's a way to encode something as a number by running the various parts of the thing thru a mathematical function.

Answer 2

Thanks bwCA...
now its quite clear to me.
in particular the following ppt was helpful:
http://www.cis.upenn.edu/~matuszek/cit594-2005/Lectures/18-hashing.ppt

Answer 3

Basically, if you are trying to find out if a particular object exists in a normal list or tuple, you need to scan through that list/tuple one object at a time.
for example, take the list x = [1, 2, 3]
lets say i want to write a program that will tell me whether the number 3 is in this list, it would look like this:

def isinlist(searchvalue, list):
for n in range(len(list)):
if list[n] == searchvalue:
return(True)
else:
return(False)

So, the program would look at each element in the list and return true if it matches it with the element you're looking for. This method works, but is incredibly incredibly slow if you have a massive list.

Hashing on the other hand avoids the issue of looking at every element in the list.
If you make a list, like the one above. You'll notice that you can instantly go to any element in the list as long as you know it's location. like: i could type print(x[2]) and it would print '3'. no lag time since we dont have to go looking for it.
Hashing takes advantage of the speed that goes with knowing the location, but at the cost of a very large amount of storage.

A hash map (put simply) is a massive list. lets say 100 elements (arbitrary number). By default each of these 100 elements is set equal to 0. Now if i want to add a number to my "list" lets say '50', the program would go to the 50th element and turn that 0 into a 1. Later, i want to check if the number '50' is in this "list" the program would simply go to the 50th element and check if there is a 1 or a 0. if there is a 1, it will return True, if there is a 0 False.

Answer 4

Thanks anishray... pretty good answre.

Answer 5

http://wiki.python.org/moin/DictionaryKeys

A dictionary in Python is like a hash in Perl 5. In Perl 5, variables that store hashes always start with a % character. In Python, variables can be named anything, and Python keeps track of the datatype internally. Creating a dictionary is easy. The syntax is similar to sets, but instead of values, you have key-value pairs. Once you have a dictionary, you can look up values by their key.