Apa cara yang benar dan bagus untuk mengimplementasikan __hash __ ()?

Apa cara yang benar dan bagus untuk diterapkan __hash__()?

Saya berbicara tentang fungsi yang mengembalikan kode hash yang kemudian digunakan untuk menyisipkan objek ke dalam tagar alias kamus.

Ketika __hash__()mengembalikan integer dan digunakan untuk "binning" objek ke dalam hashtable, saya berasumsi bahwa nilai integer yang dikembalikan harus terdistribusi secara seragam untuk data umum (untuk meminimalkan benturan). Apa praktik yang baik untuk mendapatkan nilai seperti itu? Apakah tabrakan merupakan masalah? Dalam kasus saya, saya memiliki kelas kecil yang bertindak sebagai kelas wadah memegang beberapa int, beberapa mengapung dan tali.

Cara mudah dan benar untuk diterapkan __hash__()adalah dengan menggunakan kunci tuple. Ini tidak akan secepat hash khusus, tetapi jika Anda membutuhkannya maka Anda mungkin harus mengimplementasikan tipe dalam C.

Berikut adalah contoh menggunakan kunci untuk hash dan kesetaraan:

class A:
    def __key(self):
        return (self.attr_a, self.attr_b, self.attr_c)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        if isinstance(other, A):
            return self.__key() == other.__key()
        return NotImplemented

Juga, dokumentasi__hash__ memiliki lebih banyak informasi, yang mungkin berharga dalam beberapa keadaan tertentu.

John Millikin mengusulkan solusi yang mirip dengan ini:

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

Masalah dengan solusi ini adalah bahwa hash(A(a, b, c)) == hash((a, b, c)). Dengan kata lain, hash bertabrakan dengan hasrat anggota kunci. Mungkin ini tidak terlalu penting dalam praktek?

Perbarui: dokumen Python sekarang merekomendasikan untuk menggunakan tuple seperti pada contoh di atas. Perhatikan bahwa dokumentasi menyatakan

Satu-satunya properti yang diperlukan adalah objek yang membandingkan sama memiliki nilai hash yang sama

Perhatikan bahwa yang terjadi adalah sebaliknya. Objek yang tidak membandingkan sama mungkin memiliki nilai hash yang sama. Tabrakan hash seperti itu tidak akan menyebabkan satu objek untuk menggantikan yang lain ketika digunakan sebagai kunci dict atau mengatur elemen selama objek tidak juga sama .

Solusi usang / buruk

The dokumentasi Python pada__hash__ menyarankan untuk menggabungkan hash dari sub-komponen menggunakan sesuatu seperti XOR , yang memberi kami ini:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Pembaruan: seperti yang ditunjukkan Blckknght, mengubah urutan a, b, dan c dapat menyebabkan masalah. Saya menambahkan tambahan ^ hash((self._a, self._b, self._c))untuk menangkap urutan nilai yang di-hash. Final ini ^ hash(...)dapat dihapus jika nilai-nilai yang digabungkan tidak dapat disusun ulang (misalnya, jika mereka memiliki tipe yang berbeda dan karena itu nilai _atidak akan pernah ditugaskan _batau _c, dll.).

Paul Larson dari Microsoft Research mempelajari berbagai fungsi hash. Dia memberitahuku itu

for c in some_string:
    hash = 101 * hash  +  ord(c)

bekerja sangat baik untuk berbagai string. Saya telah menemukan bahwa teknik polinomial serupa bekerja dengan baik untuk menghitung hash dari subfield yang berbeda.

Saya dapat mencoba menjawab bagian kedua dari pertanyaan Anda.

Tabrakan mungkin akan menghasilkan bukan dari kode hash itu sendiri, tetapi dari memetakan kode hash ke indeks dalam koleksi. Jadi misalnya fungsi hash Anda dapat mengembalikan nilai acak dari 1 hingga 10.000, tetapi jika tabel hash Anda hanya memiliki 32 entri, Anda akan mendapatkan tabrakan pada penyisipan.

Selain itu, saya akan berpikir bahwa tabrakan akan diselesaikan oleh koleksi secara internal, dan ada banyak metode untuk menyelesaikan tabrakan. Yang paling sederhana (dan terburuk) adalah, diberi entri untuk disisipkan di indeks i, tambahkan 1 ke i sampai Anda menemukan tempat kosong dan masukkan di sana. Pengambilan kemudian bekerja dengan cara yang sama. Ini menghasilkan pengambilan yang tidak efisien untuk beberapa entri, karena Anda dapat memiliki entri yang memerlukan melintasi seluruh koleksi untuk menemukan!

Metode resolusi tabrakan lainnya mengurangi waktu pengambilan dengan memindahkan entri dalam tabel hash ketika item dimasukkan untuk menyebarkan hal-hal. Ini meningkatkan waktu penyisipan tetapi mengasumsikan Anda membaca lebih dari yang Anda masukkan. Ada juga metode yang mencoba dan bercabang entri bertabrakan yang berbeda sehingga entri ke cluster di satu tempat tertentu.

Juga, jika Anda perlu mengubah ukuran koleksi, Anda harus mengulangi semuanya atau menggunakan metode hashing dinamis.

Singkatnya, tergantung pada apa yang Anda gunakan kode hash untuk Anda mungkin harus menerapkan metode resolusi tabrakan Anda sendiri. Jika Anda tidak menyimpannya dalam koleksi, Anda mungkin bisa pergi dengan fungsi hash yang hanya menghasilkan kode hash dalam rentang yang sangat besar. Jika demikian, Anda dapat memastikan wadah Anda lebih besar dari yang seharusnya (semakin besar semakin baik tentu saja) tergantung pada masalah memori Anda.

Berikut ini beberapa tautan jika Anda lebih tertarik:

penggabungan hashing di wikipedia

Wikipedia juga memiliki ringkasan berbagai metode resolusi tabrakan:

Juga, " Organisasi File dan Pemrosesan " oleh Tharp mencakup banyak metode resolusi tabrakan secara luas. IMO itu referensi yang bagus untuk algoritma hashing.

Penjelasan yang sangat bagus tentang kapan dan bagaimana mengimplementasikan __hash__fungsi ini di situs web programiz :

Hanya tangkapan layar untuk memberikan ikhtisar: (Diperoleh 2019-12-13)

Adapun implementasi metode ini secara pribadi, situs yang disebutkan di atas memberikan contoh yang cocok dengan jawaban millerdev .

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))

Bergantung pada ukuran nilai hash yang Anda kembalikan. Ini logika sederhana bahwa jika Anda perlu mengembalikan int 32bit berdasarkan hash dari empat int 32bit, Anda akan mendapatkan tabrakan.

Saya lebih suka operasi bit. Seperti, kode pseudo C berikut:

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

Sistem seperti itu bisa bekerja untuk float juga, jika Anda hanya menganggapnya sebagai nilai bitnya daripada benar-benar mewakili nilai floating-point, mungkin lebih baik.

Untuk string, saya punya sedikit / tidak tahu.