Hash Map Example: Grouping Melodies Played in a Different Key

Two melodies are the same tune when the steps between their notes match, so the steps, not the notes, become the key.

Grouping items that should count as equal needs a canonical key: a value computed from each item that comes out the same for every item that should match, and different for every item that should not. A hash map from that key to a list then collects each group in one pass. Nothing in this problem says hash map. A music app wants to group short melodies that are the same tune started on a different note. Each note is a MIDI number, where a step up of 1 is one semitone, the smallest step between two keys on a piano.

The notes themselves cannot be the key: 60 64 67 and 62 66 69 are the same rising major chord started two semitones apart, and they share no note. What survives the move is the gap from each note to the next, so the steps between notes are the key. The table gives six melodies with their keys.

Six melodies grouped by the steps between their notes
Melody	Notes	Steps between notes (the key)	Group
1	60 64 67	4 3	A
2	62 66 69	4 3	A
3	60 62 64	2 2	B
4	65 69 72	4 3	A
5	67 69 71	2 2	B
6	60 63 67	3 4	C

Summing the steps would be the wrong key. Melodies 1 and 6 both climb 7 semitones in all, but melody 1 takes the large step first and is a major chord, while melody 6 takes the small step first and is a minor one. A key that loses the order of the steps would merge two different tunes. The listing builds each key as a tuple, which Python compares by its contents.

melody_groups.pypy

def group_by_steps(melodies: list[list[int]]) -> dict[tuple[int, ...], list[list[int]]]:
    groups: dict[tuple[int, ...], list[list[int]]] = {}
    for melody in melodies:
        key = tuple(later - earlier for earlier, later in zip(melody, melody[1:]))
        groups.setdefault(key, []).append(melody)
    return groups


melodies = [[60, 64, 67], [62, 66, 69], [60, 62, 64], [65, 69, 72], [67, 69, 71], [60, 63, 67]]
for key, group in group_by_steps(melodies).items():
    print("steps", *key, "->", group)

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

steps 4 3 -> [[60, 64, 67], [62, 66, 69], [65, 69, 72]]
steps 2 2 -> [[60, 62, 64], [67, 69, 71]]
steps 3 4 -> [[60, 63, 67]]

Three groups came out, and melody 6 stands alone although it spans the same 7 semitones as group A. In Java the key can be a List<Integer>, which also compares by contents. In TypeScript a Map compares an array key by reference, so two separate arrays holding 4 and 3 would be two different keys; the key there is a string such as "4,3". Building one key costs O(L) for a melody of L notes, so grouping n melodies costs O(n × L) on average. Anagrams group the same way, under each word's letters in sorted order.

Hash Tables

← → move through sections and cards