Build and Count a Hash Table, a Tree and a Heap

Goal

You will build a linear probing hash table, an unbalanced binary search tree, a min-heap, and a sorted array yourself, and count, as deterministic numbers, the probe count by load factor, the tree height by input order, the heap replacement count for top-k, and the range count. Finally, you choose a structure for four workloads and attach those numbers as the evidence.

Why it matters

The cost of a data structure can be counted before you measure any time. In a hash table, as the load factor rises, the number of slots you walk to look for one missing key grows as a square; an unbalanced tree turns into a list when it meets sorted input; and a heap that picks the top k discards most items with a single comparison. These numbers do not wobble even on a Pod that shares its CPU, so they serve as evidence for proving to others why you chose a structure. So the grader does not measure time; it runs your classes and functions again on inputs that are not the materials, and compares the probe counts, heights, pop order, and the number of element reads with the reference implementation.

Materials

They are under /opt/fixtures/svccs/structures/. Only read them.

keys.txt        세션 토큰 8,000개(한 줄에 하나, 서로 다름)
absent.txt      keys.txt 에 없는 토큰 3,000개
bst_keys.txt    서로 다른 정수 3,000개(섞인 순서)
stream.csv      id,score 40,000줄(점수 동점이 많다)
timestamps.txt  정렬된 초 단위 시각 30,000줄(같은 초가 여러 번 나온다)
queries.json    {"queries": [[lo, hi], …]} 구간 질의
workload.json   {"scenarios": [{name, desc, …부하별 값, evidence: [근거 키 이름]}]}
params.json     table_size · loads(적재율 목록) · k

Counting rules

집 칸     home(key, size) = int.from_bytes(sha256(key.encode("utf-8")).digest()[:8], "big") % size
탐사      집 칸부터 한 칸씩(끝에서 0 으로 돈다) 본다. 본 칸의 수가 탐사 수 — 첫 칸도 1회,
          찾은 칸도 1회, 없는 키면 마지막 빈 칸도 1회
높이      뿌리에서 잎까지 가장 긴 경로의 노드 수. 빈 트리 0, 노드 하나 1. 같은 키는 다시 넣지 않는다
top-k     점수 큰 순, 동점이면 id 작은 순. 크기 k 최소 힙(키 (score, -id)) — k 개가 찬 뒤
          새 항목의 키가 루트보다 크면 루트를 바꾸고 replacements +1
구간      [lo, hi) — lo 포함, hi 제외, lo >= hi 면 0

Steps

1. In /root/svccs/structures/home.json, write size (table_size from params.json), first5 (the list of home slots of the first 5 keys in keys.txt), and distinct_homes (the number of distinct slots among the home slots of the first size÷2 keys in keys.txt).
2. In /root/svccs/structures/structs.py, create LinearProbeTable(size). insert(key) returns the number of slots looked at (for a key that already exists, it does not insert and returns the number of slots looked at until it is found), search(key) returns a tuple (찾았나, 본 칸의 수) (whether it was found, and the number of slots looked at), and len(table) is the count.
3. For each load factor listed in params.json under loads, put the first n = round(α × size) keys of keys.txt into a new table (of size table_size), and in /root/svccs/structures/loads.json write {"size", "rows": [{"alpha", "n", "avg_hit", "avg_miss", "max_hit", "theory_hit", "theory_miss"}]}. avg_hit is the average probe count of searching for the keys you inserted, avg_miss is the average of searching for absent.txt, max_hit is the maximum over the keys you inserted, theory_hit = ½(1 + 1/(1−α)), theory_miss = ½(1 + 1/(1−α)²), and the averages and theoretical values are to three decimal places.
4. In the same file, create bst_height(keys) (the height after inserting in order into an unbalanced BST), and in /root/svccs/structures/bst.json write n, shuffled_height (the file order of bst_keys.txt), sorted_height (ascending), and min_height (ceil(log2(n + 1))).
5. In the same file, create MinHeap: push(value), pop() (the smallest value; IndexError if empty), and len(heap). Build it yourself with a single array, and do not use heapq or sorting inside the class.
6. In the same file, create top_k(stream, k). The stream is an iterator of (id, score) that can be traversed only once, and it returns {"top": [[id, score], …], "replacements": 정수} (where the replacements value is an integer; you may use heapq). With stream.csv and the k in params.json, in /root/svccs/structures/topk.json write k, n (the number of data lines), top, and replacements.
7. In the same file, create count_range(values, lo, hi) (values is a sorted sequence). Do not copy or scan values; count with binary search. In /root/svccs/structures/ranges.json, write n (the number of lines in timestamps.txt) and counts (the counts in the order of queries.json).
8. In /root/svccs/structures/choose.json, write {"choice", "evidence", "reason"} for each workload in workload.json. choice is one of hash·bst·heap·sorted_array, reason is one sentence, and evidence holds the values, calculated by the rules below, of the keys in that workload's evidence list.

Evidence number rules (step 8)

sessions      alpha = round(n / table_size, 3)
              avg_hit_probes = 크기 table_size 표에 keys.txt 앞 n 개를 넣고 그 키들을 search 한 평균(셋째 자리)
leaderboard   kept = k, replacements = top_k(stream.csv, k) 의 replacements
audit-window  count = timestamps.txt 에서 window 의 [lo, hi) 개수
order-ids     bst_height_sorted = bst_height(1, 2, …, n)
              bst_height_shuffled = bst_height(bst_keys.txt 앞 n 개, 파일 순서)

Notes

• The grader imports structs.py. Put code that reads files and produces results under if __name__ == "__main__": or in a separate script.
• Common mistakes: counting probes as collisions (probes − 1), counting height as the number of edges, recursion exceeding the limit on sorted input, and using bisect_right on the hi side of a range.
• The outputs disappear when the session ends. Keep them elsewhere if you need them.

Compute the home slot with the hash rule

Write the home slots of the first 5 keys in keys.txt, and the number of distinct home slots among the first size÷2 keys, to /root/svccs/structures/home.json as size, first5, and distinct_homes.

Read hashlib.sha256(key.encode('utf-8')).digest()[:8] with int.from_bytes(…, 'big') and take the remainder after dividing by size. If the number of distinct home slots is noticeably smaller than the number of keys even at a load factor of 0.5, that many keys received someone else's slot as their home from the start.

Build a linear probing table and count the probes

Create LinearProbeTable(size) in /root/svccs/structures/structs.py: insert returns the number of slots looked at, and search returns (found or not, the number of slots looked at). The grader compares the probe counts one by one against the reference implementation using variant keys.

Start at the home slot and move one slot at a time, counting, until you meet an empty slot or that key. The first slot counts as 1. After the last slot comes slot 0 (% size). If you keep the search path and the insert path in a single function, the two operations will not count differently.

The load factor changes the probe count

For each load factor 0.5, 0.75, and 0.9, insert keys into a new table, and write the average probe count for present keys and absent keys, the maximum probe count, and the theoretical values to /root/svccs/structures/loads.json.

Build a new table for each load factor. A missing key has to walk until it meets an empty slot, so as the load factor rises it grows much faster than a successful search. The theoretical values are an approximation under the uniform hashing assumption, so they may differ a little from the measurements.

Sorted input turns the tree into a list

Create bst_height(keys) in structs.py, and write the heights from inserting bst_keys.txt in file order and in ascending order to /root/svccs/structures/bst.json. The grader also calls it with 1,500 sorted keys, duplicates, and empty input.

Height is the number of nodes (1 for a single node). If you descend recursively, the depth becomes n on sorted input and you get a RecursionError. Write the insertion as a loop and carry along the maximum depth at which you attached a new node as the height, and then you do not need to compute it separately.

Build a min-heap yourself

Create MinHeap (push, pop, len) in structs.py with a single array. The grader compares the pop order against heapq on a sequence of mixed push/pop operations (including duplicate values and tuples).

Push appends at the end and moves it up while it is smaller than its parent. Pop takes out the root, puts the last element at the root, and then moves it down by swapping with the smaller of its two children. If you look only at the left child, the pop order goes wrong. The children of index k are 2k+1 and 2k+2.

The top k of a stream with a size-k heap

Create top_k(stream, k) in structs.py, and with stream.csv and the k in params.json, write k, n, top, and replacements to /root/svccs/structures/topk.json. The grader passes in variant streams with many ties as iterators.

It is a min-heap of size k, not a max-heap: the root is the threshold. To keep the one with the smaller id on a tie, set the key to (score, -id). For top, at the end sort the heap by score descending and convert it to [id, score]. The stream can be traversed only once.

Count a range with a sorted array and bisect

Create count_range(values, lo, hi) in structs.py and write the range counts from queries.json to /root/svccs/structures/ranges.json. The grader calls it with variant arrays whose boundaries fall on duplicate values, and also counts how many times elements are read.

bisect_left gives "the number of elements smaller than this value." So [lo, hi) is the difference of two bisect_left calls. If you use bisect_right on the hi side, it also counts values equal to hi. If you copy values with list() or scan it with for, you read every element.

Choose a structure for each workload by the numbers

For each of the four workloads in workload.json, choose a structure (hash, bst, heap, sorted_array), calculate the evidence numbers with the functions you built in the earlier steps, and write them to /root/svccs/structures/choose.json.

Look at what each workload asks (exact match, top k, range) and in what order the input arrives. You already measured in step 4 what height you get if you put an ever-growing key into an unbalanced tree. The evidence rules are exactly the "Evidence number rules" in the instructions.