Welchen Hash Algorithmus verwendet Perl? (Allgemeines zu Perl)

[thread]15224[/thread]

Welchen Hash Algorithmus verwendet Perl?

Leser: 23

Articles: hide open all | hide show old branches

+14 replies
pope

2010-06-30 13:59

User since
2009-10-11
30 Artikel
BenutzerIn

Hi Leute,

kurze Frage. Welchen Hash Algorithmus verwendet Perl? B*-Baum?

Beschreibungen über die internen Abläufe von Perl zu finden ist manchmal ganz schön schwierig.
- +4 replies
- lichtkind
  
  2010-06-30 15:07
  
  User since
  2004-03-22
  5679 Artikel
  ModeratorIn + EditorIn
  
  dächte mal gelesen zu haben Rot-Schwarz-Baum aber siehs mal als unbestätigten rumor
  Last edited: 2010-06-30 15:08:54 +0200 (CEST)
  Tutorien in der Wiki, mein zeug:
  kephra, baumhaus, garten, gezwitscher
  
  Es beginnt immer mit einer Entscheidung.
  - +2 replies
  - pope
    
    2010-06-30 15:19
    
    User since
    2009-10-11
    30 Artikel
    BenutzerIn
    
    ja, du scheinst recht zu haben: http://www.perl.com/lpt/a/679. Wird zwar nicht direkt gesagt, aber der Satz im Abschnitt "Nomenclature" impliziert das in Bezug auf die Aussagen des Abschnittes "Implementing Dictionaries".
    
    Danke
    Last edited: 2010-06-30 15:23:43 +0200 (CEST)
    - murphy
      
      2010-06-30 15:55
      
      User since
      2004-07-19
      1776 Artikel
      HausmeisterIn
      
      Der verlinkte Artikel beschreibt aber überhaupt nicht die Implementation eines Red-Black-Trees, sondern die gewöhnlicher Hashtables!
      When C++ is your hammer, every problem looks like your thumb.
  - murphy
    
    2010-06-30 16:07
    
    User since
    2004-07-19
    1776 Artikel
    HausmeisterIn
    
    Ich glaube, es wurde mal darüber nachgedacht, Red-Black-Trees zu verwenden, weil die Performance im ungünstigsten Fall besser wäre als bei Hashtables.
    
    Durch das Zufallselement in der Hashfunktion vermeidet man aber auch mit großer Wahrscheinlichkeit Komplexitätsprobleme. Und in weniger pathologischen Fällen können Hashtables halt auch schneller als Red-Black-Trees sein.
    When C++ is your hammer, every problem looks like your thumb.
- +9 replies
- murphy
  
  2010-06-30 15:50
  User since
  2004-07-19
  1776 Artikel
  HausmeisterIn
  Ein B-Baum ist kein Hashalgorithmus, sondern eine Datenstruktur, die ähnlich wie ein Hash zur Implementation assoziativer Arrays verwendet werden kann.
  
  Perl verwendet zur Implementation seiner Hashes meines Wissens tatsächlich gewöhnliche Hashtables mit verlinkten Listen als Datenstruktur der Buckets. Ein kurzer Blick in hv.h und hv.c aus der Quellcodedistribution von Perl 5.12.1 bestätigt diese Hypothese.
  
  Die verwendete Hashfunktion ist eine einfache Bitpermutation:
  
  Code (C): (dl )
  
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  
  #define PERL_HASH(hash,str,len) \ STMT_START { \ register const char * const s_PeRlHaSh_tmp = str; \ register const unsigned char *s_PeRlHaSh = (const unsigned char *)s_PeRlHaSh_tmp; \ register I32 i_PeRlHaSh = len; \ register U32 hash_PeRlHaSh = PERL_HASH_SEED; \ while (i_PeRlHaSh--) { \ hash_PeRlHaSh += *s_PeRlHaSh++; \ hash_PeRlHaSh += (hash_PeRlHaSh << 10); \ hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); \ } \ hash_PeRlHaSh += (hash_PeRlHaSh << 3); \ hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); \ (hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); \ } STMT_END
  
  Der Wert PERL_HASH_SEED wird beim Start des Interpreters in der Regel zufällig gewählt und dient dazu, die Hashfunktion zu randomisieren um Komplexitätsattacken auf Perls Hashes zu erschweren.
  When C++ is your hammer, every problem looks like your thumb.
  - +8 replies
  - pope
    
    2010-06-30 16:52
    
    User since
    2009-10-11
    30 Artikel
    BenutzerIn
    
    Ah, habs glaub ich so halbwegs kapiert.
    
    Es ging mir um eine Begründung, warum für das Suchen eines Wortes in einer Menge aus Wörten (z.B. in meinem Fall einem Dictionary) ein Hash viel sinnvoller und schneller ist als eine Liste o.ä.
    - +7 replies
    - esskar
      
      2010-06-30 17:07
      
      User since
      2003-08-04
      7321 Artikel
      ModeratorIn
      
      wenn du diese liste sortiert hälst, reicht eine binäre suche.
      - +6 replies
      - pope
        
        2010-06-30 17:10
        
        User since
        2009-10-11
        30 Artikel
        BenutzerIn
        
        Aber warum sich mühe machen, wenn eine solche Datenstruktur schon vorhanden ist und einfach mit
        
        Code (perl): (dl )
        
        1 2
        
        @_ = <FH>; @Dict{ @_ } = ( );
        
        erstellt werden und anschliesend mit
        
        Code (perl): (dl )
        
        exists $Dict{ $Word }
        
        durchsucht werden kann?
        
        EDIT:
        Obwohl... das Wörterbuch ist bereits sortiert. Sollte man sich vllt doch Gedanken drüber machen.
        Last edited: 2010-06-30 17:15:18 +0200 (CEST)
        
        +5 replies
        
        esskar
        
        2010-06-30 17:25
        
        User since
        2003-08-04
        7321 Artikel
        ModeratorIn
        
        wie gross ist denn dein dictionary?
        
        +4 replies
        
        pope
        
        2010-06-30 17:39
        
        User since
        2009-10-11
        30 Artikel
        BenutzerIn
        
        ~310 000 Wörter
        
        +3 replies
        
        esskar
        
        2010-06-30 22:08
        
        User since
        2003-08-04
        7321 Artikel
        ModeratorIn
        
        hmm. wie sieht das denn im speicher aus, wenn du da alle reinlädst. ist ja nicht wenig!
        
        +2 replies
        
        pope
        
        2010-07-01 07:09
        
        User since
        2009-10-11
        30 Artikel
        BenutzerIn
        
        Hm, ich weiss jetzt nicht so genau was du meinst.
        
        Die Anwendung braucht 50 MB, da werden aber auch noch andere Module geladen. Das Dictionary selbst ist als Datei 4 MB groß, wird im Speicher dann wohl noch etwas mehr sein, wenns strukturiert wurde.
        
        esskar
        
        2010-07-01 09:30
        
        User since
        2003-08-04
        7321 Artikel
        ModeratorIn
        
        nee, dann passts. würde es wohl selber in einem array halten und mit binary-search drin suchen und (ggf. einfügen).

View all threads created 2010-06-30 13:59.