What to hand in

algo with index and ordered, passing go test ./..., plus a report.

1. Three searches, one library

n = 1,000 / 10,000 / 100,000, looking up every title:

n	linear (lesson 1)	binary (lesson 6)	hash index

Comparisons per lookup, not time.

Which column grows with n and which does not? Binary search needs sorted data — add the cost of the sort to its column and say after how many lookups it pays for itself.

2. The threshold

In step 5 the threshold was 1.0 and it yields ~1.3 comparisons per lookup.

Change it to 0.5, 2.0 and 4.0. For each, measure comparisons per lookup, the bucket count, and the memory used (len(buckets) × pointer size, plus the entries).

Which threshold looks right to you, and what question has to be answered first for that decision to mean anything at all?

3. The trade, in your own words

Three sentences:

• what a hash table buys;
• what it pays with;
• what you would have to know about your library before choosing one.

Then name two things in your algo program you would already route through a hash index, and one you would not — and why not.

4. Bytes and runes

Step 7 showed how transit breaks Lithuanian search.

Your hashKey works in bytes too. Is that a bug? Answer yes or no and justify it in one sentence.

Then write a Get that finds an item regardless of case ("bamila" finds "Bamila"). Where does the normalization belong — before the hash function or inside it? And what happens if you normalize on lookup but not on insert?

5. When a tree, when a table

Step 8 listed the questions the index cannot answer.

Invent three real features you would want in your library program, and for each say whether a hash index is enough.

At least one of the three must be one where it is not. Describe what you would have to do with the current structure, and what it would cost.

(Lesson 11 starts here.)

---

Coursework option

For anyone who wants it: a prefix index — a structure that answers "which titles start with these letters". Step 7 showed both its price and one way to get it wrong.

It is not a requirement of this lesson.