Próbuję wdrożyć funkcję Hash w Pythonie. Czy uważasz, że następuje prawdziwa funkcja Hash? Mam 10 wiadra i wartości od 1 do 7. będzie również liczyć kwotę kolizji :)

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

EDYTOWAĆ:

Spojrzałem na wszystkie komentarze i próbowałem utworzyć kolejną funkcję Hash. Tym razem używam losowo, aby określić klucze, które mają być zniesienie. Tym razem mam tylko 3 wiadra. Spróbuję z 25 wartościami od 1 do 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]
3
John 1 grudzień 2011, 20:26

5 odpowiedzi

Najlepsza odpowiedź

nie. funkcja Hash musi być określona. Nie może polegać na przypadkowości.

Procedura Hash musi być deterministyczna - co oznacza, że dla danej wartości wejściowej musi zawsze generować tę samą wartość hash. Innymi słowy, musi być funkcją danych zniesienia, w sensie matematycznego terminu. Wymóg ten wyklucza funkcje Hash, które zależą od zewnętrznych parametrów zmiennych, takich jak generatory liczb pseudo-losowych lub pora dnia. Wyklucza również funkcje, które zależą od adresu pamięci wymieszanie obiektu, ponieważ adres ten może się zmieniać podczas wykonywania (jak może wystąpić w systemach, które wykorzystują pewne metody gromadzenia śmieci), chociaż czasami odbieranie elementu jest możliwe).

Źródło: Funkcja Hash - determinizm (Wikipedia)

4
Dennis 1 grudzień 2011, 16:28

Nie, to nie jest funkcja Hash. Funkcja Hash dana wejście powinna podać taką samą wydajność przez siebie.

Zamiast budować własną funkcję hash, dlaczego nie używać hash w samym Pythonie. Python ma wbudowany wdrożenie Hash.

>>> hash("xyz")
-5999452984703080694

Więc zamiast używać list Użyj dict za pomocą {{x2} Collusy można łatwo wykryć.

1
Srikar Appalaraju 1 grudzień 2011, 16:35

Funkcja Hash musi podać taką samą wyjście dla tego samego wejścia ... Wystarczy daje losową liczbę. Więc nie sądzę, że to prawdziwa funkcja Hash, nie.

0
Claudiu 1 grudzień 2011, 16:28

Nie Funkcja Hash ma wejście i zwraca wartość deterministyczną. Ta wartość zwracana jest hash.

0
Peter Rowell 1 grudzień 2011, 16:31

Nie, to nie jest funkcja hash. Funkcja Hash mapuje element z większych danych ustawionych na mniejszy. Jest to tylko losowo wkładanie liczb do listy.

0
Chris Lacasse 1 grudzień 2011, 16:31