Search by keyword:

Astronomy

Chemistry

Classical Physics

Climate Change

Cosmology

Finance and Accounting

General Relativity

Lagrangian and Hamiltonian Mechanics

Macroeconomics

Mathematics

Microeconomics

Particle Physics

Probability and Statistics

Programming and Computer Science

Quantum Field Theory

Quantum Mechanics

Semiconductor Reliability

Solid State Electronics

Special Relativity

Statistical Mechanics

String Theory

Superconductivity

Supersymmetry (SUSY) and Grand Unified Theory (GUT)

test

The Standard Model

Topology

Units, Constants and Useful Formulas

Hashing

--------

Hashing is the transformation of a string of characters of arbitrary length into a usually
shorter fixed-length value or key that represents the original string. Hashing is used to
index and retrieve items in a database/array because it is faster to find the item using
the shorter hashed key than to find it by searching character-by-character across the
original string. It is also used in many encryption algorithms.

A collision can occur in a situation when two distinct pieces of data have the same
hash value. Collisions are likely whenever members of a very large set are mapped
to a relatively short bit string. The impact of collisions depends on the application.
In some cases such as DNA analysis the hashing functions are designed to
maximize the probability of collision between distinct but similar data. On the other
hand, when analyzing checksums for example, it is desirable to construct functions
that minimize the probability.

Most hash table implementations have some kind of collision resolution strategy to
handle such events. There are 2 basic methods. The first method is to use a data
structure such as a linked list to store multiple items that hash to the same slot.
The second method is to search for other slots using a second function and store
the item in the first empty slot found.