Courses

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

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:

• 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() {

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

>

Activation for Quicksort

enter main()

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:

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

Activation Record

• Temporary values
• Local data
• A saved machine status
• 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:

Designing Calling Sequences:

•  Values communicated between caller and callee are generally placed at the beginning of   callees activation record
•  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

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:

Access links for finding nonlocal data:

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:

Maintaining the Display:

Memory Manager:

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

Typical Memory Hierarchy Configurations:

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!

Compiler Design

16 videos|44 docs|29 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;