Hash table

[akash16]

What is hash table and its applications?

Hi All,

I never use Hash table in my coding or any other design.
So I am very qurious to know basics and some internals of hash table.

What I know is:

Hash is a data structure, which map key to specific value.

So map in STL may can implement by using hash table.

Please share thoughts....

[E0p9LyTq]

There are examples for how to use the STL map container in the reference section here.

http://www.cplusplus.com/reference/map/map/

[kevinkjt2000]

Wikipedia has a decent definition of a hash table: https://en.wikipedia.org/wiki/Hash_table

[akash16]

Hey thanks FG for reply.
But here I am interested about hash table and not about map.


@k2000
What mentioned is same as wiki.


Is anyone have some additional points to share about hash table?

[E0p9LyTq]

map IS a hash table.

http://www.sparknotes.com/cs/searching/hashtables/section1.html

[akash16]

Hey nice link. thanks.

But we can implement map by using other data structure also like binary search tree or list.

So same we can implement map by using hash table.

So we can not say that map is hash table.

[kevinkjt2000]

So we can not say that map is hash table.

The STL std::map does use a hash table though! So we can say that std::map is a hash table...
Sure you could implement your own map data structure using something other than a hash table, but std::map will still be using a hash table.
I was wrong. Turns out using other languages makes c++ details easier to forget.

What mentioned is same as wiki.

Then why did you ask

what is hash table

?

If you meant to ask a different question, what is it?

[Peter87]

kevinkjt2000 wrote:

The STL std::map does use a hash table though! So we can say that std::map is a hash table...

You must be thinking of std::unordered_map. std::map is normally implemented as some kind of binary search tree.

http://www.cplusplus.com/reference/map/map/
http://www.cplusplus.com/reference/unordered_map/unordered_map/

[Duthomhas]

Careful: a hash table is a map, but a map is not necessarily a hash table.

[akash16]

What we are saying hash table is a map ???

We can implement map by using hash table.

And also its very true that std::map is implemented by binary search tree.

[kevinkjt2000]

If you meant to ask a different question, what is it?

[dhayden]

std::map is not a hash table. It is an ordered collection (remember it takes a comparison function in the arguments). Hash tables don't put the items in a client-specified order.

Assuming that you've read some of the links that describe what a hash table is, here are some details on their application.

Hash tables can provide very fast lookup if the number of buckets is appropriately large. I usually aim for an average bucket size of 4. In comparison, std::map is usually implemented with a red-black tree (I think). This is a type of self-balancing binary tree.

So consider a collection with 1,000,000 items:
- searching in a hash table means compute the hash, and then compare against an avg of 4 items: hash comp comp comp comp done.
- searching a map requires about log2(1,000,000) comparisons: about 20 comparisons
- insert and delete in the hash table are also pretty quick if the buckets are small Changing the number of buckets is expensive because you have to rehash and move every item.
- inserting and deleting in a map is requires finding the item and possibly rebalancing the tree (I think that's up to 20 operations if the depth is 20).
- Bottom line on insert/delete is that hash tables can be faster, but they can be WAY slower if the number of buckets isn't managed carefully.
- As I mentioned, maps store their items in order. Sometimes this is really handy.

- The final gotchya: the hashing vs comparison function. Imagine that your collection is random strings that average 10k bytes in size. Comparing strings for less-than can be pretty quick, perhaps only one character. But computing the hash value always requires traversing the entire string. Or the opposite may be true: maybe comparing objects takes 20 comparisons, but you can use a single integer as a hash value. So the complexity of the comparison function vs the hashing function can be a factor in which one to use.

Hope this helps.

[akash16]

Arrays can not easily grow but lookup time is very less. i.e. O(1)

Link list can easily grow but lookup time is not efficient. i.e. O(n)

Can we do better than O(n) whle still our data structure grow over time...?
I think hash table offers a solution over.

We can use hash table when speedy Insertion, Deletion and lookup of elements is priority.

So what is hash table anyway?
So Hast table is just an Array coupled with the function which will call Hash Function.
This hash function takes input as key and generate value and decide its place/position in hash table.

e.g. We want to store words using hash table.
We have a hash function which check input key in alphabetical order and then generate value for it and put it into Hash table.

1. Apple as a input to our hash function It generate 0 has a hash value Because it start from alphabet 'a' and store it into hash table at 0th.
2. Same If I gave input Banana then our hash function generate hash value 1.
3. Same for cat.

Hash Function:

int HashFunction(char* key)
{
   // Hash on first letter of string

   // Return equivalent Index Value
}

Hash Table:

Index    Values
===      ====
0          Apple
1          Banana
2          Cat
3

If we want to store "ant" into table as well:
we give "ant" as input to our hash function, what will be the hash value he generate???
If he generate 0th as its also start from alphabet 'a' then in such cases collision will occur.
i.e. Two key hashing to the same index.

Thats why you should have a plan to handle the collision in your hash function.

thee are some methods to resolving collision:
1. Linear probing
2. Separate chaining


http://algs4.cs.princeton.edu/34hash/

http://www.algolist.net/Data_structures/Hash_table/Simple_example