# HashTrace and HashTable

> HashTrace::record(buckets, &keys) starts a table with separate chaining: a key goes to bucket key mod buckets (Euclidean, so negative keys land in a…

Page: https://fframes-kit.pages.dev/docs/computer-science/hash-trace-and-hash-table/
Cargo feature: `cs` (`fframes-kit = { version = "..", features = ["cs"] }`)

`HashTrace::record(buckets, &keys)` starts a table with separate chaining: a key goes to
bucket `key mod buckets` (Euclidean, so negative keys land in a bucket too) and is added to
the end of its chain. `insert`, `find` and `remove` show the hash, walk the chain one entry
a step and note each comparison; a key that is already there is not added twice. `HashTable`
draws the buckets as a column of index cells with each chain to its right, linked by
arrows. Gallery scene: `HashTable`.

Gallery clip of `HashTable`: https://fframes-kit.pages.dev/media/scenes/HashTable-82f8a1b3.mp4

```rust
use fframes_kit::prelude::*;

let table = HashTrace::record(5, &[12, 7, 3]).insert(17).find(9).finish();
let last = table.steps().last().unwrap();
assert_eq!(last.buckets[2].len(), 3);
assert_eq!(last.note, "9 is not there");

fn draw_table<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a HashTrace) -> Svgr<'a> {
    ui.show(HashTable { trace: Some(trace), step_time: 0.6, ..ui.defaults() })
}
```

## API

Components are plain structs. Set the fields you need and fill the rest with `..ui.defaults()`: the defaults below come from the current theme (`theme.` values are fields of `Theme`).

### HashTable

A hash table: a column of numbered buckets, each `height` pixels tall and `gap` apart, with its chain of entries (`cell` pixels wide, `link` pixels apart) linked to its right, centred on `center` (units of `ui.space`). It plays a `HashTrace`, one step every `step_time` seconds from `delay`: the bucket a key hashes to lights up, the entries walked light up one by one, a found entry turns green, new entries slide in at the end of their chain and removed ones leave as the chain closes. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | `Option<&HashTrace>` | `None` | The recorded steps to play (`HashTrace`); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.7` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the table, in units of `ui.space`. |
| `bucket` | `f32` | `64.0` | Width of a bucket in pixels. |
| `cell` | `f32` | `96.0` | Width of an entry in a chain in pixels. |
| `height` | `f32` | `56.0` | Height of a bucket and of its entries in pixels. |
| `gap` | `f32` | `14.0` | Space between neighbouring buckets in pixels. |
| `link` | `f32` | `48.0` | Length of the arrow between a bucket and its first entry, and between entries, in pixels. |
| `notes` | `bool` | `true` | Whether the step's note is written under the table. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the entries in each state (walked, found, moved). |
| `bucket_color` | `Color` | `theme.colors.surface` | Colour of a bucket at rest; the bucket a key hashes to takes `colors.compare`. |
| `link_color` | `Color` | `theme.colors.text` | Colour of the arrows that link a chain. |
| `index_color` | `Color` | `theme.colors.muted` | Colour of the bucket numbers. |
| `value_style` | `TextStyle` | `value_style` | The font of the keys in the entries. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the bucket numbers and notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/hash.rs#L224)