[algogeeks] Re: Hash Table
from high level and with a very few collisions, it's O(1). there isn't much to prove because this is based on a common sense. for example, have the world as a hashtable and all countries as the keys of it. boxes(storage) marked by different country names(key) and you know where to locate them. now, you are given a mail and asked to put it into the box which goes to its destination country. so how many operations does it take you to put a mail in the box? 1 if you realized the mail wasn't misplaced and you need to take it out, how many operations does it take you to take the mail out of the box? i hope this helps a bit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ZamCyJETdscJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
If N Element is already hashed and when you insert next element , Does hashing will take log N time to find the next available position? Actually the next insertion typically does not have any co-relation to pre-existing table content (Until your Hash function is badly designed to hash always on the same key everytime). So, its actually the design of Hash that has to be efficient.Hence every operation cannot be mapped to the number of data which is present in the existing table. On Thu, Oct 27, 2011 at 12:49 AM, ligerdave david.c...@gmail.com wrote: from high level and with a very few collisions, it's O(1). there isn't much to prove because this is based on a common sense. for example, have the world as a hashtable and all countries as the keys of it. boxes(storage) marked by different country names(key) and you know where to locate them. now, you are given a mail and asked to put it into the box which goes to its destination country. so how many operations does it take you to put a mail in the box? 1 if you realized the mail wasn't misplaced and you need to take it out, how many operations does it take you to take the mail out of the box? i hope this helps a bit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/ZamCyJETdscJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
suppose the problem is
Problem 4: Find all unique pairs of element in an array that sum to S. For
ex. If array = {2,4,6,4,6} and S = 8 then answer is {2,6, 4,4}
suppose we use STL c++ hash class to solve the problem . In the first we
hash all the elements . in the second pass we take each element and subtract
it from '8' and then we search for that difference in the hash table. if it
is found then the pair exists .otherwise it does not exist.
My questions are
1) What is the space complexity used by hash table . is it O(n) becoz 'n'
elements are hashed into hash table.
2) Does the time to search an element is hash table is still O(1) ,but there
are 'n' elements in hash table .Then how could it be O(1)
Please clear my above doubts .These doubts are haunting me .I am very
thankful to them ...
On 27 October 2011 06:18, Prem Krishna Chettri hprem...@gmail.com wrote:
If N Element is already hashed and when you insert next element , Does
hashing will take log N time to find the next available position? Actually
the next insertion typically does not have any co-relation to pre-existing
table content (Until your Hash function is badly designed to hash always on
the same key everytime). So, its actually the design of Hash that has to be
efficient.Hence every operation cannot be mapped to the number of data which
is present in the existing table.
On Thu, Oct 27, 2011 at 12:49 AM, ligerdave david.c...@gmail.com wrote:
from high level and with a very few collisions, it's O(1).
there isn't much to prove because this is based on a common sense.
for example, have the world as a hashtable and all countries as the keys
of it. boxes(storage) marked by different country names(key) and you know
where to locate them. now, you are given a mail and asked to put it into the
box which goes to its destination country.
so how many operations does it take you to put a mail in the box? 1
if you realized the mail wasn't misplaced and you need to take it out, how
many operations does it take you to take the mail out of the box?
i hope this helps a bit
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/ZamCyJETdscJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
@Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
I am asking for the above quesiton On 27 October 2011 07:38, kumar raja rajkumar.cs...@gmail.com wrote: @Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
@Kumar: It's O(1) for searching an element in hash table as long as there is no collision. -Vicki On Thu, Oct 27, 2011 at 10:38 AM, kumar raja rajkumar.cs...@gmail.comwrote: @Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Hash Table
One sentence answer to your query is all Hash DataStructure is suppose to provide Constant Time Complexity .i.e.O(1). However as an when HashTable fills up,Data Value collision occurs becoz,common key will generated by HashFunction.Thats where HashFunction dependibility comes into picture.. Well the Worst Case of Time Complxity extremgely poor hash function may go upto O(n). Which is very rare and when data is hash table is fully filled with all colliding values.. On 10/27/11, kumar raja rajkumar.cs...@gmail.com wrote: I am asking for the above quesiton On 27 October 2011 07:38, kumar raja rajkumar.cs...@gmail.com wrote: @Prem : So is the time complexity is O(1) or O(log n) or O(n)??? On 27 October 2011 07:28, Prem Krishna Chettri hprem...@gmail.com wrote: Well, if we talk abt space complexity in Hash.. M srry we require O(n) for Hash Datastructure... As each Bucket can contain at most one data value of Key Value pair,thats where key is gonna hash your value.. However, when we talk abt time complexity, its alwayz, the Hash Function dependable question... On 10/27/11, ligerdave david.c...@gmail.com wrote: I am a bit confused. Are you talking about the runtime of hash function itself or to find the position. Agree on the efficient hash function design. However, no function could be designed to fit all cases. A key to make a particular hash function efficient is to know the potential data size. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/G_0Wm4NQIyIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Hash Table
It can be true if the hash table is used properly. If the table becomes too full or the hash function produces too many collisions it will not be constant time. So designing the hash system well remains very important. Don On Oct 25, 12:15 am, kumar raja rajkumar.cs...@gmail.com wrote: I have read that Hash table provides storing/search operations in constant time. Is it true?? How to prove it?? I have not found any sort of proof for it... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Hash Table
When the number of elements increases gradually ,the complexity must increase .so it the situtaion is like it has to store all the 'n' elements then all the basic operations require O(log n) time.so how it is constant always i am not getting... On 24 October 2011 22:15, kumar raja rajkumar.cs...@gmail.com wrote: I have read that Hash table provides storing/search operations in constant time. Is it true?? How to prove it?? I have not found any sort of proof for it... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Hash Table Design
First, if you have a set of unique usernames, those could be used to be keys. How to generate hash is depends on your requirements. You can add a few prefix chars or postfix On Sep 30, 2:45 pm, amit amitjaspal...@gmail.com wrote: Design a hash table to store phone #s. Your job is to write a hash function that has a parameter username, and generate a key. Username is unique, length 5 and can be A-Z, 0-9, space. Write a hash function that generate keys without collisions and use minimum memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Hash Table Design
Use a trie, the memory needed will be less than having a list of strings and it will be faster than hashTable (array implementation of trie). Check Trie in Wikipedia. If the datastructure is going to be static, then using a Directed acyclic finite automata (dafsa) may be even better. On Sep 30, 9:45 pm, amit amitjaspal...@gmail.com wrote: Design a hash table to store phone #s. Your job is to write a hash function that has a parameter username, and generate a key. Username is unique, length 5 and can be A-Z, 0-9, space. Write a hash function that generate keys without collisions and use minimum memory. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
