C Programming

Top Answer

While binary search trees provide logarithmic search times on average, we would like to do even better. For

integer keyed items, we can trivially get constant search time by using an array, with one position for each

possible key. However, with 232 possible keys, there's no way we could create an array large enough.

Instead, we could get almost constant search time if we create an array twice as large as our data set,

and store a value k at position kmodm, where m is the size of the array. To search for a value k, we again

compute k mod m and then check the corresponding array position. We would expect an even distribution

of values, so we expect one or two values per array position. To retain this expectation, we may need to

resize the array as we insert values. We want to keep the load factor, k

m, at about 0:5. Resizing potentially

requires us to move all values, but the total amortized cost of insertion is still constant. Searching is also

constant in this scheme.

There is the problem of multiple values mapping to the same array position, or bucket. This situation

is called a collision. There are multiple ways of resolving collisions. One way is to place a value that maps

to an occupied bucket to the next empty bucket. Another is to have linked lists at each bucket, and store

values in the lists. This is the solution we'll use.

This is ne for integer values, but what about arbitrary objects? We rst compute an integer corresponding

to the object, called a hash code, and use that to map the objects to positions. There are two

conditions on a hash code. Equal objects (as dened by the equals() method) must have equal hash codes,

and the hash code for an object cannot change while it is in a hash table. Then, assuming the hash code

can be computed quickly and distributes objects evenly in a table, this gives us constant-time searching for

arbitrary objects.

How should we compute a hash code on an object? Many objects can be represented as k-tuples of

integers. For example, an object corresponding to a point in two-dimensional space can be represented by a

double of integers, converting the

oating point x and y values bitwise to integers. A good hash code for a

k-tuple (x0; x1; :::; xk1) is

x0 an1 + x1 an2 + ::: + xn2 a + xn1

where a is a constant. Choosing a prime number minimizes the chance of a collision.

Our hash code formula works even if k is unbounded, such as in strings. Java's String class uses the

following formula:

public int hashCode() {

int code = 0;

for (int i = 0; i < length(); i++) {

code = 31 * code + charAt(i);

}

}

This is our formula, with a = 31 and xi =charAt(i).

Hashing is performed on arbitrary data by a hash function. A hash function is any function that can convert data to either a number or an alphanumeric code. There are possibly as many types of hashing as there are data. How precisely the hash function works depends on what data it is meant to generate a hash code from. Hashing is used for a variety of things. For example, a hash table is a data structure used for storing data in memory. Instead of iterating through the structure to find a specific item, we associate a key (hash code) to a particular item (data). A hash code can be generated from a file or disk image. If the data does not match the code, then the data is assumed to be corrupted. Hashing has the advantage of taking a larger amount of data and representing it as a smaller amount of data (hash code). The code generated is unique to the data it came from. Generating a hash code can take time however, depending on the function and the data. Some hash functions include Bernstein hash, Fowler-Noll-Vo hash, Jenkins hash, MurmurHash, Pearson hashing and Zobrist hashing.

Trending Questions

Who would you swap lives with for a day?

Did Bill Nye go to jail?

Which is the verb in this sentence - it is such a nice day?

Din se roshan hai raat se andhari hai khao to haram hai peo to halal hai aurat sari zindgi you use 1 bar use karti hai aur mard din you 3 bar use karta hai quran you uska 5 dafa zikar hai?

Is 30 pints greater than 7 gallons?

What is 180 degree Celsius equal to in Fahrenheit?

A farmer has 19 sheep All but 7 die How many are left?

How many times does 3 go into 100?

Hottest Questions

What should I know about coronavirus?

What does contingent mean in real estate?

How many stars are in the Big Dipper?

What is the one food you could eat for the rest of your life?

What does a red flag mean on the beach?

What's the weirdest state symbol?

What is OK short for?

Is it possible to die of a broken heart?

Previously Viewed

clearUnanswered Questions

What is the English word for maram oru varam

What is the novel strategy to popularize environmental causes was introduced in 2008. Identify the strategy.

What are the Advantage and disadvantage of mechanical transducer

Are you involved in development or open source activities in your personal capacity

Looking for a movie that I forgot the name of

What happened to Kelly on tmz

What is the difference between indigenous and formal bookkeeping

What is an example of juxtaposition in Private peaceful

Copyright © 2020 Multiply Media, LLC. All Rights Reserved. The material on this site can not be reproduced, distributed, transmitted, cached or otherwise used, except with prior written permission of Multiply.