Hashing (OCR A Level Computer Science)

Worked Example

A developer is designing a network security system. She is developing a component that logs websites users can access. This software records the websites' URLs and details about the allowed users and their access times.

For each website, the following details are captured:

• Required user rank (A-D)

• If it's accessible 24/7 (true) or only during breaks and outside office hours (false)

For instance, a website that can be accessed by users of rank B and higher throughout the day would have the data [B, true] associated with it.

A site that ranks C and above users but only outside office hours would be recorded as [C, false].

Identify an appropriate data structure to keep the details of a single website.

[1]

Answer:

 Answer that gets full marks:

Hash table or tuple.

Worked Example

Every website's URL, along with its corresponding data, is saved in a hash map.

The hash function of this map processes the website's URL (serving as the key). The hashing procedure is as follows:

1. Remove characters up to and inclusive of the first dot.

2. Eliminate characters from and after the next dot present.

3. Convert the remaining string to uppercase.

4. Sum up the ASCII values of the characters.

Given the ASCII values for the letters:

As an example, consider the URL www.exam.net. The hashing process would be:

Step 1: exam.net

Step 2: exam

Step 3: EXAM

Step 4: 69 + 88 + 65 + 77 = 299

This results in a hashed value of 299.

State what hashed value would be given by the website www.foo.co.uk

[1]

How to answer this question:

Follow the same steps as described in the question. 

1. Remove characters up to and inclusive of the first dot.

Result: foo.co.uk

2. Eliminate characters from and after the next dot present.

Result: foo

3. Convert the remaining string to uppercase.

Result: FOO

4. Sum up the ASCII values of the characters.

• F: 70

• O: 79

• O: 79

Sum: 70 + 79 + 79 = 228

Answer:

Answer that gets full marks:

The sum of ascii values for www.foo.co.uk is 228.

Worked Example

Complete the function hash, which takes in a string and returns the hashed value.

You can assume you have access to the following three functions:

• asc() – this takes in a character and returns its ASCII value. For example, asc("A") returns 65.

• locate() – this takes in a string and character and returns the location of the first instance of the character (with the string starting at character 0). For example, locate("electricity","c") returns 3.

• upper() – this takes in a string and returns the UPPERCASE version. For example upper("hello") returns "HELLO".

You should also assume that all website names use letters but no numbers or symbols.

function hash(siteName)

endfunction

[5]

How to answer this question:

1. Understand the requirements:

   • You are to create a hash function.

   • Make use of the provided functions: asc(), locate(), and upper().

   • Implement the hash function as described in the earlier content.

2. Implement the steps:

   • Discard characters up to and including the first dot.

   • Discard characters including and to the right of the remaining leftmost dot.

   • Convert the characters to uppercase.

   • Add the ASCII values of the characters together.

Answer:

Answer that gets full marks:

function hash(siteName)
    firstDot = locate(siteName, ".")
    remainingString = siteName[firstDot+1:]

    secondDot = locate(remainingString, ".")
    requiredString = upper(remainingString[:secondDot])

    sum = 0
    for char in requiredString
        sum += asc(char)
    endfor
    
    return sum
endfunction

Acceptable answers you could have given instead:

function hash(siteName)
    parts = siteName.split(".")
    if len(parts) > 2:
        keyString = upper(parts[1])
    else:
        return -1  // handle error or unexpected input
    
    sum = 0
    for char in keyString
        sum += asc(char)
    endfor

    return sum
endfunction