Advanced Data Structures I:Sets and Maps

Advanced Data Structures I:Sets and Maps

By ghost | 4390 Reads |

0     0

/////////////////////////////////////////////////// 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