Ändern Sie die Hash-Funktion eines Wörterbuchs

Question

Nach diesem question, wissen wir, dass zwei verschiedene Wörterbücher, und dict_2 zum Beispiel die exakt gleiche Hash-Funktion verwenden.

Gibt es eine Möglichkeit, die vom Wörterbuch verwendete Hash-Funktion zu ändern? _{Negative Antworten auch angenommen!}

Answer 1

Sie können die Hash-Funktion nicht ändern - das Dict ruft hash auf den Schlüsseln auf, die es einfügen soll, und das ist es.

Sie können jedoch die Schlüssel umhüllen, um verschiedene __hash__ und __eq__ -Methoden bereitzustellen.

class MyHash(object): 
    def __init__(self, v): 
     self._v = v 

    def __hash__(self): 
     return hash(self._v) * -1 

    def __eq__(self, other): 
     return self._v == other._v 

Wenn dies tatsächlich etwas mit Ihrer ursprünglichen Problem/Frage hilft ich allerdings bezweifeln, so scheint es eher eine benutzerdefinierte Liste/Arrays basierende Datenstruktur könnte die Antwort sein. Oder nicht.

Answer 2

Hier ist eine "Hash-Tabelle" über einer Liste von Listen, wobei jedes Hash-Tabellenobjekt mit einer bestimmten Hash-Funktion verknüpft ist.

class HashTable(object): 
    def __init__(self, hash_function, size=256): 
     self.hash_function = hash_function 
     self.buckets = [list() for i in range(size)] 
     self.size = size 

    def __getitem__(self, key): 
     hash_value = self.hash_function(key) % self.size 
     bucket = self.buckets[hash_value] 
     for stored_key, stored_value in bucket: 
      if stored_key == key: 
       return stored_value 
     raise KeyError(key) 


    def __setitem__(self, key, value): 
     hash_value = self.hash_function(key) % self.size 
     bucket = self.buckets[hash_value] 
     i = 0 
     found = False 
     for stored_key, stored_value in bucket: 
      if stored_key == key: 
       found = True 
       break 
      i += 1 
     if found: 
      bucket[i] = (key, value) 
     else: 
      bucket.append((key, value)) 

Der Rest Ihrer Anwendung kann immer noch die zugrunde liegende Liste der Buckets sehen. Ihre Anwendung erfordert möglicherweise zusätzliche Metadaten, die jedem Bucket zugeordnet werden. Dies wäre jedoch so einfach wie das Definieren einer neuen Klasse für die Elemente der Bucket-Liste anstelle einer einfachen Liste.

Answer 3

Ich denke, was Sie wollen, ist eine Möglichkeit, Eimer zu erstellen. Basierend darauf empfehle ich collections.defaultdict mit einem Initialisierer set als "Eimer" (hängt davon ab, wofür Sie es verwenden). Hier

ist ein Beispiel:

#!/usr/bin/env python 

from collections import defaultdict 
from itertools import combinations 

d = defaultdict(set) 

strs = ["str", "abc", "rts"] 
for s in strs: 
    d[hash(s)].add(s) 
    d[hash(''.join(reversed(s)))].add(s) 

for combination in combinations(d.values(), r=2): 
    matches = combination[0] & combination[1] 
    if len(matches) > 1: 
     print matches 

# output: set(['str', 'rts']) 

Zwei Strings in den gleichen Eimer hier sind sehr wahrscheinlich die gleiche endet. Ich habe eine Hash-Kollision erstellt, indem ich die umgekehrte Funktion benutze und eine Zeichenfolge verwende, die als Werte umgekehrt ist.

Beachten Sie, dass das Set den vollständigen Vergleich verwendet, aber es sollte sehr schnell gehen.

Hash nicht zu viele Werte, ohne die Sätze zu leeren.