Search Data Structures
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 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 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, a probability of all active entries being accessed in the table same.
- For an unsuccessful search, the symbol can enter 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 consider that for a table containing ‘f’ occupied entries, the probability of successful search is log2f and unsuccessful search is log2f.
- So, The binary search organization requires that entry number of a symbol table should not change after ‘add’ operation. This may become a 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.
- Hashtable 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:
1.A hash table that contains a fixed array of ‘m’ pointers to storage table entries.
2.Storage table entries organized into separate linked lists called buckets.
- Hash function 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.