| dbo:abstract
|
- Dokonalá (perfektní) hašovací funkce množiny S je taková hašovací funkce, která mapuje vzdálené elementy v množině S na množinu celých čísel tak, aby nedošlo ke kolizím klíčů. Dokonalá hašovací funkce podporuje mnoho aplikací stejných jako jiné hašovací funkce, ale bez nutnosti implementace řešení kolize. Použití dokonalé hašovací funkce je vhodné v takových případech, kdy jsou data, která chceme zmapovat, uložena v úložišti, ve kterém se často hledá a méně často se do něj zapisuje. Dokonalé hašování s sebou nese ale poměrně vysokou složitost a tím snižuje výkon aplikace. Matematickým výrazem lze dokonalou hašovací funkci vyjádřit jako úplné prosté zobrazení. (cs)
- Eine perfekte Hash-Funktion ist eine Hashfunktion , die unterschiedliche Elemente aus einer endlichen und festen Schlüsselmenge auf unterschiedliche Elemente aus einer Bildmenge abbildet (keine Kollisionen, Injektivität). Aus der Injektivität ergibt sich ein wichtiger Vorteil: Auf ein Element einer Hashtabelle, die mit einer perfekten Hash-Funktion erstellt wurde, kann im worst Case in konstanter Zeit zugegriffen werden. Eine perfekte Hash-Funktion heißt minimal, wenn , d. h. . Das bedeutet, dass die Bildmenge der Funktion genauso viele Elemente wie die Urbildmenge hat. In der Praxis senkt dies den Speicherbedarf des Arrays, das die Elemente für jedes mit speichert, auf das Minimum. Im Gegensatz zu nicht perfektem Hashing, das amortisiert Zugriffszeit benötigt und im worst Case , bietet perfektes Hashing selbst im worst Case einen Zugriff auf die Elemente in konstanter Zeit , ist also deutlich schneller. Dies wird erreicht, indem die Werte der Schlüssel in einem von bis indizierten Array an der Position gespeichert werden; im Gegensatz zu normalem Hashing enthält jeder Eimer (Bucket) aufgrund der Injektivität von also nur genau ein Element. Dafür bezahlt man mit Rechenzeit, um die Hashfunktion zu konstruieren, und benötigt mehr Speicherplatz. In der Praxis sucht man Hashfunktionen mit folgenden Eigenschaften:
* Konstruktion in Zeit, d. h. mit wachsender Schlüsselanzahl steigt die Zeit der Konstruktion linear.
* Evaluation in , d. h. nach Konstruktion kann man einen Schlüssel in konstanter Zeit auf einen Index abbilden.
* Die Hashfunktion benötigt möglichst wenig Speicher.
* Die Hashfunktion soll minimal perfekt sein. Derzeit gängige minimal perfekte Hashfunktionen arbeiten in Zeit zur Konstruktion und benötigen mindestens 1,56 Bit pro Schlüssel. (Minimale) perfekte Hashfunktionen sind in der Praxis dann angebracht, wenn:
* es eine feste Schlüsselmenge gibt, der jeweils Werte zugeordnet sind (bei sich ständig ändernden Schlüsselmengen wäre eine ständige Neukonstruktion zu zeitintensiv),
* genug Zeit vorhanden ist, um die Hashfunktion zu konstruieren,
* auf die Werte ein Zugriff in konstanter Zeit benötigt wird,
* zusätzlicher Speicher für die Hashfunktion vorhanden ist. (de)
- In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective function. Perfect hash functions may be used to implement a lookup table with constant worst-case access time. A perfect hash function can, as any hash function, be used to implement hash tables, with the advantage that no collision resolution has to be implemented. In addition, if the keys are not the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space. Disadvantages of perfect hash functions are that S needs to be known for the construction of the perfect hash function. Non-dynamic perfect hash functions need to be re-constructed if S changes. For frequently changing S dynamic perfect hash functions may be used at the cost of additional space. The space requirement to store the perfect hash function is in O(n). The important performance parameters for perfect hash functions are the evaluation time, which should be constant, the construction time, and the representation size. (en)
- 对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致，但不需要任何冲突解决方案。在数学术语中，这是一个单射函数. (zh)
|
| rdfs:comment
|
- Dokonalá (perfektní) hašovací funkce množiny S je taková hašovací funkce, která mapuje vzdálené elementy v množině S na množinu celých čísel tak, aby nedošlo ke kolizím klíčů. Dokonalá hašovací funkce podporuje mnoho aplikací stejných jako jiné hašovací funkce, ale bez nutnosti implementace řešení kolize. Použití dokonalé hašovací funkce je vhodné v takových případech, kdy jsou data, která chceme zmapovat, uložena v úložišti, ve kterém se často hledá a méně často se do něj zapisuje. Dokonalé hašování s sebou nese ale poměrně vysokou složitost a tím snižuje výkon aplikace. Matematickým výrazem lze dokonalou hašovací funkci vyjádřit jako úplné prosté zobrazení. (cs)
- 对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致，但不需要任何冲突解决方案。在数学术语中，这是一个单射函数. (zh)
- Eine perfekte Hash-Funktion ist eine Hashfunktion , die unterschiedliche Elemente aus einer endlichen und festen Schlüsselmenge auf unterschiedliche Elemente aus einer Bildmenge abbildet (keine Kollisionen, Injektivität). Aus der Injektivität ergibt sich ein wichtiger Vorteil: Auf ein Element einer Hashtabelle, die mit einer perfekten Hash-Funktion erstellt wurde, kann im worst Case in konstanter Zeit zugegriffen werden. In der Praxis sucht man Hashfunktionen mit folgenden Eigenschaften: (Minimale) perfekte Hashfunktionen sind in der Praxis dann angebracht, wenn: (de)
- In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective function. Disadvantages of perfect hash functions are that S needs to be known for the construction of the perfect hash function. Non-dynamic perfect hash functions need to be re-constructed if S changes. For frequently changing S dynamic perfect hash functions may be used at the cost of additional space. The space requirement to store the perfect hash function is in O(n). (en)
|
