# Advanced Data Structures I:Sets and Maps

## What they are, what they are used for, and how efficient they are..

///////////////////////////////////////////////////

Advanced Data Structures I:Sets and Maps

//////////////////////////////////////////////////

Ok. so your an experienced programmer who is asked to write a program that stores thousands of people and their personal information. The user of your program must be able to look up a person and view that person\'s information very efficiently. Look no further than Advanced Data Structures. Some advanced data structures are linked lists, stacks, queues, sets, maps, binary search trees, heaps, etc. In later tutorials i will try to cover all of these.

These tutorials will be separated into three parts: 1.Explanations 2.Efficiency (Since you are looking into advanced data structures i\'m sure you are familiar with Big O notation which i will use) 3.Application

So lets get started...

////////////////////////////////////////

~Sets~

///////////////////////////////////////

1. A set is an unordered collection of distinct elements. There are no duplicate items in sets. Now sets can be implemented as a Hashset or a Treeset. (I will cover hashes and trees in a later tutorial)

2. Hashset using a hash table ----> O(1)

Treeset --------------------------> O(log(n))

Meaning a set using a hash table will only take one iteration to find what it is looking for. Hows that for efficiency??

A set using a tree will take log of the number of items in the set to find what it is looking for.

3. An easy example of a sets use could be a resort\'s activities. Activities can\'t be ordered in any way(unless alphabetically) so we can store all of the activities in a set. Then a search bar can take the user input and find the activity in the set.

////////////////////////////////////////////

~Maps~

///////////////////////////////////////////

1. Maps store data using \"keys\" and \"values\". For every key there is only one value. But a value can belong to different keys. Maps are kept in order according to their keys. If the keys are strings it will be alphabetical, integers in numerical order, and so on. eg. A Mapping of all of your college friends to the university they attend. -alot of your friends(keys) can attend the same university(values) but a friend can\'t belong to more than one university. A map can also be implemented as a hash map or a tree map.

2. Hash map--------->O(1)

Tree map--------->O(log(n))

This means the same as above mentioned for sets.

3. Maps are very useful for easy ways to store, erase, and print information. An example that i have used a TreeMap for was a gradebook application. It would store a Student object as the keys and grades(as integers) for values. When you print the grades they are in alphabetical order according to the students last name. Maps are a very precise way of storing information

/////////////////////////////////////////

Ok. So i thought i would start off with these data structures because of their simplistic nature. I can\'t wait to write a tutorial on hashes, trees, and tree traversals. And everyones favorite HEAPS! Hope everyone enjoys this and learns from it!

--zumo--

xfire me-------->tacobueno

Advanced Data Structures I:Sets and Maps

//////////////////////////////////////////////////

Ok. so your an experienced programmer who is asked to write a program that stores thousands of people and their personal information. The user of your program must be able to look up a person and view that person\'s information very efficiently. Look no further than Advanced Data Structures. Some advanced data structures are linked lists, stacks, queues, sets, maps, binary search trees, heaps, etc. In later tutorials i will try to cover all of these.

These tutorials will be separated into three parts: 1.Explanations 2.Efficiency (Since you are looking into advanced data structures i\'m sure you are familiar with Big O notation which i will use) 3.Application

So lets get started...

////////////////////////////////////////

~Sets~

///////////////////////////////////////

1. A set is an unordered collection of distinct elements. There are no duplicate items in sets. Now sets can be implemented as a Hashset or a Treeset. (I will cover hashes and trees in a later tutorial)

2. Hashset using a hash table ----> O(1)

Treeset --------------------------> O(log(n))

Meaning a set using a hash table will only take one iteration to find what it is looking for. Hows that for efficiency??

A set using a tree will take log of the number of items in the set to find what it is looking for.

3. An easy example of a sets use could be a resort\'s activities. Activities can\'t be ordered in any way(unless alphabetically) so we can store all of the activities in a set. Then a search bar can take the user input and find the activity in the set.

////////////////////////////////////////////

~Maps~

///////////////////////////////////////////

1. Maps store data using \"keys\" and \"values\". For every key there is only one value. But a value can belong to different keys. Maps are kept in order according to their keys. If the keys are strings it will be alphabetical, integers in numerical order, and so on. eg. A Mapping of all of your college friends to the university they attend. -alot of your friends(keys) can attend the same university(values) but a friend can\'t belong to more than one university. A map can also be implemented as a hash map or a tree map.

2. Hash map--------->O(1)

Tree map--------->O(log(n))

This means the same as above mentioned for sets.

3. Maps are very useful for easy ways to store, erase, and print information. An example that i have used a TreeMap for was a gradebook application. It would store a Student object as the keys and grades(as integers) for values. When you print the grades they are in alphabetical order according to the students last name. Maps are a very precise way of storing information

/////////////////////////////////////////

Ok. So i thought i would start off with these data structures because of their simplistic nature. I can\'t wait to write a tutorial on hashes, trees, and tree traversals. And everyones favorite HEAPS! Hope everyone enjoys this and learns from it!

--zumo--

xfire me-------->tacobueno

Comments

only_samuraion December 28 2006 - 17:40:33 The efficiency of a hash map or hash set is not always O(1). That depends on your hashing algorithm. It is probably the most efficient way of storing data when done correctly, but is only O(1) in certain cases. Mathematically it would best be said that the limit of x in O(x) approaches 1, depending on your algorithm. |

zumoon December 28 2006 - 18:26:45 I also was only referring to the lookup efficiency for an item in all of those. the efficiency changes when you want to add or remove objects. but O(1) is the general efficiency of looking up a piece of data in a hash set or map. _off topic_ i wonder how many ppl on this site are actually skilled programmers and know this stuff? |

spywareon December 28 2006 - 18:43:31 not me |

only_samuraion December 28 2006 - 19:32:26 well, even on a look up it isn't a O(1)....again, still depends on your hashing algorithm. |

zumoon December 29 2006 - 17:59:38 k ur college programming experience trumps my high school. i got things to learn. hey if u can i'd love to be able to come to you on any problems i encouter (that i can't figure out myself) on this upcoming first person 3d shooter i'm making. its gonna be "Counter Smite". a java version of cs:s in the same way if u have seen Jake or Jake 2 (which is java Quake). btw do you know C++? I'm taking independent study classes my senior year to work through a pretty intense game in C++. Good to know another programmer. |

only_samuraion December 29 2006 - 19:14:54 heh, sure you can ask me. i'm not huge with C++, but i know people who are so i can always check with them. I'm a java guy. and i just reread what I posted, seemed a little harsh. sorry about that. I was just trying to correct you so that others don't learn wrong. |

Post Comment

**Sorry.**

You must have completed the challenge

**Basic 1**and have

**100 points**or more, to be able to post.