Motivation Hashing Example Interning Subroutines Tips Questions?

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1 Lab 5: String Interning

Motivation Hashing Example Interning Subroutines Tips Questions?     

 Suppose we have some text (possibly code) with many long, identical strings:

def long and useless function(long variable name): loop  increment  counter  = 0;

while loop increment counter < long variable name: loop increment counter = loop increment counter + 1 long and useless function(long variable name 1) print(‘‘This isn’t useful!")

During a task such as compiling, we may need to compare these strings (such as variable and function names) many, many times.

This is computationally expensive!

⇒ The solution: string interning.

 Instead of performing comparisons on long strings such as

long and useless function and loop increment counter, we will:

Create a 1 word (4 byte) unique identifier for these strings. Compare these identifiers.

For example:

long and useless function → 0x47fa018b long variable name → 0xcc81b504 loop increment counter → 0x57cf47ab

Now the comparisons can be performed very quickly.

A hashing function takes some data as input and returns a fixed-length representation of that data.

For example:

"123password" d2bc2f8d09990ebe87c809684fd78c66 "This is  a sentence."  d15ba5f31fa7c797c093931328581664 "Hash  me!" e09f9e0c17051e3ad13f4176076cbb92 These are all examples of the MD5 hash algorithm.

There are three things you should note about hash functions:

1 The output is always the same length.

2 Identical input will always produce identical output.

3 If the input is unbounded (can be any length), multiple inputs will have the same output.

 When two different inputs have the same output in a hash function, a collision occurs.

For example:

"Both strings have the same value" → 0x5f44a1b3 "for  this  particular  hash  function." → 0x5f44a1b3

One of the goals of a hash function is to reduce the number of collisions that occur.

 

Attachments:

Expert's Answer

380 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of