Search data structures (Search structure) is used to create and organize various tables of information and mainly used during the analysis of the program.
Features of Search data structures
The important features of search data structures include the following:
- An entry in search data structure is essentially a set of fields referred to as a record.
- Every entry in search structure contains two parts: fixed and variable. The value in fixed part determines the information to be stored in the variable part of the entry.
Operations on Search Structures
Search structures are characterized by following operations:
- Insert Operation: To add the entry of a newly found symbol during language processing.
- Search Operation: To enable and support search and locate activity for the entry of symbol.
- Delete Operation: To delete the entry of a symbol especially when identified by language processor as redundant declarations.
Sequential Search Organization
- In sequential search organization, during the search for a symbol, probability of all active entries being accessed in the table is same.
- For an unsuccessful search, the symbol can be entered using an ‘add’ operation into the table.
Binary Search Organization
- Tables using binary search organization have their entries assumed to satisfy an ordering relation.
- It should be considered that for table containing ‘f’ occupied entries, the probability of successful search is log2f and unsuccessful search is log2f.
- The binary search organization requires that entry number of a symbol table should not change after ‘add’ operation. This may become limiting factor for addition and deletion during language processing.
Hash Table Organization
- A hash table, also known as a hash map is a data structure that has the ability to map keys to the values using a hash function.
- Hash table organization is an efficient m implementing associative arrays and symbol tables that outperform other data structures with its capability of performing 'm' accesses on 'n' names.
- It has the following two parts:
- A hash table that contains a fixed array of 'm' pointers to storage table entries.
- Storage table entries organized into separate linked lists called buckets.
- Hash function is used for the mapping of a key value and the slot where that value belongs to the hash table.
- The hash function takes any key value from the collection and computes an integer value from it in the range of slot names, between 0 and m - 1.
Linked List and Tree Structure Organizations
Linear List
- Linear list organization is the simplest and easiest way to implement the symbol tables.
- It can be constructed using single array or equivalently several arrays that store names and their associated information.
- During insertion of a new name, we must scan the list to ensure whether it is a new entry or not.
- If an entry is found during the scan, it may update the associated information but no new entries are made.
- If the symbol table has 'n' names, the insertion of new name will take effort proportional to 'n' and to insert 'n' names with 'm' information, the total effort is 'cn(n+m)', where 'c' is a constant representing the time necessary for a few machine operations.
- The advantage of using list is that it takes minimum possible space. On the other hand, it may suffer for performance for larger values of 'n' and 'm’.
Self-Organizing List
- Searching in symbol table takes most of the time during symbol table management process.
- The pointer field called 'LINK' is added to each record, and the search is controlled by the
- order indicated by the ‘LINK’.
- A pointer called 'FIRST' can be used to designate the position of the first record on the linked list, and each 'LINK' field indicates the next record on the list.
- Self-organizing list is advantageous over simple list implementation in the sense that frequently referenced name variables will likely to be at the top of the list.
- If the access is random, the self-organizing list will cost time and space.
Search Trees
- Symbol tables can also be organized as binary tree organization with two pointer fields, namely, 'LEFT' and 'RIGHT' in each record that points to the left and right subtrees respectively.
- The left subtree of the record contains only records with names less than the current records name. The right subtree of the node will contain only records with name variables greater than the current name.
- The advantage of using search tree organization is that it proves efficient in searching operations, which are the most performed operations over the symbol tables.
- A binary search tree gives both performance compared to list organization at some difficulty in implementation
