<< Chapter < Page Chapter >> Page >

8. hashing

8.1. introduction to hashing algorithms

(From Wikipedia, the free encyclopedia)

Hash algorithms are designed to be fast and to yield few hash collisions in expected input domains. In hash tables and data processing , collisions inhibit the distinguishing of data, making records more costly to find.

A hash algorithm must be deterministic , i.e. if two hashes generated by some hash function are different, then the two inputs were different in some way.

Hash algorithms are usually not injective , i.e. the computed hash value may be the same for different input values. This is because it is usually a requirement that the hash value can be stored in fewer bits than the data being hashed. It is a design goal of hash functions to minimize the likelihood of such a hash collision occurring.

A desirable property of a hash function is the mixing property: a small change in the input (e.g. one bit) should cause a large change in the output (e.g. about half of the bits). This is called the avalanche effect .

Typical hash functions have an infinite domain , such as byte strings of arbitrary length, and a finite range, such as bit sequences of some fixed length. In certain cases, hash functions can be designed with one-to-one mapping between identically sized domain and range. Hash functions that are one-to-one are also called permutations . Reversibility is achieved by using a series of reversible "mixing" operations on the function input.

8.2. hash list

(From Wikipedia, the free encyclopedia)

In computer science, a hash list is typically a list of hashes of the data blocks in a file or set of files. Lists of hashes are used for many different purposes, such as fast table lookup (hash tables) and distributed databases (distributed hash tables). This article covers hash lists that are used to guarantee data integrity.

A hash list with a top hash

A hash list is an extension of the old concept of hashing an item (for instance, a file). A hash list is usually sufficient for most needs, but a more advanced form of the concept is a hash tree.

Hash lists can be used to protect any kind of data stored, handled and transferred in and between computers. Currently the main use of hash lists is to make sure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and to check that the other peers do not "lie" and send fake blocks.

Usually a cryptographic hash function such as SHA-1 is used for the hashing. If the hash list only needs to protect against unintentional damage less secure checksums such as CRCs can be used.

Hash lists are better than a simple hash of the entire file since, in the case of a data block being damaged, this is noticed, and only the damaged block needs to be redownloaded. With only a hash of the file, the whole file would have to be redownloaded instead, since it would be impossible to determine which part of the file was damaged. Hash lists also protect against nodes that try to sabotage by sending fake blocks, since in such a case the damaged block can be acquired from some other source.

Questions & Answers

what is the VA Ha D R X int Y int of f(x) =x²+4x+4/x+2 f(x) =x³-1/x-1
Shadow Reply
can I get help with this?
Are they two separate problems or are the two functions a system?
Also, is the first x squared in "x+4x+4"
thank you
Please see ***imgur.com/a/lpTpDZk for solutions
f(x)=x square-root 2 +2x+1 how to solve this value
Marjun Reply
factor or use quadratic formula
what is algebra
Ige Reply
The product of two is 32. Find a function that represents the sum of their squares.
if theta =30degree so COS2 theta = 1- 10 square theta upon 1 + tan squared theta
Martin Reply
how to compute this 1. g(1-x) 2. f(x-2) 3. g (-x-/5) 4. f (x)- g (x)
Yanah Reply
what sup friend
not much For functions, there are two conditions for a function to be the inverse function:   1--- g(f(x)) = x for all x in the domain of f     2---f(g(x)) = x for all x in the domain of g Notice in both cases you will get back to the  element that you started with, namely, x.
sin theta=3/4.prove that sec square theta barabar 1 + tan square theta by cosec square theta minus cos square theta
Umesh Reply
acha se dhek ke bata sin theta ke value
sin theta ke ja gha sin square theta hoga
I want to know trigonometry but I can't understand it anyone who can help
Siyabonga Reply
which part of trig?
differentiation doubhts
Prove that 4sin50-3tan 50=1
Sudip Reply
False statement so you cannot prove it
f(x)= 1 x    f(x)=1x  is shifted down 4 units and to the right 3 units.
Sebit Reply
f (x) = −3x + 5 and g (x) = x − 5 /−3
what are real numbers
Marty Reply
I want to know partial fraction Decomposition.
Adama Reply
classes of function in mathematics
Yazidu Reply
divide y2_8y2+5y2/y2
Sumanth Reply
wish i knew calculus to understand what's going on 🙂
Dashawn Reply
@dashawn ... in simple terms, a derivative is the tangent line of the function. which gives the rate of change at that instant. to calculate. given f(x)==ax^n. then f'(x)=n*ax^n-1 . hope that help.
thanks bro
maybe when i start calculus in a few months i won't be that lost 😎
what's the derivative of 4x^6
Axmed Reply
comment écrire les symboles de math par un clavier normal
what's the easiest and fastest way to the synthesize AgNP?
Damian Reply
types of nano material
abeetha Reply
I start with an easy one. carbon nanotubes woven into a long filament like a string
many many of nanotubes
what is the k.e before it land
what is the function of carbon nanotubes?
I'm interested in nanotube
what is nanomaterials​ and their applications of sensors.
Ramkumar Reply
what is nano technology
Sravani Reply
what is system testing?
preparation of nanomaterial
Victor Reply
Yes, Nanotechnology has a very fast field of applications and their is always something new to do with it...
Himanshu Reply
good afternoon madam
what is system testing
what is the application of nanotechnology?
In this morden time nanotechnology used in many field . 1-Electronics-manufacturad IC ,RAM,MRAM,solar panel etc 2-Helth and Medical-Nanomedicine,Drug Dilivery for cancer treatment etc 3- Atomobile -MEMS, Coating on car etc. and may other field for details you can check at Google
anybody can imagine what will be happen after 100 years from now in nano tech world
after 100 year this will be not nanotechnology maybe this technology name will be change . maybe aftet 100 year . we work on electron lable practically about its properties and behaviour by the different instruments
name doesn't matter , whatever it will be change... I'm taking about effect on circumstances of the microscopic world
how hard could it be to apply nanotechnology against viral infections such HIV or Ebola?
silver nanoparticles could handle the job?
not now but maybe in future only AgNP maybe any other nanomaterials
I'm interested in Nanotube
this technology will not going on for the long time , so I'm thinking about femtotechnology 10^-15
can nanotechnology change the direction of the face of the world
Prasenjit Reply
At high concentrations (>0.01 M), the relation between absorptivity coefficient and absorbance is no longer linear. This is due to the electrostatic interactions between the quantum dots in close proximity. If the concentration of the solution is high, another effect that is seen is the scattering of light from the large number of quantum dots. This assumption only works at low concentrations of the analyte. Presence of stray light.
Ali Reply
the Beer law works very well for dilute solutions but fails for very high concentrations. why?
bamidele Reply
how did you get the value of 2000N.What calculations are needed to arrive at it
Smarajit Reply
Privacy Information Security Software Version 1.1a
Got questions? Join the online conversation and get instant answers!
QuizOver.com Reply

Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, Data structures and algorithms. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10765/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?