Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 4 down vote favorite

My understandment is that hash maps allow us to link, say, a string, to certain memory location. But if every string were to be linked to a unique place in memory it would need a huge block of empty memory. I don't get it.

share|improve this question
Question asked an answered in stackoverflow – Andres F. Jan 21 at 17:46
Try (en.algoritmy.net/article/50101/Hash-table), there are several approaches discussed, including your proposed array based storage (which is not hash table) – malejpavouk Mar 27 at 20:43

2 Answers

up vote 8 down vote accepted

Hash functions are used to convert the input (usually string) to a smaller fixed length (typically) "hashed value" which typically is used somewhat like a array index for the hash table. Ideally this value should be evenly spread throughout its range, and avoid any obvious/significant concentrations.

A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length.

You have been miss informed with regards to the "certain memory location". The use of such a function is to reduce a large piece of data into a much smaller value which can be used to identify that large data. Since you are reducing the size of the data however, it is likely that more than one input "data" will have the same hashed value - that is what is called collision.

A valid hash function (not a very good one, but valid still) could be one that sums up each of the letters of the string by their ASCII codes.

share|improve this answer
I see. Which hashing algorithm is used to implement hash tables? – Dokkat Jan 21 at 6:30
5  
@Dokkat I expect each implementation has its own. The choice is tough because it has several dimensions that should be considered - It should be good, but fast, should spread the values evenly, etc. – Karthik T Jan 21 at 6:33
to a random "hashed value" I would NEVER use a hash 'function' that has random output. – Thomas Eding Jan 22 at 6:35
1  
@ThomasEding I meant random such that the values are evenly spread with no obvious patterns, but I agree, missleading. – Karthik T Jan 22 at 6:38
up vote 1 down vote

Hash and map are two different concepts. (And hence two tags hashing and map :-)).
The concept of map (in this context) is collection of key-value pairs, where key could be anything and value could be anything. Once you created a map, map should be able to retrieve value of a given key. A simple map could be storing the key-value pair in an array, or linked list. A map can be implemented using any storage technique. Popular are Red-Black Trees and Hashing.
Hashing is converting anything into a unique representation (most of the times as random as possible) which is limited by some range. Hashing is one way, means once you hash A into B there is no guaranteed way to get A from B.
A hash function is one which takes A as input and returns B as output. Two properties for hash functions are important.

  1. It should always return same B given the same A. 
  2. Ideally it should return different B for different A. But it is impossible if the range of B is smaller than range of A.

Getting a good hash function is really difficult as maintaining property 2 is quite difficult. A simplest hash function is modulo operator. There exists a good lot of hash algorithms and libraries.
Now what you get when you combine these two? A hash map. The key is converted to hash and stored against the value. So if I have a pair (A,A'), I will convert A to hash B and store (B, A'). Now If I want to get what is the value stored against key A, I will first convert A to B and then see what is stored against B, and return it.
The advantage of using hash map is the fast retrieval. It is O(1), i.e. in constant time I can find whether a key is present and the value against it. Compare it to Red-Black Tree where the time complexity of retrieving is O(logn). (There is also time of inserting and deleting which I am not discussing here.)
So now tell me what's your question?

share|improve this answer
3  
Property 2 is impossible, given the requirement of limited range. Imagine a 128-bit hash of a string; it cannot possibly have a unique value for every different string. Why not? Because a string can express any 128-bit hash and other values; the domain is larger than the range. – Graham Lee Jan 21 at 9:17
yes, true. But not sure what to put there, what about "As different as possible"? – Manoj R Jan 21 at 9:21
1  
When you're designing a data structure that depends on a hash function to distribute values through the structure, if you want the structure to be evenly balanced then you require the hash function to have evenly distributed output. – Graham Lee Jan 21 at 11:16
Point 2 can be corrected simply by removing the always qualifier. (A hashmap implementation must handle hash collisions.) @GrahamLee's point is also a serious consideration for any hash function used in a hashmap implementation. – Michael Kjörling Jan 21 at 12:15
1  
@ManojR It doesn't give 2 different values. f(x) = 0 is a valid hash function; one that maps every input value to the same bucket. The only true constraint for a hash function f is that x == y --> f(x) == f(y). Note that any constant function satisfies this condition. Not saying this is a good choice of hash function, though ;) – Andres F. Jan 21 at 15:19
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.