hash
Get flash to fully experience Pearltrees
Timer Hash
Abstract Real-time ORBs and their applications require predictable, efficient, and flexible timer support. Conventional methods of implementing timer strategies do not provide adequate predictability and scalability. This paper describes the design, performance, and optimizations for building a family of timer strategies that are targeted for various types of real-time applications. This paper makes several contributions to the design and optimization of real-time Timer strategies. First, we adapted a interrupt driven timer queue to work with a non-interrupt driven model.
Eternally Confuzzled - The Art of Hashing
I n Binary Search Trees I, II, and III, we considered methods for efficient searching of an ordered collection by using key comparisons. While these methods were indeed very fast, they were limited to O(log N) performance due to the comparison tree inherent in the data structure. Binary search trees are also somewhat complicated, especially when the chance of encountering a degenerate tree is minimized, or removed entirely. A n alternative method for searching uses they key itself an an address into the data structure, thus breaking the O(log N) barrier and allowing searches to be performed with an expected time complexity of O(1), which is as good as it gets when it comes to searching, and algorithms in general. U nfortunately, not all keys are easily used as a table address.
Hash functions are by definition and implementation pseudo random number generators (PRNG). From this generalization its generally accepted that the performance of hash functions and also comparisons between hash functions can be achieved by treating hash function as PRNGs. Analysis techniques such a Poisson distribution can be used to analyze the collision rates of different hash functions for different groups of data. In general there is a theoretical hash function known as the perfect hash function for any group of data. The perfect hash function by definition states that no collisions will occur meaning no repeating hash values will arise from different elements of the group. In reality its very difficult to find a perfect hash function and the practical applications of perfect hashing and its variant minimal perfect hashing are quite limited.
.:: General Purpose Hash Function Algorithms - By Arash Partow ::.
Perfect hashing guarantees that you get no collisions at all. It is possible when you know exactly what set of keys you are going to be hashing when you design your hash function. It's popular for hashing keywords for compilers.
Perfect Hashing
CMPH - C Minimal Perfect Hashing Library
Motivation A perfect hash function maps a static set of n keys into a set of m integer numbers without collisions, where m is greater than or equal to n. If m is equal to n, the function is called minimal. Minimal perfect hash functions are widely used for memory efficient storage and fast retrieval of items from static sets, such as words in natural languages, reserved words in programming languages or interactive systems, universal resource locations (URLs) in Web search engines, or item sets in data mining techniques. Therefore, there are applications for minimal perfect hash functions in information retrieval systems, database systems, language translation systems, electronic commerce systems, compilers, operating systems, among others.