3

im trying to implement a hash function in python. Would you consider the following a real hash function? I've 10 buckets and values from 1 to 7. It will also count amount of collisions :)

import random A=[1,2,3,4,5,6,7] hashed=[] def func(): i=0 count=0 while len(A)>i: m=random.randint(1,10) # 10 buckets if m in hashed: count+=1 hashed.append(m) print "element:",A[i], "hashed to bucket", m i+=1 print "Amount of collisions:", count func()

Test:

element: 1 hashed to bucket 3 element: 2 hashed to bucket 2 element: 3 hashed to bucket 10 element: 4 hashed to bucket 8 element: 5 hashed to bucket 3 element: 6 hashed to bucket 10 element: 7 hashed to bucket 4 Amount of collisions: 2

EDIT:

I looked at all the comments and tried to create another hash function. This time I use random to determine the keys that are to be hashed. This time i only have 3 buckets. I will try with 25 values that are between 1 and 10:

import random count=[] list1 = [] # bucket 1 list2 = [] # bucket 2 list3 = [] # bucket 3 the_list = [] the_list.append(list1) the_list.append(list2) the_list.append(list3) # using lists within a list def func(): while True: number=random.randint(1,10) i=random.randint(0,len(the_list)-1) the_list[i].append(number) count.append(number) if len(count)>25: # testing for 25 values break func() print "Bucket 1:", the_list[0] print "Bucket 2:", the_list[1] print "Bucket 3:", the_list[2]

Test:

Bucket 1: [5, 9, 8, 10, 3, 10] Bucket 2: [10, 5, 8, 5, 6, 2, 6, 1, 8] Bucket 3: [9, 4, 7, 2, 1, 6, 7, 10, 9, 1, 5]
Improve this question
4
  • How would you figure out where an element went when the time comes to retrieve it? You're introducing randonmess there, and the next time you has '1' it could come back with "bucket 10" instead, but oops... it's really in bucket 3. Commented Dec 1, 2011 at 16:30
  • @John: your test output can't have come from the code you posted. count is local to func(), and you print the collision count before you run func. Here it's easy to see what probably happened, but in general always make sure that you post self-contained examples which generate the output when run on their own. Commented Dec 1, 2011 at 16:35
  • yeah i forgot to create space for the last print, the print statement is inside the func in my program. ty for info though. Commented Dec 1, 2011 at 16:39
  • You don't normally need to implement a hash function in Python anyway because you don't normally need to do anything yourself that hash functions are for. In particular, you don't need to make hashed containers, because there are two built in, called dict (associative mapping) and set (collection with uniqueness constraint). Commented Dec 1, 2011 at 16:47

5 Answers 5

Reset to default
4

No. A hash function has to be deterministic. It cannot rely on randomness.

A hash procedure must be deterministic—meaning that for a given input value it must always generate the same hash value. In other words, it must be a function of the hashed data, in the mathematical sense of the term. This requirement excludes hash functions that depend on external variable parameters, such as pseudo-random number generators or the time of day. It also excludes functions that depend on the memory address of the object being hashed, because that address may change during execution (as may happen on systems that use certain methods of garbage collection), although sometimes rehashing of the item is possible).

Source: Hash function - Determinism (Wikipedia)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

thank you. i was mislead, do you have any advice on how to create a simple hash func in python?
Here's a simple hash function to hash an integer: f(x): return x % 10
@John: Your modified example randomly fills some arrays with integers. There is no input that could be hashed. What do you need the hash function for?
1

No this is not a hash function. Hash function given a input should give same output over & over again.

Instead of building your own hash function why not use hash in python itself. Python has inbuilt hash implementation. 

>>> hash("xyz") -5999452984703080694

So instead of using a list use a dict with hash with key being this hash output. Collusions can be easily detected.

Improve this answer

Comments

0

A hash function needs to give the same output for the same input... yours just gives a random number. So, I don't think it is a real hash function, no.

Improve this answer

Comments

0

No. You are not doing any hashing at all, simply randomly sticking values into an array. A hash function takes an input and returns a deterministic value. That return value is the hash.

Improve this answer

Comments

0

No, this is not a hash function. A hash function maps an element from a larger data set to a smaller one. This is just randomly inserting numbers into a list.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.