Introduction
In this article, we’ll discuss the tables and dictionaries. And techniques to perform the operations on them in order to obtain the efficient speed.
Table
Table is an abstract data type that consists of the collection of rows and columns.
Table looks like a 2D array, but it’s not the case every time. Because table contains the field of different data types.
- Column of table is called field.
- Row of table is called record or tuple.
Field contains some type of information. For example: A table named “Employee” can have the fields of “Name”, “Department”, and “Salary”.
Following table contains three fields (Name, Address, Phone) and three rows.
| Name | Address | Phone |
| Sohail Aslam | 50 Zahoor Elahi Rd, Gulberg-4, Lahore | 567-4567 |
| Imran Ahmad | 30-T Phase-IV, LCCHS, Lahore | 517-2349 |
| Salman Akhtar | 131-D Model Town, Lahore | 756-5678 |
Dictionary
In programming, dictionary is a data type that is in the form of sets of fields, where field comprise data items.
Uses of Table ADT
Databases: The main use of tables you’ll find in the data bases. Example: A table named “Students” with fields of name, location, age, and class is stored in a database. All fields are filled with the data. Whenever, admin wants the information of the student, he can do this using SQL (Structured Query Language).
Compilers: Symbol tables are used in this regard. In a program, each variable declared has a, type and scope. When the compiler compiles a program, it makes a table of all the variables in the program.
To find an entry in the table, we only need to know the contents of one of the fields (not all of them). This field is called key.
The key that uniquely identifies an entry in a table is called primary key.”
We obtain the record or piece of record (any information) with the help of primary key. For example: In user account table, the key is usually user_id. If we want to find the account information of a specific user then we’ll just go to the specific key assigned to that specific user.
Name field in Table-1 can be used as primary key because none of any entry in that field matches. So, searching/finding operation will be carried through this key.
Operations on Table ADT
- Insert: This method puts the key and the other related fields in a table (adding record).
- Find: This method is given a key and it finds the entry associated with the key.
- Remove: This method is given a key to find and remove the entry associated with that key.
Implementation of Table
Our choice for implementation of the Table ADT depends on the answers to the following.
- How often entries are inserted, found and removed?
- How many of the possible key values are likely to be used?
- What is the likely pattern of searching for keys? Will most of the accesses be to just one or two key values?
- Is the table small enough to fit into the memory?
- How long will the table exist?
In a table for searching purposes, it is best to store the key and the entry separately (even though the key’s value may be inside the entry).
See following Figure-1 to understand the difference between the key and entry.
Unsorted Sequential Array
We store the data of table in an array such that keys are stored consecutively in any order
We’ll use class to store the fields of different types. Later, object of the class will be stored in array. In this array, every object is a table entry.
- Insert: Insert operation is fast. We add object to the back of the array. Means, we put the data at the last available position. So, insertion in this array is efficient in terms of speed.
- Find: Find operation is slow. The time of searching will be proportional to the number of entries i.e. n. Similarly the remove method also requires time proportional to n.
- Remove: Remove operation is also slow. Because first it consumes time in find operation. Later, in shifting the elements for consecutive nature of array.
The insertion of data is fast but the find operation is slow and requires much time.
Sorted Sequential Array
In this, we keep the data in the array in a sorted form with a particular order.
Sorted sequential array is also fast as binary search tree. But we’ll use array, not tree. We’ll put the data in array and then sort it. Consider we sort the name of students from “Student” table alphabetically. Then, names with letter “a” will come first, after this “b”, later “c” and so on.
- Insert: Insert operation is slow. Because after insertion we may need to shift the elements of array to keep them sorted and consecutive.
- Find: Find operation is fast. Searching out a particular entry takes log n times, where n is the number of entries in array.
- Remove: Remove operation is also slow (proportional to n). Because find operation takes log n times and then it shuffle the elements to maintain the order.
Conclusion
We make array of objects to avoid facing the problem of multiple data types. Objects in the array can be sorted or unsorted. In case of sorted, Insertion and removal operation are slow and find operation is fast. While, in case of unsorted, searching and removal operations are slow and insertion operation is fast. We can use any of these methods depending upon the answers of above given questions.
Few more techniques for Table ADT:
REFERENCE: CS301 Handouts (page 424 to 428)
