Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev

Compiler Design

Computer Science Engineering (CSE) : Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev

The document Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Compiler Design.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Hash Tables and Hash Functions: ·
A hash table is an array with index range: 0 to TableSize – 1  

  •  Most commonly used data structure to implement symbol tables    
  •  Insertion and lookup can be made very fast – O(1)  
  • A hash function maps an identifier name into a table index  
  • A hash function, h(name), should depend solely on name
  • h(name) should be computed quickly 
  • h should be uniform and randomizing in distributing names 
  • All table indices should be mapped with equal probability
  • Similar names should not cluster to the same table index.   

Storage Allocation:  

  • Compiler must do the storage allocation and provide access to variables and data  
  • Memory management  
  • Stack allocation
  • Heap management  
  •  Garbage collection   


    Storage Organization:
     

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
 

• Assumes a logical address space 

  • Operating system will later map it to physical addresses, decide how touse cache memory, etc.  

 
• Memory typically divided into areas for

  • Program code   
  • Other static data storage, including global constants and compilergenerated data  
  • Stack to support call/return policy for procedures
  • Heap to store data that can outlive a call to a procedure  


Static vs. Dynamic Allocation:  

  • Static: Compile time, Dynamic: Runtime allocation  
  •  Many compilers use some combination of following
  • Stack storage: for local variables, parameters and so on  
  • Heap storage: Data that may outlive the call to the procedure that created it 
  • Stack allocation is a valid allocation for procedures since procedure calls are nest   

 Example:
Consider the quick sort programint a[ll]

void readArray() { / Reads 9 integers into a[l],a[9j. */ int i;

int partition (int m, int n) ■(

/* Picks a separator value v, and partitions a[m.. n] so that
a\m .. p — 1] are less than v, a\p\ = v, and a[p + 1.. n] are
equal to or greater than v. Returns >

void quicksort (int m, int n) -( int i;

if (n > m) -(

i = partition(m, n);
quicksort(m, i-1);
quicksort(i+1, n);

main() {

readArray() ; a[0] = -9999;
a [10] = 9999;
quicksort(1,9);

>

Activation for Quicksort

enter main()

enter readArray() 
leave readArray() 
enter quicksort(1,9)

enter partition(l,9)
leave partition(1,9)
enter quicksort(1,3)

leave quicksort(1,3)
enter quicksort(5,9)

leave quicksort(5,9)
leave quicksort(1,9)
leave main()

Activation tree representing calls during an execution of quicksort:


        Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
 

Activation records

  • Procedure calls and returns are usually managed by a run-time stack called the control stack.  
  • Each live activation has an activation record (sometimes called a frame)  
  •  The root of activation tree is at the bottom of the stack  
  • The current execution path specifies the content of the stack with the last  
  • Activation has record in the top of the stack.
     

A General Activation Record

                          Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
 

Activation Record

  • Temporary values  
  • Local data    
  • A saved machine status  
  • An “access link”  
  • A control link
  • Space for the return value of the called function  
  • · The actual parameters used by the calling procedure    
  • · Elements in the activation record:   
  • Temporary values that could not fit into registers. 
  • Local variables of the procedure.
    Saved machine status for point at which this procedure called. Includes return address  
    and contents of registers to be re  stored. 
  • Access link to activation record of previous block or procedure in lexical scope chain.
  • Control link pointing to the activation record of the caller.  
  • Space for the return value of the function, if any.
  • actual parameters (or they may be placed in registers, if possible)  

 Downward-growing stack of activation records:
 

 

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
 

Designing Calling Sequences:

  •  Values communicated between caller and callee are generally placed at the beginning of   callees activation record   Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
  •  Fixed-length items: are generally placed at the middle    
  •  Items whose size may not be known early enough: are placed at the end of activation record    
  •  We must locate the top-of-stack pointer judiciously: a common approach is to have it point to the end of fixed length fields  
     

Access to dynamically allocated arrays:
 

 

                                   Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
 

     ML

  • ML is a functional language
  • Variables are defined, and have their unchangeable values initialized, by a statementof the form:
  • val (name) = (expression)
  • Functions are defined using the syntax: fun (name) ( (arguments) ) = (body)
  • For function bodies we shall use let-statements of the form:
  • let (list of definitions) in (statements) end  
     

A version of quick sort, in ML style, using nested functions:
 

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
 

Access links for finding nonlocal data: 
 

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
 

Sketch of ML program that uses function-parameters:
 

 

 

fun a(x) =
let

fun b(f) =

... f ...     ;

fun c(y) =
let

fun d(z) =

in

b(d)

end

 

in
                   ....c(1).......                            

end;
 

Actual parameters carry their access link with them:
 

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev
Maintaining the Display:
 

 

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev

Memory Manager: 

  •  Two basic functions:   
  • Allocation  
  • Deallocation
  • Properties of memory managers: 
  • Space efficiency  
  • Program efficiency  

Low overhead

Typical Memory Hierarchy Configurations:

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev

Locality in Programs:

The conventional wisdom is that programs spend 90% of their time executing 10% of the code: 

  • Programs often contain many instructions that are never executed.  
  • Only a small fraction of the code that could be invoked is actually executed in atypical run of the program.  
  • The typical program spends most of its time executing innermost loops and tight recursive cycles in a program.  

 

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

MCQs

,

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev

,

pdf

,

Free

,

Exam

,

Objective type Questions

,

past year papers

,

shortcuts and tricks

,

video lectures

,

ppt

,

Previous Year Questions with Solutions

,

Summary

,

practice quizzes

,

mock tests for examination

,

study material

,

Important questions

,

Extra Questions

,

Viva Questions

,

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev

,

Hash Tables and Hash Functions Computer Science Engineering (CSE) Notes | EduRev

,

Semester Notes

,

Sample Paper

;